Given a problem instance and a solution (certificate), verify that the solution solves the problem.

Example: PATH problem

Given:

(G, u, v, k, ) path p

Verify:

length(p)  k

In some cases, having a certificate does not help much since verification is no faster than generating a solution from scratch (e.g., PATH). However, this is not true of all problems...