GATE2004-30, ISRO2017-10

Question

The problem $3$-SAT and $2$-SAT are 

• A. both in $P$

• B. both $NP$ complete

• C. $NP$-complete and in $P$ respectively

• D. undecidable and $NP$ complete respectively

Comments

Is this part of syllabus now?

Answer 1

Option is $C$.

http://cstheory.stackexchange.com/questions/6864/why-is-2sat-in-p

Comments

Why 2-SAT problem is solvable in polynomial time by deterministic machine ? ..It is beautifully explained by Prof. Shai Simonson   here :-

Answer 2

option C

$3$-SAT is NP complete

$2$-SAT is P

Comments

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...

---

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 .

Answer 3

Option (c)  NP-complete and in P, respectively is the correct answer.

Reference :http://infolab.stanford.edu/~ullman/ialc/spr10/slides/pnp2.pdf

Answer 4

3 SAT - NPC Problem

2 SAT - p class problem

so option c

Answer 5

3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT) when each clause contains exactly k = 3 and k = 2 literals respectively.

2-SAT is P while 3-SAT is NP-Complete.

http://suraj.lums.edu.pk/~cs514s05/data/2SAT.pdf

Answer 6

3 sat np and 2 sat p problem

Answer 7

Option C is correct.

Comments

2 sat is solvable in polynomial time whereas 3 sat is in np

---

3 Sat in NP-C