How do I reduce 3-SAT to a 3-SAT NAE problem?
$begingroup$
I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.
Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.
Anyway, how do I go for that?
Since the size of each clause is already the same, I don't have to work on that.
But I can't seem to find a way to create an instance I2 of 3SAT-NAE which is accepted iff the 3SAT accepts it.
EXTRA QUESTION: Does SAT (or 3SAT) allow any operation in the clauses? Because I always saw V (or) and never other operations. That confuses me a lot, because if it only allows V, then I don't get the reduction I found; but if it accepts even AND, then I get it.
np-complete
asked Jan 22 '14 at 17:04
N3shN3sh
1314
$endgroup$
add a comment |
$begingroup$
I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.
Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.
Anyway, how do I go for that?
Since the size of each clause is already the same, I don't have to work on that.
But I can't seem to find a way to create an instance I2 of 3SAT-NAE which is accepted iff the 3SAT accepts it.
EXTRA QUESTION: Does SAT (or 3SAT) allow any operation in the clauses? Because I always saw V (or) and never other operations. That confuses me a lot, because if it only allows V, then I don't get the reduction I found; but if it accepts even AND, then I get it.
np-complete
asked Jan 22 '14 at 17:04
N3shN3sh
1314
$endgroup$
$begingroup$
with NOT all Equal you mean: all clauses true but for a single one? And No: SAT and 3-SAT are in en.wikipedia.org/wiki/Conjunctive_normal_form that's why you'll always find $lor$ inside the clause and $land$ between them
$endgroup$
– b00n heT
Jan 22 '14 at 17:06
1
$begingroup$
There must be at least 1 True and 1 False. {T,T,F} {F,F,T} {T,F,T} {F,T,F}.... The one you said is similar to OIT (On In Three) and wants exactly 1 True and 2 False.
$endgroup$
– N3sh
Jan 22 '14 at 17:07
add a comment |
$begingroup$
I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.
Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.
Anyway, how do I go for that?
Since the size of each clause is already the same, I don't have to work on that.
But I can't seem to find a way to create an instance I2 of 3SAT-NAE which is accepted iff the 3SAT accepts it.
EXTRA QUESTION: Does SAT (or 3SAT) allow any operation in the clauses? Because I always saw V (or) and never other operations. That confuses me a lot, because if it only allows V, then I don't get the reduction I found; but if it accepts even AND, then I get it.
np-complete
asked Jan 22 '14 at 17:04
N3shN3sh
1314
$endgroup$
I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.
Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.
Anyway, how do I go for that?
Since the size of each clause is already the same, I don't have to work on that.
But I can't seem to find a way to create an instance I2 of 3SAT-NAE which is accepted iff the 3SAT accepts it.
EXTRA QUESTION: Does SAT (or 3SAT) allow any operation in the clauses? Because I always saw V (or) and never other operations. That confuses me a lot, because if it only allows V, then I don't get the reduction I found; but if it accepts even AND, then I get it.
np-complete
np-complete
asked Jan 22 '14 at 17:04
N3shN3sh
1314
asked Jan 22 '14 at 17:04
N3shN3sh
1314
asked Jan 22 '14 at 17:04
N3shN3sh
1314
asked Jan 22 '14 at 17:04
N3shN3sh
1314
asked Jan 22 '14 at 17:04
N3shN3sh
1314
1314
$begingroup$
with NOT all Equal you mean: all clauses true but for a single one? And No: SAT and 3-SAT are in en.wikipedia.org/wiki/Conjunctive_normal_form that's why you'll always find $lor$ inside the clause and $land$ between them
$endgroup$
– b00n heT
Jan 22 '14 at 17:06
1
$begingroup$
There must be at least 1 True and 1 False. {T,T,F} {F,F,T} {T,F,T} {F,T,F}.... The one you said is similar to OIT (On In Three) and wants exactly 1 True and 2 False.
$endgroup$
– N3sh
Jan 22 '14 at 17:07
add a comment |
$begingroup$
with NOT all Equal you mean: all clauses true but for a single one? And No: SAT and 3-SAT are in en.wikipedia.org/wiki/Conjunctive_normal_form that's why you'll always find $lor$ inside the clause and $land$ between them
$endgroup$
– b00n heT
Jan 22 '14 at 17:06
1
$begingroup$
There must be at least 1 True and 1 False. {T,T,F} {F,F,T} {T,F,T} {F,T,F}.... The one you said is similar to OIT (On In Three) and wants exactly 1 True and 2 False.
$endgroup$
– N3sh
Jan 22 '14 at 17:07
$begingroup$
with NOT all Equal you mean: all clauses true but for a single one? And No: SAT and 3-SAT are in en.wikipedia.org/wiki/Conjunctive_normal_form that's why you'll always find $lor$ inside the clause and $land$ between them
$endgroup$
– b00n heT
Jan 22 '14 at 17:06
$begingroup$
with NOT all Equal you mean: all clauses true but for a single one? And No: SAT and 3-SAT are in en.wikipedia.org/wiki/Conjunctive_normal_form that's why you'll always find $lor$ inside the clause and $land$ between them
$endgroup$
– b00n heT
Jan 22 '14 at 17:06
1
1
$begingroup$
There must be at least 1 True and 1 False. {T,T,F} {F,F,T} {T,F,T} {F,T,F}.... The one you said is similar to OIT (On In Three) and wants exactly 1 True and 2 False.
$endgroup$
– N3sh
Jan 22 '14 at 17:07
$begingroup$
There must be at least 1 True and 1 False. {T,T,F} {F,F,T} {T,F,T} {F,T,F}.... The one you said is similar to OIT (On In Three) and wants exactly 1 True and 2 False.
$endgroup$
– N3sh
Jan 22 '14 at 17:07
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For the pedantic's sake, we first have a polynomial reduction $3SAT leq_p s3SAT$, where the later has strictly 3 terms per clause, not less (as accepted by the former). This is achieved by taking an instance of $3SAT$ and mapping the clauses respectively:
$ (a) mapsto (lnot s lor lnot s lor lnot s) land (s lor s lor a) $
$ (a lor b) mapsto (lnot s lor lnot s lor lnot s) land (s lor b lor a) $
where $s$ is a dummy variable, and a and b are terms where $lnot lnot$ is negated respectively. We concatenate the end result with $land$. Clearly we construct in polynomial time.
Next we do the polynomial reduction $s3SAT leq_p NAE-4SAT$, where the second is simply $NAE-3SAT$ but with four terms per clause. For this we take an instance of $s3SAT$ and map each clause as follows:
$ (x lor y lor z) mapsto (x lor y lor z lor s) land (lnot x lor lnot y lor lnot z lor lnot s)$
Where $x,y,z$ are terms and $s$ is our dummy variable, as before. Notice the symmetry here, if we find an assignment with $s = true$ we can simply invert the assignment to receive another valid assignment with $s=false$. This is the assignment we want.
As a last step we reduce $NAE-4SAT leq_p NAE-3SAT$. Take an instance in $NAE-4SAT$ and map the clauses as follows:
$ (a lor b lor c lor d) mapsto (s lor a lor b) land (lnot s lor c lor d)$
All the same as before, concatenate the result once more. Notice here that if the true and false variable's (one of each must exist) are mapped to the same clause, $s$ can be choose appropriately. If they are mapped to different clauses, $s$ can be choose opposite to the respective variable value in each pair.
To summarize: $3SAT leq_p s3-SAT leq_p NAE_4SAT leq_p NAE-3SAT$.
Answer to extra question: 3SAT only allows $lor$ in the clauses.
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
$endgroup$
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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fmath.stackexchange.com%2fquestions%2f647710%2fhow-do-i-reduce-3-sat-to-a-3-sat-nae-problem%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 the pedantic's sake, we first have a polynomial reduction $3SAT leq_p s3SAT$, where the later has strictly 3 terms per clause, not less (as accepted by the former). This is achieved by taking an instance of $3SAT$ and mapping the clauses respectively:
$ (a) mapsto (lnot s lor lnot s lor lnot s) land (s lor s lor a) $
$ (a lor b) mapsto (lnot s lor lnot s lor lnot s) land (s lor b lor a) $
where $s$ is a dummy variable, and a and b are terms where $lnot lnot$ is negated respectively. We concatenate the end result with $land$. Clearly we construct in polynomial time.
Next we do the polynomial reduction $s3SAT leq_p NAE-4SAT$, where the second is simply $NAE-3SAT$ but with four terms per clause. For this we take an instance of $s3SAT$ and map each clause as follows:
$ (x lor y lor z) mapsto (x lor y lor z lor s) land (lnot x lor lnot y lor lnot z lor lnot s)$
Where $x,y,z$ are terms and $s$ is our dummy variable, as before. Notice the symmetry here, if we find an assignment with $s = true$ we can simply invert the assignment to receive another valid assignment with $s=false$. This is the assignment we want.
As a last step we reduce $NAE-4SAT leq_p NAE-3SAT$. Take an instance in $NAE-4SAT$ and map the clauses as follows:
$ (a lor b lor c lor d) mapsto (s lor a lor b) land (lnot s lor c lor d)$
All the same as before, concatenate the result once more. Notice here that if the true and false variable's (one of each must exist) are mapped to the same clause, $s$ can be choose appropriately. If they are mapped to different clauses, $s$ can be choose opposite to the respective variable value in each pair.
To summarize: $3SAT leq_p s3-SAT leq_p NAE_4SAT leq_p NAE-3SAT$.
Answer to extra question: 3SAT only allows $lor$ in the clauses.
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
$endgroup$
add a comment |
$begingroup$
For the pedantic's sake, we first have a polynomial reduction $3SAT leq_p s3SAT$, where the later has strictly 3 terms per clause, not less (as accepted by the former). This is achieved by taking an instance of $3SAT$ and mapping the clauses respectively:
$ (a) mapsto (lnot s lor lnot s lor lnot s) land (s lor s lor a) $
$ (a lor b) mapsto (lnot s lor lnot s lor lnot s) land (s lor b lor a) $
where $s$ is a dummy variable, and a and b are terms where $lnot lnot$ is negated respectively. We concatenate the end result with $land$. Clearly we construct in polynomial time.
Next we do the polynomial reduction $s3SAT leq_p NAE-4SAT$, where the second is simply $NAE-3SAT$ but with four terms per clause. For this we take an instance of $s3SAT$ and map each clause as follows:
$ (x lor y lor z) mapsto (x lor y lor z lor s) land (lnot x lor lnot y lor lnot z lor lnot s)$
Where $x,y,z$ are terms and $s$ is our dummy variable, as before. Notice the symmetry here, if we find an assignment with $s = true$ we can simply invert the assignment to receive another valid assignment with $s=false$. This is the assignment we want.
As a last step we reduce $NAE-4SAT leq_p NAE-3SAT$. Take an instance in $NAE-4SAT$ and map the clauses as follows:
$ (a lor b lor c lor d) mapsto (s lor a lor b) land (lnot s lor c lor d)$
All the same as before, concatenate the result once more. Notice here that if the true and false variable's (one of each must exist) are mapped to the same clause, $s$ can be choose appropriately. If they are mapped to different clauses, $s$ can be choose opposite to the respective variable value in each pair.
To summarize: $3SAT leq_p s3-SAT leq_p NAE_4SAT leq_p NAE-3SAT$.
Answer to extra question: 3SAT only allows $lor$ in the clauses.
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
$endgroup$
add a comment |
$begingroup$
For the pedantic's sake, we first have a polynomial reduction $3SAT leq_p s3SAT$, where the later has strictly 3 terms per clause, not less (as accepted by the former). This is achieved by taking an instance of $3SAT$ and mapping the clauses respectively:
$ (a) mapsto (lnot s lor lnot s lor lnot s) land (s lor s lor a) $
$ (a lor b) mapsto (lnot s lor lnot s lor lnot s) land (s lor b lor a) $
where $s$ is a dummy variable, and a and b are terms where $lnot lnot$ is negated respectively. We concatenate the end result with $land$. Clearly we construct in polynomial time.
Next we do the polynomial reduction $s3SAT leq_p NAE-4SAT$, where the second is simply $NAE-3SAT$ but with four terms per clause. For this we take an instance of $s3SAT$ and map each clause as follows:
$ (x lor y lor z) mapsto (x lor y lor z lor s) land (lnot x lor lnot y lor lnot z lor lnot s)$
Where $x,y,z$ are terms and $s$ is our dummy variable, as before. Notice the symmetry here, if we find an assignment with $s = true$ we can simply invert the assignment to receive another valid assignment with $s=false$. This is the assignment we want.
As a last step we reduce $NAE-4SAT leq_p NAE-3SAT$. Take an instance in $NAE-4SAT$ and map the clauses as follows:
$ (a lor b lor c lor d) mapsto (s lor a lor b) land (lnot s lor c lor d)$
All the same as before, concatenate the result once more. Notice here that if the true and false variable's (one of each must exist) are mapped to the same clause, $s$ can be choose appropriately. If they are mapped to different clauses, $s$ can be choose opposite to the respective variable value in each pair.
To summarize: $3SAT leq_p s3-SAT leq_p NAE_4SAT leq_p NAE-3SAT$.
Answer to extra question: 3SAT only allows $lor$ in the clauses.
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
$endgroup$
For the pedantic's sake, we first have a polynomial reduction $3SAT leq_p s3SAT$, where the later has strictly 3 terms per clause, not less (as accepted by the former). This is achieved by taking an instance of $3SAT$ and mapping the clauses respectively:
$ (a) mapsto (lnot s lor lnot s lor lnot s) land (s lor s lor a) $
$ (a lor b) mapsto (lnot s lor lnot s lor lnot s) land (s lor b lor a) $
where $s$ is a dummy variable, and a and b are terms where $lnot lnot$ is negated respectively. We concatenate the end result with $land$. Clearly we construct in polynomial time.
Next we do the polynomial reduction $s3SAT leq_p NAE-4SAT$, where the second is simply $NAE-3SAT$ but with four terms per clause. For this we take an instance of $s3SAT$ and map each clause as follows:
$ (x lor y lor z) mapsto (x lor y lor z lor s) land (lnot x lor lnot y lor lnot z lor lnot s)$
Where $x,y,z$ are terms and $s$ is our dummy variable, as before. Notice the symmetry here, if we find an assignment with $s = true$ we can simply invert the assignment to receive another valid assignment with $s=false$. This is the assignment we want.
As a last step we reduce $NAE-4SAT leq_p NAE-3SAT$. Take an instance in $NAE-4SAT$ and map the clauses as follows:
$ (a lor b lor c lor d) mapsto (s lor a lor b) land (lnot s lor c lor d)$
All the same as before, concatenate the result once more. Notice here that if the true and false variable's (one of each must exist) are mapped to the same clause, $s$ can be choose appropriately. If they are mapped to different clauses, $s$ can be choose opposite to the respective variable value in each pair.
To summarize: $3SAT leq_p s3-SAT leq_p NAE_4SAT leq_p NAE-3SAT$.
Answer to extra question: 3SAT only allows $lor$ in the clauses.
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
answered Jun 22 '18 at 12:13
ZirconCodeZirconCode
529417
529417
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f647710%2fhow-do-i-reduce-3-sat-to-a-3-sat-nae-problem%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
$begingroup$
with NOT all Equal you mean: all clauses true but for a single one? And No: SAT and 3-SAT are in en.wikipedia.org/wiki/Conjunctive_normal_form that's why you'll always find $lor$ inside the clause and $land$ between them
$endgroup$
– b00n heT
Jan 22 '14 at 17:06
1
$begingroup$
There must be at least 1 True and 1 False. {T,T,F} {F,F,T} {T,F,T} {F,T,F}.... The one you said is similar to OIT (On In Three) and wants exactly 1 True and 2 False.
$endgroup$
– N3sh
Jan 22 '14 at 17:07