= Certificate complexity of a Boolean function
{title2=$C(f)=\max_x\min\{|S|:S\text{ certifies }f(x)\}$}
= Query certificate complexity
{synonym}
A <query certificate> fixes some input coordinates to their values in a chosen input and must force the output for every completion. The smallest such size is $C(f,x)$; maximizing over accepted or rejected inputs gives $C_1(f)$ or $C_0(f)$, and maximizing both gives $C(f)$. A one-sided maximum over an empty output class is defined as zero. This is <query certificate> complexity, distinct from polynomial verification of a witness in <NP>.
Back to article page
