edited by
11,658 views
15 votes
15 votes

The problem $\text{3-SAT}$ and $\text{2-SAT}$ are 

  1. both in $\text{P}$

  2. both $\text{NP}$ complete

  3. $\text{NP}$-complete and in $\text{P}$ respectively

  4. undecidable and $\text{NP}$ complete respectively

edited by

7 Answers

Best answer
11 votes
11 votes
edited by
6 votes
6 votes

option C

$3$-SAT is NP complete

$2$-SAT is P

edited by
Answer:

Related questions

8 votes
8 votes
5 answers
2
29 votes
29 votes
7 answers
3
24 votes
24 votes
3 answers
4