Given a language A, which is in NP and also not NP-complete, I have to prove that P != NP.

[Note: A is not trivial]

Any suggestions?


1 Answer 1


If A is in NP but not NP-complete, that means it's not NP-hard. Now assume P = NP and show that every nontrivial language in NP is NP-hard under that assumption.

(The statement even holds for any nontrivial language at all.)

  • $\begingroup$ I stuck at this point, that's the reason I wrote this question. $\endgroup$ Jun 9, 2014 at 17:10
  • $\begingroup$ If P = NP, what can you solve with the reduction you need for an NP-hardness proof? $\endgroup$
    – G. Bach
    Jun 9, 2014 at 17:11
  • $\begingroup$ realy have no idea... $\endgroup$ Jun 9, 2014 at 17:40
  • $\begingroup$ What kind of algorithm is the reduction allowed to be? $\endgroup$
    – G. Bach
    Jun 9, 2014 at 17:44
  • 1
    $\begingroup$ The comment should've been about $B,C \in$ NP to avoid confusion. Assume P = NP; can you then reduce $B$ to $C$ in deterministic polynomial time? How? $\endgroup$
    – G. Bach
    Jun 9, 2014 at 19:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .