I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?
In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out the Strongly Connected Components in that resultant graph. What is wrong in this statement which makes 3 SAT a P problem? eg.
(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
= (-a ->((-b->c).(-c->b)))....2 for each like this
algorithm graph-theory np sat 2-satisfiability
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
add a comment |
In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out the Strongly Connected Components in that resultant graph. What is wrong in this statement which makes 3 SAT a P problem? eg.
(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
= (-a ->((-b->c).(-c->b)))....2 for each like this
algorithm graph-theory np sat 2-satisfiability
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
1
a or b or ccannot be expressed in 2sat.
– wowserx
Nov 13 '18 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 '18 at 7:18
You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere!
– FindersKeeper
Nov 13 '18 at 18:07
add a comment |
In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out the Strongly Connected Components in that resultant graph. What is wrong in this statement which makes 3 SAT a P problem? eg.
(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
= (-a ->((-b->c).(-c->b)))....2 for each like this
algorithm graph-theory np sat 2-satisfiability
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
In case of 3SAT instead of getting 2 implications for one clause, we'd get 12(3C2*2*2) maybe.and which will form a graph of 12m edges when m is the number of clauses in 3 CNF and we can still find out the Strongly Connected Components in that resultant graph. What is wrong in this statement which makes 3 SAT a P problem? eg.
(a+b) = (-a->b).(-b->a)
(a+b+c) = (-a->(b+c)).(-(b+c)->a).....4 more like this
= (-a ->((-b->c).(-c->b)))....2 for each like this
algorithm graph-theory np sat 2-satisfiability
algorithm graph-theory np sat 2-satisfiability
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
edited Nov 12 '18 at 22:35
Kyle Jones
4,82011326
4,82011326
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
asked Nov 11 '18 at 13:07
FindersKeeperFindersKeeper
114
114
1
a or b or ccannot be expressed in 2sat.
– wowserx
Nov 13 '18 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 '18 at 7:18
You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere!
– FindersKeeper
Nov 13 '18 at 18:07
add a comment |
1
a or b or ccannot be expressed in 2sat.
– wowserx
Nov 13 '18 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 '18 at 7:18
You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere!
– FindersKeeper
Nov 13 '18 at 18:07
1
1
a or b or c cannot be expressed in 2sat.– wowserx
Nov 13 '18 at 2:31
a or b or c cannot be expressed in 2sat.– wowserx
Nov 13 '18 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 '18 at 7:18
Why not try to solve it and see if it works?
– n.m.
Nov 13 '18 at 7:18
You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere!
– FindersKeeper
Nov 13 '18 at 18:07
You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere!
– FindersKeeper
Nov 13 '18 at 18:07
add a comment |
1 Answer
1
active
oldest
votes
Unfortunately, 3-SAT cannot be expressed in 2-SAT, so it cannot be as simple as in 2-SAT.
However, there exist many works related to searching a polynomial-time algorithm for 3-SAT.
The idea is to find criteria that can make the 3-SAT instance "Fixed-Parameter Trackable" (FPT).
I can recommend you the article On Fixed-Parameter Tractable Parameterizations of SAT by Stefan Szeider where there is a passage about seeing the SAT instance as a graph and searching a parameter in the graph to make the SAT problem trackable.
You can find more information about FPT here: https://en.wikipedia.org/wiki/Parameterized_complexity
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
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%2fstackoverflow.com%2fquestions%2f53249042%2fi-understand-2-sat-can-be-solved-in-polynomial-time-finding-out-strongly-connect%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
Unfortunately, 3-SAT cannot be expressed in 2-SAT, so it cannot be as simple as in 2-SAT.
However, there exist many works related to searching a polynomial-time algorithm for 3-SAT.
The idea is to find criteria that can make the 3-SAT instance "Fixed-Parameter Trackable" (FPT).
I can recommend you the article On Fixed-Parameter Tractable Parameterizations of SAT by Stefan Szeider where there is a passage about seeing the SAT instance as a graph and searching a parameter in the graph to make the SAT problem trackable.
You can find more information about FPT here: https://en.wikipedia.org/wiki/Parameterized_complexity
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
add a comment |
Unfortunately, 3-SAT cannot be expressed in 2-SAT, so it cannot be as simple as in 2-SAT.
However, there exist many works related to searching a polynomial-time algorithm for 3-SAT.
The idea is to find criteria that can make the 3-SAT instance "Fixed-Parameter Trackable" (FPT).
I can recommend you the article On Fixed-Parameter Tractable Parameterizations of SAT by Stefan Szeider where there is a passage about seeing the SAT instance as a graph and searching a parameter in the graph to make the SAT problem trackable.
You can find more information about FPT here: https://en.wikipedia.org/wiki/Parameterized_complexity
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
add a comment |
Unfortunately, 3-SAT cannot be expressed in 2-SAT, so it cannot be as simple as in 2-SAT.
However, there exist many works related to searching a polynomial-time algorithm for 3-SAT.
The idea is to find criteria that can make the 3-SAT instance "Fixed-Parameter Trackable" (FPT).
I can recommend you the article On Fixed-Parameter Tractable Parameterizations of SAT by Stefan Szeider where there is a passage about seeing the SAT instance as a graph and searching a parameter in the graph to make the SAT problem trackable.
You can find more information about FPT here: https://en.wikipedia.org/wiki/Parameterized_complexity
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
Unfortunately, 3-SAT cannot be expressed in 2-SAT, so it cannot be as simple as in 2-SAT.
However, there exist many works related to searching a polynomial-time algorithm for 3-SAT.
The idea is to find criteria that can make the 3-SAT instance "Fixed-Parameter Trackable" (FPT).
I can recommend you the article On Fixed-Parameter Tractable Parameterizations of SAT by Stefan Szeider where there is a passage about seeing the SAT instance as a graph and searching a parameter in the graph to make the SAT problem trackable.
You can find more information about FPT here: https://en.wikipedia.org/wiki/Parameterized_complexity
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
answered Nov 23 '18 at 12:37
Valentin MontmirailValentin Montmirail
1,74111641
1,74111641
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53249042%2fi-understand-2-sat-can-be-solved-in-polynomial-time-finding-out-strongly-connect%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
1
a or b or ccannot be expressed in 2sat.– wowserx
Nov 13 '18 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 '18 at 7:18
You are right actually. I just thought after learning these, this must be the first thing to come in a students mind, which must be answered somewhere!
– FindersKeeper
Nov 13 '18 at 18:07