Ttykuu

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

How could an airship be repaired midflight?

How are passwords stolen from companies if they only store hashes?

Book about superhumans hiding among normal humans

Aluminum electrolytic or ceramic capacitors for linear regulator input and output?

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

Is "upgrade" the right word to use in this context?

Did Ender ever learn that he killed Stilson and/or Bonzo?

The German vowel “a” changes to the English “i”

What options are left, if Britain cannot decide?

Why is the President allowed to veto a cancellation of emergency powers?

New passport but visa is in old (lost) passport

What are substitutions for coconut in curry?

How to deal with taxi scam when on vacation?

PTIJ: Who should I vote for? (21st Knesset Edition)

What's the meaning of a knight fighting a snail in medieval book illustrations?

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

Bacteria contamination inside a thermos bottle

How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?

Do I need to be arrogant to get ahead?

What is the Japanese sound word for the clinking of money?

Bach's Toccata and Fugue in D minor breaks the "no parallel octaves" rule?

Is it insecure to send a password in a `curl` command?

How to write cleanly even if my character uses expletive language?

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?

combinatorics satisfiability 2-sat

share|cite|improve this question

edited 3 hours ago

David Richerby

68.4k15103194

asked 3 hours ago

Rikard OlssonRikard Olsson

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.

$endgroup$

add a comment | 

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?

combinatorics satisfiability 2-sat

share|cite|improve this question

edited 3 hours ago

David Richerby

68.4k15103194

asked 3 hours ago

Rikard OlssonRikard Olsson

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.

$endgroup$

add a comment | 

$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?

combinatorics satisfiability 2-sat

share|cite|improve this question

edited 3 hours ago

David Richerby

68.4k15103194

asked 3 hours ago

Rikard OlssonRikard Olsson

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.

$endgroup$

share|cite|improve this question

edited 3 hours ago

David Richerby

68.4k15103194

asked 3 hours ago

Rikard OlssonRikard Olsson

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.

share|cite|improve this question

edited 3 hours ago

David Richerby

68.4k15103194

asked 3 hours ago

Rikard OlssonRikard Olsson

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.

edited 3 hours ago

David Richerby

68.4k15103194

edited 3 hours ago

David Richerby

68.4k15103194

asked 3 hours ago

Rikard OlssonRikard Olsson

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.

asked 3 hours ago

Rikard OlssonRikard Olsson

1082

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

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

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

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');

var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);

;
$window.on('scroll', onScroll);

);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

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

Name

Email

Required, but never shown

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

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

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

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

$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

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194

$endgroup$

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

share|cite|improve this answer

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194

answered 3 hours ago

David RicherbyDavid Richerby

68.4k15103194