edited by
11,672 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

Answer:

Related questions

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