3 votes 3 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 Theory of Computation tifr2016 theory-of-computation reduction p-np-npc-nph + – go_editor asked Dec 28, 2016 recategorized Nov 24, 2022 by Lakshman Bhaiya go_editor 610 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply hs_yadav commented Dec 8, 2017 i edited by hs_yadav Dec 8, 2017 reply Follow Share 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 votes 0 votes Mk Utkarsh commented Dec 8, 2018 reply Follow Share @ankitgupta.1729 why A is true? if $P \neq NP$ then 2SAT is P and not NP right? 0 votes 0 votes ankitgupta.1729 commented Dec 9, 2018 reply Follow Share @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 votes 0 votes Please log in or register to add a comment.
Best answer 0 votes 0 votes 3-SAT is NPC problem. 2-SAT is P problem. NPC cannot be reduced to P (When P$\neq$NP). So C is false. akashsheoran answered Dec 29, 2016 selected Dec 8, 2017 by Rupendra Choudhary akashsheoran comment Share Follow See all 0 reply Please log in or register to add a comment.