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?
2026-03-29 04:42:48.1774759368
Prove in complexity theory
71 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
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.)