recategorized by
609 views
3 votes
3 votes

Assume $P \neq NP$. Which of the following is not TRUE?

  1. $2$-SAT in NP
  2. $2$-SAT in coNP
  3. $3$-SAT is polynmial-time reducible to $2$-SAT
  4. 4-SAT is polynmial-time reducible to $3$-SAT
  5. $2$-SAT in P
recategorized by

1 Answer

Answer:

Related questions

4 votes
4 votes
1 answer
2