Counting models satisfying a boolean formulaProve NP-completeness of deciding satisfiability of monotone boolean formulaHow to represent a 0-valid boolean formula?What is wrong with this seeming contradiction with a paper about AND-compression of SAT?Why do we care about random Boolean SAT formula?What does a square mean in a Boolean formulaUnrolling closures into SAT boolean formulaEfficient alternatives to inclusion-exclusionCounting (enumerating) minimal solutions of a dual horn formulan-DNF boolean formula k satisfiabilityCalculating the number of assignments satisfying a general propositional formula

Python if-else code style for reduced code for rounding floats

How could a scammer know the apps on my phone / iTunes account?

My adviser wants to be the first author

Why do tuner card drivers fail to build after kernel update to 4.4.0-143-generic?

Official degrees of earth’s rotation per day

Planetary tidal locking causing asymetrical water distribution

Is honey really a supersaturated solution? Does heating to un-crystalize redissolve it or melt it?

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Employee lack of ownership

Is there a hypothetical scenario that would make Earth uninhabitable for humans, but not for (the majority of) other animals?

Violin - Can double stops be played when the strings are not next to each other?

As a new Ubuntu desktop 18.04 LTS user, do I need to use ufw for a firewall or is iptables sufficient?

Are ETF trackers fundamentally better than individual stocks?

Knife as defense against stray dogs

Why does a Star of David appear at a rally with Francisco Franco?

Is it true that good novels will automatically sell themselves on Amazon (and so on) and there is no need for one to waste time promoting?

When should I use the pronoun "ri"?

How well should I expect Adam to work?

Math equation in non italic font

Why Choose Less Effective Armour Types?

Adventure Game (text based) in C++

New passport but visa is in old (lost) passport

Describing a chess game in a novel

Most cost effective thermostat setting: consistent temperature vs. lowest temperature possible



Counting models satisfying a boolean formula


Prove NP-completeness of deciding satisfiability of monotone boolean formulaHow to represent a 0-valid boolean formula?What is wrong with this seeming contradiction with a paper about AND-compression of SAT?Why do we care about random Boolean SAT formula?What does a square mean in a Boolean formulaUnrolling closures into SAT boolean formulaEfficient alternatives to inclusion-exclusionCounting (enumerating) minimal solutions of a dual horn formulan-DNF boolean formula k satisfiabilityCalculating the number of assignments satisfying a general propositional formula













1












$begingroup$


I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.



I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?










share|cite|improve this question









New contributor




Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$
















    1












    $begingroup$


    I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.



    I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?










    share|cite|improve this question









    New contributor




    Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$














      1












      1








      1





      $begingroup$


      I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.



      I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?










      share|cite|improve this question









      New contributor




      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.



      I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?







      combinatorics satisfiability 2-sat






      share|cite|improve this question









      New contributor




      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question









      New contributor




      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question








      edited 3 hours ago









      David Richerby

      68.4k15103194




      68.4k15103194






      New contributor




      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 3 hours ago









      Rikard OlssonRikard Olsson

      1082




      1082




      New contributor




      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Rikard Olsson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















          1 Answer
          1






          active

          oldest

          votes


















          3












          $begingroup$

          For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with



          count = 0
          j = number of variables
          for v1 = 0 to 1 do
          for v2 = 0 to 1 do
          ...
          for vj = 0 to 1 do
          if formula_value(phi, v1, ..., vj) == true
          count = count + 1


          This runs in time $Theta(2^j) = O(2^k) = Theta(1)$, since $k$ is fixed.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            Wow, thanks man!!
            $endgroup$
            – Rikard Olsson
            3 hours ago










          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "419"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );






          Rikard Olsson is a new contributor. Be nice, and check out our Code of Conduct.









          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105674%2fcounting-models-satisfying-a-boolean-formula%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          3












          $begingroup$

          For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with



          count = 0
          j = number of variables
          for v1 = 0 to 1 do
          for v2 = 0 to 1 do
          ...
          for vj = 0 to 1 do
          if formula_value(phi, v1, ..., vj) == true
          count = count + 1


          This runs in time $Theta(2^j) = O(2^k) = Theta(1)$, since $k$ is fixed.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            Wow, thanks man!!
            $endgroup$
            – Rikard Olsson
            3 hours ago















          3












          $begingroup$

          For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with



          count = 0
          j = number of variables
          for v1 = 0 to 1 do
          for v2 = 0 to 1 do
          ...
          for vj = 0 to 1 do
          if formula_value(phi, v1, ..., vj) == true
          count = count + 1


          This runs in time $Theta(2^j) = O(2^k) = Theta(1)$, since $k$ is fixed.






          share|cite|improve this answer









          $endgroup$












          • $begingroup$
            Wow, thanks man!!
            $endgroup$
            – Rikard Olsson
            3 hours ago













          3












          3








          3





          $begingroup$

          For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with



          count = 0
          j = number of variables
          for v1 = 0 to 1 do
          for v2 = 0 to 1 do
          ...
          for vj = 0 to 1 do
          if formula_value(phi, v1, ..., vj) == true
          count = count + 1


          This runs in time $Theta(2^j) = O(2^k) = Theta(1)$, since $k$ is fixed.






          share|cite|improve this answer









          $endgroup$



          For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with



          count = 0
          j = number of variables
          for v1 = 0 to 1 do
          for v2 = 0 to 1 do
          ...
          for vj = 0 to 1 do
          if formula_value(phi, v1, ..., vj) == true
          count = count + 1


          This runs in time $Theta(2^j) = O(2^k) = Theta(1)$, since $k$ is fixed.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 3 hours ago









          David RicherbyDavid Richerby

          68.4k15103194




          68.4k15103194











          • $begingroup$
            Wow, thanks man!!
            $endgroup$
            – Rikard Olsson
            3 hours ago
















          • $begingroup$
            Wow, thanks man!!
            $endgroup$
            – Rikard Olsson
            3 hours ago















          $begingroup$
          Wow, thanks man!!
          $endgroup$
          – Rikard Olsson
          3 hours ago




          $begingroup$
          Wow, thanks man!!
          $endgroup$
          – Rikard Olsson
          3 hours ago










          Rikard Olsson is a new contributor. Be nice, and check out our Code of Conduct.









          draft saved

          draft discarded


















          Rikard Olsson is a new contributor. Be nice, and check out our Code of Conduct.












          Rikard Olsson is a new contributor. Be nice, and check out our Code of Conduct.











          Rikard Olsson is a new contributor. Be nice, and check out our Code of Conduct.














          Thanks for contributing an answer to Computer Science Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105674%2fcounting-models-satisfying-a-boolean-formula%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          How should I use the fbox command correctly to avoid producing a Bad Box message?How to put a long piece of text in a box?How to specify height and width of fboxIs there an arrayrulecolor-like command to change the rule color of fbox?What is the command to highlight bad boxes in pdf?Why does fbox sometimes place the box *over* the graphic image?how to put the text in the boxHow to create command for a box where text inside the box can automatically adjust?how can I make an fbox like command with certain color, shape and width of border?how to use fbox in align modeFbox increase the spacing between the box and it content (inner margin)how to change the box height of an equationWhat is the use of the hbox in a newcommand command?

          Doxepinum Nexus interni Notae | Tabula navigationis3158DB01142WHOa682390"Structural Analysis of the Histamine H1 Receptor""Transdermal and Topical Drug Administration in the Treatment of Pain""Antidepressants as antipruritic agents: A review"

          inputenc: Unicode character … not set up for use with LaTeX The Next CEO of Stack OverflowEntering Unicode characters in LaTeXHow to solve the `Package inputenc Error: Unicode char not set up for use with LaTeX` problem?solve “Unicode char is not set up for use with LaTeX” without special handling of every new interesting UTF-8 characterPackage inputenc Error: Unicode character ² (U+B2)(inputenc) not set up for use with LaTeX. acroI2C[I²C]package inputenc error unicode char (u + 190) not set up for use with latexPackage inputenc Error: Unicode char u8:′ not set up for use with LaTeX. 3′inputenc Error: Unicode char u8: not set up for use with LaTeX with G-BriefPackage Inputenc Error: Unicode char u8: not set up for use with LaTeXPackage inputenc Error: Unicode char ́ (U+301)(inputenc) not set up for use with LaTeX. includePackage inputenc Error: Unicode char ̂ (U+302)(inputenc) not set up for use with LaTeX. … $widehatleft (OA,AA' right )$Package inputenc Error: Unicode char â„¡ (U+2121)(inputenc) not set up for use with LaTeX. printbibliography[heading=bibintoc]Package inputenc Error: Unicode char − (U+2212)(inputenc) not set up for use with LaTeXPackage inputenc Error: Unicode character α (U+3B1) not set up for use with LaTeXPackage inputenc Error: Unicode characterError: ! Package inputenc Error: Unicode char ⊘ (U+2298)(inputenc) not set up for use with LaTeX