Certificate (Complexity Theory)

Definition

Certificate (Complexity Theory)

Let be the language of positive problem instances of a decision problem, with instances encoded as strings. A certificate relation for is a relation

such that

A string satisfying is a certificate for the positive instance . The relation identifies which candidates certify which instances; the definition itself imposes no bound on the length of and no efficiency requirement on deciding membership in .

NP Certificates

For NP, certificates must satisfy both restrictions:

where is a polynomial and is a polynomial-time verifier. Equivalently, the certificate relation is polynomially balanced and polynomially decidable. Thus, an NP certificate is a polynomially bounded, efficiently verifiable certificate; the word certificate itself is more general.