+10 votes
3.8k views

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

1. both in $P$

2. both $NP$ complete

3. $NP$-complete and in $P$ respectively

4. undecidable and $NP$ complete respectively

asked
edited | 3.8k views
0
Is this part of syllabus now?

## 7 Answers

+9 votes
Best answer
answered by Active (3.3k points)
edited
0

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

+6 votes

option C

$3$-SAT is NP complete

$2$-SAT is P

answered by Boss (10.3k points)
edited by
+1
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
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 .
+4 votes

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

answered by (255 points)
+2 votes
3 SAT - NPC Problem

2 SAT - p class problem

so option c
answered by Boss (11.6k points)
+1 vote

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

answered by Loyal (9.7k points)
–1 vote
3 sat np and 2 sat p problem
answered by (47 points)
–1 vote
Option C is correct.
answered by Active (2.9k points)
0
2 sat is solvable in polynomial time whereas 3 sat is in np
0
3 Sat in NP-C
Answer:

+15 votes
6 answers
1
+14 votes
7 answers
2
+4 votes
1 answer
3
+21 votes
4 answers
4
+36 votes
4 answers
5
+9 votes
8 answers
6
+15 votes
7 answers
7