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.