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 be the language of encoded yes-instances of a decision problem . There are a polynomial and an NTM such that every branch of on input halts within steps and

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

Certificate–Verifier Form

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

The string is a polynomially bounded certificate, and 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 , let be the computation tree of the NTM . Its level contains the configurations reached after steps. Define the level width by

If each configuration has at most successors, where is a constant determined by the fixed machine , then a polynomial-time bound gives

For a deterministic polynomial-time computation, , 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 is polynomial, its width is bounded by —for example, when . This is not hyperexponential or double-exponential growth such as

Here, uses poly notation: it denotes an unspecified polynomial in .

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

Example

Graph -colouring

Given a graph and a natural number , consider the decision problem asking whether has a proper -colouring. A certificate is a function

The verifier checks in polynomial time that

This certifies that the chromatic number satisfies ; it does not by itself prove that is the minimum number of colours.