Q The Query Complexity Zoo
\(\mathrm{Search}(\varphi)\)

SearchCNF

The canonical TFNP-style query relation: given an assignment, output a falsified clause.

relation relational arity: $n$ bits (an assignment to an unsatisfiable CNF $\varphi$)

Description

Fix an unsatisfiable $k$-CNF $\varphi$ on $n$ variables. Given an assignment $x$, output (the index of) some clause of $\varphi$ falsified by $x$. Total by unsatisfiability. This is the query-complexity home of TFNP$^{dt}$ and of resolution lower bounds.

Measure values

MeasureValueNotes
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(1)\)· For a random $\Delta$-dense unsatisfiable $k$-CNF with $\Delta$ a large enough constant: with high probability every assignment falsifies a constant fraction of the clauses, so sampling $O(1)$ clauses at random and reading their $k$ variables finds a falsified one. At least one query is needed, so $\Theta(1)$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Omega(n^{1/3})\) $\Omega(\sqrt n)$ in the related setting of [GIPS21]; also $\exp(\widetilde\Omega(n^{1/4}))$ in pseudo-deterministic decision-tree size. CDM23
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(n)\)· For a random $\Delta$-dense unsatisfiable $k$-CNF. $\mathrm{D}(\mathrm{Search}(\varphi))$ is the minimum depth of a tree-like resolution refutation of $\varphi$ [LNNW95] -- a decision tree solving the search problem, read leaf-to-root, is exactly such a refutation. Random $k$-CNFs require resolution width $\Omega(n)$, hence depth $\Omega(n)$; and $n$ queries trivially suffice. So the $\mathrm{R} = O(1)$ upper bound above is an unbounded $\mathrm{D}$-vs-$\mathrm{R}$ separation, for a total relation. LNNW95 BenSassonWigderson01
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\)· Decision-tree size for the search problem equals tree-like resolution size, and the size-width tradeoff of [BenSassonWigderson01] with the $\Omega(n)$ width bound gives $2^{\Omega(n)}$ for random $k$-CNFs; $2^n$ is the trivial ceiling. Compare $\mathrm{R}=O(1)$: no bounded-error algorithm needs to know anything about $\varphi$ beyond one clause. BenSassonWigderson01
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every variable is relevant, so a non-adaptive algorithm reads the whole assignment.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(1)\)· putative Sampling a clause of $\varphi$ at random and reading its $k$ variables is non-adaptive; for a random $\Delta$-dense $\varphi$ a constant fraction of clauses is falsified by any fixed assignment, so $O(1)$ tries suffice.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(1)\) putative For the random $\Delta$-dense formula this entry is otherwise about -- not $\Theta(n)$. Critical block sensitivity lower-bounds the randomized cost: let $s$ be the plurality output of a bounded-error algorithm, take a critical $x$ and $b$ disjoint blocks with $s(x^B) \ne s(x)$; an algorithm that never queries inside $B$ cannot answer whp at both $x$ and $x^B$, so it must enter each block with constant probability and $\mathrm{cbs} = O(\mathrm{R})$. Here $\mathrm{R} = \Theta(1)$. [ABK21lifting] give the same conclusion through $\mathrm{cbs} = O(\mathrm{CA})$ with $\mathrm{CA} = \Theta(1)$. The famous $\mathrm{cbs} = \Theta(n)$ belongs to the Tseitin contradiction on a bounded-degree expander [HuynhNordstrom12, GoosPitassi14], where an assignment can falsify a single vertex constraint and random sampling therefore fails -- see \(\mathrm{Ts}(G)\). Against $\mathrm{D} = \Theta(n)$ this makes the dense random formula an unbounded $\mathrm{D}$-vs-$\mathrm{cbs}$ separation rather than the $\Theta(1)$ ratio previously recorded. GoosPitassi14 HuynhNordstrom12 ABK21lifting
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(1)\) putative The $k$ variables of a falsified clause certify that clause, so $\mathrm{C} \le k = O(1)$ at every assignment. So $\mathrm{C} = \Theta(1)$ against $\mathrm{D} = \Theta(n)$: a falsified clause is trivially verifiable and yet, by the resolution-depth lower bound, very far from findable. This is the query-complexity shadow of TFNP.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(1)\) The witness is self-verifying (read the clause's $k$ variables and check), so the sampling algorithm can be made never-wrong by repeating until it succeeds: $\mathrm{R}_0 = \Theta(\mathrm{R}) = \Theta(1)$. Contrast \(\mathrm{ApproxHW}\), where there is no witness and $\mathrm{R}_0$ jumps to $\Theta(n)$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(1)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$; at least one query.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(1)\) At most $\mathrm{R}_0 = \Theta(1)$; at least $\mathrm{Q}$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(1)\) A lower bound on $\mathrm{Q} = \Theta(1)$.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(1)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(1)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(1)$.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(1)\) At most $\mathrm{D}_\mu = \Theta(1)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(1)\) A lower bound on $\mathrm{R} = \Theta(1)$, hence $\Theta(1)$. By $\mathrm{cbs} = O(\mathrm{CA})$ [ABK21lifting] this forces \(\mathrm{cbs}(S)\) $= \Theta(1)$ here too: both of these adversary-flavoured measures lower-bound the randomized cost, so neither can see the $\Theta(n)$ deterministic cost. Only \(\mathrm{DTsize}(f)\) and \(\mathrm{D}(f)\) do.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(1)\) Squeezed by $\mathrm{cjdeg} \le \mathrm{R} = \Theta(1)$ and $\mathrm{cjdeg} \ge 1$.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(1)\) putative Sample a clause and read each of its $k$ variables $O(1)$ times to beat the noise.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = \Theta(1)$.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(1)\) From $\mathrm{prt} \le 2\mathrm{R} = O(1)$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(1)\) From $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(1)\) The same $k$-variable certificate as $\mathrm{C}$: reading the variables of a falsified clause certifies that clause as a valid output.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(1)\) Between $1$ and $\mathrm{C} = \Theta(1)$: the short certificate is available at every assignment, which is exactly why $\mathrm{R}$ and $\mathrm{cbs}$ stay constant while $\mathrm{D} = \Theta(n)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(n)\) Only $\mathrm{Q}_E \le \mathrm{D} = O(n)$ is available. The Las Vegas value $\mathrm{Q}_0 = \Theta(1)$ does not bound it: certainty on every branch is what \(\mathrm{SEARCH}_n\) shows can cost the full $n$, and no lower bound better than $\Omega(1)$ is proved here.
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(n)\)· putative Decision-tree rank for $\mathrm{Search}(\varphi)$ is exactly the value of the Pudlak--Impagliazzo Prover--Delayer game, and a Delayer scoring $p$ points forces tree-like resolution size $\ge 2^{p}$. Random $\Delta$-dense $k$-CNFs admit a Delayer strategy scoring $\Omega(n)$ points, and $\mathrm{rank} \le \mathrm{D} = \Theta(n)$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, and both ends are $\Theta(1)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Adv}^{\pm}) = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(1)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0 = \Theta(1)$. A falsified clause is self-certifying, so demanding a never-invalid output costs nothing.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$, and at least $1$.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$.

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 13 in total.

Separations it witnesses

Cited as a witness by