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
1
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/142937/755, stackoverflow.com/q/68662236/781723. Please do not post the same question on multiple sites. $\endgroup$– D.W. ♦Commented Aug 13, 2021 at 17:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$
answered Aug 5, 2021 at 9:08