\(\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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{C}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = n\) against \(\mathrm{C}^1(f) = \Theta(1)\)
-
\(\mathrm{psD}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{psD}(S) = \Omega(n^{1/3})\) against \(\mathrm{C}_{\min}(f) = \Theta(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{C}^1(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = n\) against \(\mathrm{C}_{\min}(f) = \Theta(1)\)
-
\(\mathrm{psD}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{0}(f_n) = O(1)\)from \(\mathrm{psD}(S) = \Omega(n^{1/3})\) against \(\mathrm{R}_{0}(f) = \Theta(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{C}_{\min}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{0}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = n\) against \(\mathrm{R}_{0}(f) = \Theta(1)\)
-
\(\mathrm{psD}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{psD}(S) = \Omega(n^{1/3})\) against \(\mathrm{C}^1(f) = \Theta(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{0}(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{R}_{0}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{0}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = n\) against \(\mathrm{Q}_{0}(f) = \Theta(1)\)
-
\(\mathrm{rank}(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{0}(f_n) = O(1)\)from \(\mathrm{rank}(f) = \Theta(n)\) against \(\mathrm{Q}_{0}(f) = \Theta(1)\)
-
\(\mathrm{psD}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{Q}_{0}(f_n) = O(1)\)from \(\mathrm{psD}(S) = \Omega(n^{1/3})\) against \(\mathrm{Q}_{0}(f) = \Theta(1)\)
Separations it witnesses
-
Unbounded, for a total relation: $\mathrm{R}=O(1)$ but $\mathrm{D}=\Theta(n)$. Unlike \(\mathrm{Find1}_{\ge n/2}\) no promise is needed -- the hardness is that a deterministic algorithm must name a specific falsified clause, which is a resolution refutation in disguise.
Cited as a witness by
-
\(\mathrm{psD}(\mathrm{SearchCNF}) = \Omega(n^{1/3}) \text{ for random } k\text{-CNFs}\)
-
\(\mathrm{D}(\mathrm{SearchCNF}) = \Theta(n) \to \infty, \qquad \mathrm{cbs}(\mathrm{SearchCNF}) = \Theta(1)\)