**1.3-SAT is polynomial-time reducible to 2-SAT**

means....all **NP problems** could be solved in polynomial time as**(2-SAT is P**) and it indicates **P=NP**

there it is false for **N!= P.**

**:- But what is coNP in 2nd option any one please..???**

Dark Mode

375 views

2 votes

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

- 2-SAT in NP
- 2-SAT in coNP
- 3-SAT is polynmial-time reducible to 2-SAT
- 4-SAT is polynmial-time reducible to 3-SAT
- 2-SAT in P

@Utkarsh, if it is in P then it should also be in NP .. Circle of problems of P class is enclosed by circle of problems of NP class.. So 2-SAT is in P and NP both but 3-SAT is in NP(strictly in NPC) but not in P means we can't solve 3-SAT problem in polynomial time by any deterministic machine for all the instances of problem...

0