Nondeterministic Polynomial Problem

computation

Definition

Nondeterministic Polynomial Problem

Verifier decision problem for which a given solution can be verified in polynomial time. Equivalently, there is a polynomial-time verifier $V(I,c)$ such that an instance $I$ is a yes-instance exactly when there exists a certificate $c$ with $V(I,c)=1$.

A nondeterministic polynomial problem is a

Choice-program decision problem that can be decided by a nondeterministic program with polynomial running time. Such a program may branch by making polynomially many binary choices, and it accepts exactly when at least one computation branch returns true.

A nondeterministic polynomial problem is a

Verification

Certificate

Certificate

A certificate is a piece of information that allows the efficient verification (using a verifier) of a “yes” answer of a decision problem.

Verifier

Verifier

A verifier is a tractable problem that, given a problem instance and a potential certificate, can determine if the certificate is valid.

Verification

• Problem: Given a graph $G$ and a natural number $k$. Is $k$ the minimal number of colours, such that there exists a $k$-colouring of $G$?
• Certificate: A $k$-colouring of $G$.
• Verifier: Verify that there are no same-coloured neighbour nodes.
• Validity: No, since we can only verify that the colouring is valid, not that it is minimal.