Query certificate
= Query certificate
{title2=$S\subseteq\{1,\ldots,n\}$}
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 (complexity)> to an NP verifier. Minimizing its size at each input and then maximizing gives <query certificate complexity>.