Nondeterministic Polynomial Problem

Definition

Nondeterministic Polynomial Problem

A nondeterministic polynomial problem is a decision problem whose yes-instances can be recognised by a nondeterministic Turing machine within a polynomial number of steps. The problem is accepted when at least one computation branch accepts; every branch must halt within the polynomial bound.

Nondeterministic Turing Machine Form

Let $L_{\mathcal{P}}\subseteq {\Sigma }^{\ast }$ be the language of encoded yes-instances of a decision problem $\mathcal{P}$. There are a polynomial $p$ and an NTM $M$ such that every branch of $M$ on input $x$ halts within $p(|x|)$ steps and

$$x\in L_{\mathcal{P}}⟺\text{some computation branch of }M\text{ on }x\text{ accepts}.$$

The existential condition is the guessing phase: one successful branch is enough.

Certificate–Verifier Form

Equivalently, there are a polynomial $q$ and a deterministic polynomial-time verifier $V$ such that

$$x\in L_{\mathcal{P}}⟺\exists y\in {\Sigma }^{\ast }:|y|\le q(|x|)\wedge V(x,y)=1.$$

The string $y$ is a polynomially bounded certificate, and $V$ performs the verification. Equivalently, the associated certificate relation is polynomially balanced and polynomially decidable. The set of all such problems is the complexity class NP.

Width of the Computation Tree

For an input $x$, let $T_M(x)$ be the computation tree of the NTM $M$. Its level $L_i$ contains the configurations reached after $i$ steps. Define the level width by

$$\mathrm{width}(T_M(x))=\underset{i}{\max }|L_i|.$$

If each configuration has at most $b$ successors, where $b$ is a constant determined by the fixed machine $M$, then a polynomial-time bound $p(|x|)$ gives

$$|L_i|\le b^i,\mathrm{width}(T_M(x))\le b^{p(|x|)}=2^{p(|x|){\log }_{2}b}=2^{O(p(|x|))}.$$

For a deterministic polynomial-time computation, $b=1$, so every level contains at most one configuration: the computation tree is a single path, or linked list. This is a property of the deterministic machine witnessing membership in P; an NTM that happens to decide a problem in P may still branch.

For an NP computation, the tree may therefore be exponentially wide. If $p(n)$ is polynomial, its width is bounded by $2^{O(p(n))}$—for example, $2^{O(n^k)}$ when $p(n)=O(n^k)$. This is not hyperexponential or double-exponential growth such as

$$2^{2^{\mathrm{poly}(n)}}.$$

Here, $\mathrm{poly}(n)$ uses poly notation: it denotes an unspecified polynomial in $n$.

The branching tree is exponentially wide, but its depth remains polynomial.

Example

Graph $k$-colouring

Given a graph $G=(V,E)$ and a natural number $k$, consider the decision problem asking whether $G$ has a proper $k$-colouring. A certificate is a function

$$c:V\to \{1,\dots ,k\}.$$

The verifier checks in polynomial time that

$$\forall \{u,v\}\in E:c(u)\ne c(v).$$

This certifies that the chromatic number satisfies $\chi (G)\le k$; it does not by itself prove that $k$ is the minimum number of colours.