in Others retagged by
375 views
2 votes
2 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
in Others retagged by
375 views

3 Comments

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

0
0

@ankitgupta.1729 why A is true? 

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

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

1 Answer

0 votes
0 votes
Best answer
3-SAT is NPC problem.

2-SAT is P problem.

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

So C is false.
selected by
Answer:

Related questions