I understand 2 SAT can be solved in Polynomial time finding out Strongly Connected Components. What about doing the same for 3SAT?
up vote
2
down vote
favorite
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 at 22:35
Kyle Jones
4,78011226
asked Nov 11 at 13:07
FindersKeeper
114
add a comment |
up vote
2
down vote
favorite
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 at 22:35
Kyle Jones
4,78011226
asked Nov 11 at 13:07
FindersKeeper
114
1
a or b or ccannot be expressed in 2sat.
– wowserx
Nov 13 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 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 at 18:07
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 at 22:35
Kyle Jones
4,78011226
asked Nov 11 at 13:07
FindersKeeper
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 at 22:35
Kyle Jones
4,78011226
asked Nov 11 at 13:07
FindersKeeper
114
edited Nov 12 at 22:35
Kyle Jones
4,78011226
asked Nov 11 at 13:07
FindersKeeper
114
edited Nov 12 at 22:35
Kyle Jones
4,78011226
edited Nov 12 at 22:35
Kyle Jones
4,78011226
edited Nov 12 at 22:35
Kyle Jones
4,78011226
4,78011226
asked Nov 11 at 13:07
FindersKeeper
114
asked Nov 11 at 13:07
FindersKeeper
114
asked Nov 11 at 13:07
FindersKeeper
114
114
1
a or b or ccannot be expressed in 2sat.
– wowserx
Nov 13 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 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 at 18:07
add a comment |
1
a or b or ccannot be expressed in 2sat.
– wowserx
Nov 13 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 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 at 18:07
1
1
a or b or c cannot be expressed in 2sat.– wowserx
Nov 13 at 2:31
a or b or c cannot be expressed in 2sat.– wowserx
Nov 13 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 at 7:18
Why not try to solve it and see if it works?
– n.m.
Nov 13 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 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 at 18:07
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
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 at 12:37
Valentin Montmirail
1,71111541
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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 at 12:37
Valentin Montmirail
1,71111541
add a comment |
up vote
0
down vote
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 at 12:37
Valentin Montmirail
1,71111541
add a comment |
up vote
0
down vote
up vote
0
down vote
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 at 12:37
Valentin Montmirail
1,71111541
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 at 12:37
Valentin Montmirail
1,71111541
answered Nov 23 at 12:37
Valentin Montmirail
1,71111541
answered Nov 23 at 12:37
Valentin Montmirail
1,71111541
answered Nov 23 at 12:37
Valentin Montmirail
1,71111541
1,71111541
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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 at 2:31
Why not try to solve it and see if it works?
– n.m.
Nov 13 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 at 18:07