Definition
Nondeterministic Polynomial Problem
A non-deterministic polynomial problem is a problem for which a given solution can be verified in polynomial time.
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.
Examples: Verification
- Problem: Given a graph and a natural number . Is the minimal number of colours, such that there exists a -colouring of ?
- Certificate: A -colouring of .
- 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.