-5
$\begingroup$

Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this?

P = NP

P ⊊ NP

P ≠ NP

NP ⊆ P

$\endgroup$
1

1 Answer 1

1
$\begingroup$

What would happen if $P=NP$? Clearly $P$-complete $=P$, and hence also $NP$-complete = $NP$. This means that every language in $NP$ would also be in $NP$-complete. So finding a language that isn't $NP$-complete, means that we must have $P\neq NP$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.