Counting models satisfying a boolean formulaProve NP-completeness of deciding satisfiability of monotone...
Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?
How could an airship be repaired midflight?
How to deal with taxi scam when on vacation?
How to pronounce "I ♥ Huckabees"?
Problem with FindRoot
Are ETF trackers fundamentally better than individual stocks?
Examples of transfinite towers
Bacteria contamination inside a thermos bottle
Why do tuner card drivers fail to build after kernel update to 4.4.0-143-generic?
Is honey really a supersaturated solution? Does heating to un-crystalize redissolve it or melt it?
How do I change two letters closest to a string and one letter immediately after a string using Notepad++?
Why does a Star of David appear at a rally with Francisco Franco?
Describing a chess game in a novel
Do I need life insurance if I can cover my own funeral costs?
This word with a lot of past tenses
As a new Ubuntu desktop 18.04 LTS user, do I need to use ufw for a firewall or is iptables sufficient?
Is it normal that my co-workers at a fitness company criticize my food choices?
What is the adequate fee for a reveal operation?
Meme-controlled people
Does this sum go infinity?
Professor being mistaken for a grad student
What options are left, if Britain cannot decide?
Why no Iridium-level flares from other satellites?
Print a physical multiplication table
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
$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
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
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
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$
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
combinatorics satisfiability 2-sat
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
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
edited 3 hours ago
David Richerby
68.4k15103194
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
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.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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.
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
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.
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.
answered 3 hours ago
David RicherbyDavid Richerby
68.4k15103194
$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.
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
answered 3 hours ago
David RicherbyDavid Richerby
68.4k15103194
68.4k15103194
$begingroup$
Wow, thanks man!!
$endgroup$
– Rikard Olsson
3 hours ago
add a comment |
$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
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
