375 views

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

edited by

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..???

@ankitgupta.1729 why A is true?

if $P \neq NP$ then 2SAT is P and not NP right?

@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...

3-SAT is NPC problem.

2-SAT is P problem.

NPC cannot be reduced to P (When P$\neq$NP).

So C is false.