Are there any known problems in NP (and not in P) that aren\'t NP Complete? My u

Question

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

If there is a problem that is NP (and not P) but not NP-complete, would this be a result of no existing isomorphism between instances of that problem and the NP-complete set? If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP-complete set?

Explanation / Answer

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

No, this is unknown (with the exception of the trivial languages ? and ??, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an NP problem which is not complete for NP w.r.t. many-one polynomial time reductions would imply that P?NP which is not known (although widely believed). If the two classes are different then we know that there are problems in NP which are not complete for it, take any problem in P.

If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

If the two complexity classes are different then by Ladner's theorem there are problems which are NP-intermediate, i.e. they are between P and NP-complete.

If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

They are still polynomial time reducible to NP-complete problems so they cannot be harder than NP-complete problems.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.