15 votes 15 votes The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$ both $\text{NP}$ complete $\text{NP}$-complete and in $\text{P}$ respectively undecidable and $\text{NP}$ complete respectively Algorithms gatecse-2004 algorithms p-np-npc-nph easy isro2017 out-of-gate-syllabus + – Kathleen asked Sep 18, 2014 • edited Jun 13, 2018 by Milicevic3306 Kathleen 11.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply Barney Ross commented Jul 2, 2018 reply Follow Share Is this part of syllabus now? 1 votes 1 votes Please log in or register to add a comment.
Best answer 11 votes 11 votes Option is $C$. http://cstheory.stackexchange.com/questions/6864/why-is-2sat-in-p anshu answered Feb 6, 2015 • edited Jun 13, 2018 by Milicevic3306 anshu comment Share Follow See 1 comment See all 1 1 comment reply ankitgupta.1729 commented Mar 29, 2018 reply Follow Share Why 2-SAT problem is solvable in polynomial time by deterministic machine ? ..It is beautifully explained by Prof. Shai Simonson here :- 2 votes 2 votes Please log in or register to add a comment.
6 votes 6 votes option C $3$-SAT is NP complete $2$-SAT is P Pranay Datta 1 answered Jun 30, 2015 • edited Nov 3, 2017 by kenzou Pranay Datta 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply supraja commented Jun 30, 2015 reply Follow Share Ans is correct But sir ,I read that SAT is NP-complete problem so why can't we say that 2-sat is also NP-complete 2-SAT is in P that indicates that there exists deterministic alg which solves the problem in Polynomial time so can't we write deterministic alg which solves the problem in Polynomial time for 3-SAT problem too.. Please explain me this difference sir... 1 votes 1 votes Pranay Datta 1 commented Jun 30, 2015 reply Follow Share satisfiability problem are not np complete as always . as you see that 2 SAT is not a np complete . 3 SAT problem can be reduced to hamiltonian problem which is a NP complete problem . (with 3 literals ) 2 SAT problem is solved in polynomial time . ( with 2 literal ) BTW do not call me sir , it sounds strange :D . 2 votes 2 votes Please log in or register to add a comment.
5 votes 5 votes Option (c) NP-complete and in P, respectively is the correct answer. Reference :http://infolab.stanford.edu/~ullman/ialc/spr10/slides/pnp2.pdf vinaykumar700156 answered May 7, 2017 vinaykumar700156 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 3 SAT - NPC Problem 2 SAT - p class problem so option c pawan kumarln answered May 8, 2017 pawan kumarln comment Share Follow See all 0 reply Please log in or register to add a comment.