Certificate (Complexity Theory)

complexity-theory

Definition

Certificate (Complexity Theory)

Let $\mathcal{P}$ be a decision problem and $\text{INSTANCES}(\mathcal{P})$ be set of all instances of $\mathcal{P}$.

A certificate (relation) for $\mathcal{P}$ is a relation

$$R\subseteq \text{INSTANCES}(\mathcal{P})\times \text{STRINGS}$$

where $\text{STRINGS}$ is the set of all strings, such that:

$$\begin{array}{r}I\in \text{INSTANCES}(\mathcal{P})\text{ positive}\\ ⟺\\ \exists \text{ certificate }C\in \text{STRING}:(I,C)\in R\end{array}$$