NP-intermediate Problem

Definition

NP-intermediate Problem

An NP-intermediate problem is a decision problem that is an NP problem, is not in P, and is not NP-complete under polynomial-time many-one reductions:

Existence and natural candidates

If , Ladner’s theorem guarantees that NP-intermediate problems exist, although its proof constructs artificial languages. No natural problem is currently known to be NP-intermediate.

Prominent candidates include:

• the graph isomorphism problem;
• the decision variant of integer factorisation asking whether has a divisor with ;
• the minimum circuit size problem, which asks whether a Boolean function given by its truth table has a circuit of size at most .