Certificate complexity of a Boolean function ($C(f)={\max }_x\min \{|S|:S\text{ certifies }f(x)\}$)

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.

For a Boolean function $f$ and a chosen input $x$, a set of coordinates $S$ is a query certificate if every $y$ agreeing with $x$ on $S$ has $f(y)=f(x)$. It fixes actual input bits rather than supplying an independently guessed certificate to an NP verifier. Minimizing its size at each input and then maximizing gives query certificate complexity.