Definition
Ladner's Theorem
If
, then at least one NP-intermediate problem exists. The theorem gives no natural example. The graph isomorphism problem is a prominent candidate, but is not known to be NP-intermediate.
Ladner's Theorem
If
, then at least one NP-intermediate problem exists. The theorem gives no natural example. The graph isomorphism problem is a prominent candidate, but is not known to be NP-intermediate.