NP-intermediate Problem

Definition

NP-intermediate Problem

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

$$\mathcal{P}\in \mathrm{NP},\mathcal{P}\notin \mathrm{P},\mathcal{P}\text{ is not NP-complete}.$$

Existence and natural candidates

If $\mathrm{P}\ne \mathrm{NP}$, 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 $n$ has a divisor $d$ with $1<d\le k$;
• the minimum circuit size problem, which asks whether a Boolean function given by its truth table has a circuit of size at most $s$.