12 Average-case complexity and the Hirahara program
This chapter formalizes average-case complexity through explicit finite ensembles and errorless heuristics, and follows Hirahara’s metacomplexity route toward excluding Impagliazzo’s Heuristica, that is, toward proving \(\mathsf{P} = \mathsf{NP}\) if and only if \(\mathsf{DistNP} \subseteq \mathsf{AvgP}\). Formalized so far: finite and dyadic ensembles, errorless heuristics and \(\mathsf{AvgP}\), Hirahara’s auxiliary-unary distribution with exact \(\mathsf{MINKT}\) probabilities, the dense-random-string extraction lemma, a finite Nisan–Wigderson reconstruction carried through list decoding to a Kolmogorov upper bound, conditional complexity and computational depth, symmetry of information as a named hypothesis, and a finite conditional theorem deriving \(\mathsf{P} = \mathsf{NP}\) from symmetry of information together with \(\mathsf{NP}\)-hardness of a conditional gap problem. The symmetry-of-information hypothesis is machine-relative and holds trivially for machines that describe nothing, so it has content only together with the other hypotheses of the theorems that use it (Definition 489). The reconstruction results assume a list-decodable code family with polynomial parameter bounds, a machine realizing the decoder, and, in the oracle form, an efficiently universal oracle machine; none of these is instantiated in the library. Samplable ensembles and \(\mathsf{DistNP}\) are not yet defined, so none of the headline equivalences is stated yet; they are the main open direction.
12.1 Ensembles and errorless heuristics
A finite ensemble assigns to each parameter \(n\) a nonempty finite seed space \(S_n\) (with decidable equality) and a sample map \(S_n \to \alpha \); the distribution at \(n\) is the pushforward of the uniform distribution on \(S_n\), with multiplicity. A dyadic ensemble is the special case \(S_n = \{ 0,1\} ^{\ell (n)}\), and its embedding into finite ensembles preserves every event probability. No sample map is called efficient until a machine realizes it (Definition 470). Samples need not have length \(n\).
If an event has probability \(p\) under the uniform distribution on a nonempty finite sample space, the probability that at least one of \(k\) independent uniform draws hits it is exactly \(1 - (1-p)^k\), and it is at least \(kp/(1+kp)\); in particular it is at least \(1/2\) whenever \(kp' \ge 1\) for some lower bound \(p' \le p\).
Count the complementary product event; then use \(1 - (1-p)^k \ge kp/(1+kp)\), which is at least \(1/2\) once \(kp \ge 1\).
A heuristic is a deterministic map from strings to the three answers accept, reject and fail; it is errorless for \(L\) if it never accepts outside \(L\) and never rejects inside \(L\). It runs in polynomial time when its answer, encoded as \([\mathrm{true}]\), \([\mathrm{false}]\) or the empty string respectively, is a function in \(\mathsf{FP}\). A distributional problem is a language with a finite ensemble of input strings. For \(\delta \colon \mathbb {N} \to \mathbb {Q}\), \(\mathsf{AvgP}_\delta \) consists of the distributional problems having a polynomial-time errorless heuristic whose failure probability on slice \(n\) is at most \(\delta (n)\) for every \(n\). \(\mathsf{AvgP} = \bigcap _{c \in \mathbb {N}} \mathsf{AvgP}_{\delta _c}\) with \(\delta _c(n) = 1/\max (1,n)^c\), which is \(n^{-c}\) for \(n \ge 1\) and \(1\) at \(n = 0\): for each \(c\) there is a possibly different polynomial-time errorless heuristic meeting \(\delta _c\). This is not the single-scheme formulation in which the heuristic receives \(1/\delta \) as an input; relating the two is part of Definition 471.
(a) If a Boolean function \(d\) satisfies \(d(x) = \mathrm{true}\) exactly when \(x\) lies in the language of a distributional problem, and the one-bit function \(x \mapsto [d(x)]\) is in \(\mathsf{FP}\), then the problem lies in \(\mathsf{AvgP}_\delta \) for every nonnegative \(\delta \) and in \(\mathsf{AvgP}\), whatever its ensemble. (b) An errorless heuristic for \(L\) (efficient or not) rejects with probability at least \(1 - \Pr [L] - \Pr [\mathrm{fail}]\) on every slice of every finite ensemble.
(a) Use the never-failing heuristic. (b) Errorlessness makes rejection exactly the complement of \(L\) minus failures.
An ensemble is polynomial-time samplable when a single machine computes its sample map from a polynomially long seed in time polynomial in \(n\), with closure under polynomial-time maps, pairing, padding, products and efficiently chosen mixtures. \(\mathsf{DistNP}\) consists of pairs \((L, D)\) with \(L \in \mathsf{NP}\) and \(D\) polynomial-time samplable. Levin-style domination is kept as a separate notion if needed.
Heuristics that may answer incorrectly on a set of bounded probability, \(\mathsf{Heur}_\delta \mathsf{P}\) and \(\mathsf{HeurP}\), the single-scheme versions of \(\mathsf{AvgP}\) and \(\mathsf{HeurP}\), randomized variants, and the standard amplification and inclusion lemmas.
If \(\mathsf{P} = \mathsf{NP}\), then \(\mathsf{DistNP} \subseteq \mathsf{AvgP}\).
\(\mathsf{P} = \mathsf{NP}\) if and only if \(\mathsf{DistNP} \subseteq \mathsf{AvgP}\). This is an open problem; the nontrivial direction is \(\mathsf{P} \neq \mathsf{NP} \Rightarrow \mathsf{DistNP} \not\subseteq \mathsf{AvgP}\). The conditional results of this chapter isolate hypotheses that would imply it.
One direction is Theorem 472.
12.2 MINKT under the auxiliary-unary distribution
Hirahara’s 2018 distribution \(D^u\): at parameter \(m {\gt} 0\), choose \(n \in \{ 0, \dots , m-1\} \) uniformly and \(x \in \{ 0,1\} ^n\) uniformly, and output \(\mathrm{pair}(x, 1^{m-n})\). The library realizes this with the seed space \(\{ 0, \dots , m-1\} \times \{ 0,1\} ^m\), keeping the first \(n\) bits of the \(m\)-bit string as \(x\), so the slice has \(m \cdot 2^m\) equiprobable seeds. The parameter \(m\) is the sum \(|x| + (m-n)\) of the component lengths, not the length of the encoded pair. The slice \(m = 0\) is totalized as the point \(\mathrm{pair}(\epsilon , \epsilon )\) (a single seed), a library convention.
For \(0 {\lt} m\) and \(|x| = n {\lt} m\), \(D^u_m\) gives \(\mathrm{pair}(x, 1^{m-n})\) mass \(1/(m \cdot 2^n)\). For every machine \(U\) and threshold \(r\),
Condition on the split length; retaining the \(n\)-bit prefix of a uniform \(m\)-bit seed preserves prefix-event probabilities. Then apply finite incompressibility at each length.
For every \(m {\gt} 0\), every machine \(U\), every threshold \(r\), and every errorless heuristic \(A\) for \(\mathsf{MINKT}(U, r)\) (no efficiency is assumed),
Thus, when the average and the failure probability are small, an errorless heuristic must certify, by rejecting, a dense set of strings of high time-bounded complexity.
12.3 Nisan–Wigderson reconstruction
A generator is any map \(G \colon \{ 0,1\} ^d \to \{ 0,1\} ^m\) (no efficiency is built in). A test \(T \subseteq \{ 0,1\} ^m\) has distinguishing advantage \(|\Pr _s[G(s) \in T] - \Pr _y[y \in T]|\). Relative to a machine \(M\), clock \(t\) and threshold \(r\): \(T\) is a random test if every \(y \in T\) has \(C^t_M(y) \ge r\); \(T\) is \(\delta \)-dense if \(\Pr _y[y \in T] \ge \delta \); and \(G\) has low complexity if every output satisfies \(C^t_M(G(s)) {\lt} r\).
(a) A \(\delta \)-dense random test has advantage at least \(\delta \) against every low-complexity generator. (b) If \(m {\gt} 0\) and the advantage is at least \(\delta \), then for \(T\) or its complement there is \(i {\lt} m\) such that the Yao hybrid whose first \(i+1\) coordinates come from \(G\) (the rest uniform) is accepted with probability at least \(\delta /m\) more than the hybrid whose first \(i\) coordinates do. (c) Over any nonempty finite background space, the predictor that outputs a uniform candidate bit when the test accepts and its complement otherwise succeeds with probability exactly \(1/2\) plus the acceptance gain from substituting the true bit for the candidate.
(a) No generator output lies in \(T\). (b) Telescope the hybrid gaps and average. (c) Expand the two candidate fibers.
An NW design is an ordered family \(S_1, \dots , S_m\) of \(\ell \)-element subsets of \([d]\), each enumerated injectively. It has overlap budget \(b\) if for every \(i\), \(\sum _{j{\lt}i} 2^{|S_i \cap S_j|} + (m - i) \le b\) (Hirahara’s weak-design cost). For \(f \colon \{ 0,1\} ^\ell \to \{ 0,1\} \) the generator is \(\mathrm{NW}^f(s) = (f(s|_{S_1}), \dots , f(s|_{S_m}))\).
Let \(m {\gt} 0\), let \(\mathrm{NW}^f\) have low complexity, and let \(T\) be a \(\delta \)-dense random test for the same machine, clock and threshold, and let the design have overlap budget \(b\). (a) There are a polarity, a coordinate \(i\) and fixed advice whose predictor agrees with \(f\) on at least a \(1/2 + \delta /m\) fraction of inputs, and whose stored data (predecessor tables, later output bits, outside seed bits and the candidate bit, excluding codec overhead) has at most \(b + (d - \ell ) + 1\) bits. (b) If \(\delta {\gt} 0\), exact checking of \(\lceil 2m/\delta \rceil \) uniformly sampled trials finds a certificate with agreement at least \(1/2 + \delta /(2m)\) with probability at least \(1/2\), and every returned certificate satisfies the same payload bound.
Hybrid and prediction steps give the predictor; each predecessor block depends only on its intersection with \(S_i\) and is hardwired by a table of \(2^{|S_i \cap S_j|}\) entries; fiber averaging fixes the outside seed and later tail. A reverse-Markov bound gives single-trial success at least \(\delta /(2m)\), and repetition gives (b).
Assume: a list-code family that is list-decodable at inverse accuracy (up to relative distance \(1/2 - 1/q\) at every inverse accuracy \(q \ge 2\)) and has polynomial parameter bounds; \(m {\gt} 0\) and \(D {\gt} 0\); an NW design over the coordinates of the code at inverse accuracy \(q = 2mD\) with overlap budget \(b\) and seed length \(d\); a message \(\mu \) such that \(\mathrm{NW}^{\mathrm{Enc}(\mu )}\) has low complexity for \((M, t, r)\); and a \((1/D)\)-dense random test \(T\) for \((M, t, r)\). Let \(B = 1 + \lceil \log _2 m\rceil + (b + (d - \ell ) + 1) + \lceil \log _2 (C_L (q+1)^{e_L}) \rceil \), where \(\ell \) is the coordinate length and \(C_L (q+1)^{e_L}\) the list-size bound. In each case below, checked sampling with \(\lceil 2mD \rceil \) trials at agreement threshold \(1/2 + 1/(2mD)\) succeeds with probability at least \(1/2\), and the stated bound on \(\mu \) holds for every returned certificate. (a) If a machine \(\mathrm{Dec}\) with monotone clock \(t_{\mathrm{dec}}\) realizes the indexed-message decoder for this design, code and test, then \(C^{t_{\mathrm{dec}}(B)}_{\mathrm{Dec}}(\mu ) \le B\); if moreover \(U\) is an efficiently universal machine, there are constants \(c, a, k\) with \(C^{a(B + t_{\mathrm{dec}}(B) + 1)^k}_U(\mu ) \le B + c\). (b) If instead one oracle machine \(\mathrm{Dec}\) with monotone clock \(t_{\mathrm{dec}}\) realizes the decoder for this design and code and every finite test given as a membership oracle, the same two bounds hold for oracle complexity relative to the membership oracle of \(T\), now with \(U\) an efficiently universal oracle machine. Moreover the returned \(c, a, k\) satisfy a transfer law for every finite test \(T'\) and message \(\mu '\): if some description of length at most \(b'\) decodes to \(\mu '\) under \(T'\), then \(C^{a(b' + t_{\mathrm{dec}}(b') + 1)^k,\, T'}_U(\mu ') \le b' + c\). (c) If a single decoder machine serves every parameter choice of the family, reading the design and test from an explicit encoding \(e\) framed with the description (or, in the oracle form, the numeric parameters and design from a canonical encoding \(e\), with the test as an oracle), then for efficiently universal \(U\) one triple \(c, a, k\), chosen before all parameters, designs, tests and messages, gives the bound of (a) (respectively of (b)) on every instance satisfying the assumptions above, with \(B\) replaced by \(2|e| + 2 + B\).
List-decode the predictor stored in the certificate, append a \(\lceil \log _2 L \rceil \)-bit index of the correct candidate, the polarity bit and the coordinate, and transfer the resulting description through the universal compiler. In (a) and the ordinary form of (c) the universality hypothesis can be discharged by \(\mathtt{utmTM}\); the code family, the decoder realization and (in (b) and the oracle form of (c)) the universal oracle machine remain hypotheses.
For every \(m\), \(\ell \) and \(\rho {\gt} 1\) there is a polynomial-time computable NW design with \(\sum _{j{\lt}i} 2^{|S_i \cap S_j|} \le \rho (m-1)\) for every \(i\) and seed length \(d = \lceil \ell /\ln \rho \rceil \cdot \ell \) (Raz–Reingold–Vadhan weak designs); its overlap budget is at most \(\rho (m-1) + m\).
There is an oracle machine that is efficiently universal for oracle machines, analogous to \(\mathtt{utmTM}\).
Instantiating Theorem 481 with an explicit code family, explicit weak designs and concrete universal machines, and realizing the design parser, sampler, checker and decoder by machines, yields Hirahara’s 2018 search step: a dense random test gives a randomized algorithm that on input \((x, 1^t)\) finds a description of \(x\) whose length exceeds \(C^t(x)\) by \(O(\sqrt{C^t(x)})\) up to logarithmic factors, running within a polynomially larger clock. The exact finite parameter theorem is proved first and the asymptotic loss derived from it.
12.4 Conditional complexity, depth, and symmetry of information
For an oracle machine \(N\) and Boolean oracle \(A\), \(C^{t,A}_N(x)\) is the minimum length of a program on which \(N^A\) produces \(x\) within \(t\) steps (\(\infty \) if there is none). The random-access oracle of a string \(y\) answers canonical tagged queries “bit \(i\) of \(y\)” and “is \(i {\lt} |y|\)” (malformed and out-of-range queries answer false), so it determines both the contents and the length of \(y\). Conditional complexity is \(C^t_N(x \mid y) = C^{t, \mathrm{oracle}(y)}_N(x)\). Other conditioning conventions (sequential input, paper-specific evaluators) are not identified with this one.
Fix an oracle machine \(N\) and an oracle \(A\). (a) If \(t \le t'\) then \(C^{t',A}_N(x) \le C^{t,A}_N(x)\). (b) For an ordinary machine \(M\) viewed as an oracle machine that never queries, \(C^{t,A}_M(x) = C^t_M(x)\) for every oracle \(A\). (c) Suppose \(N\) simulates an oracle machine \(N'\) in time \(\tau \) under a compiler \(c\) (bounded productions transfer for every oracle; bounded halting is not required), with \(|c(p)| \le |p| + C\) and \(\tau (p, t) \le a (|p| + t + 1)^e\) for all \(p, t\). Then there are \(a', e'\), chosen once for all oracles, such that for every oracle \(A\), string \(x\), clock \(t\) and bound \(b\), \(C^{t,A}_{N'}(x) \le b\) implies \(C^{a'(b + t + 1)^{e'},A}_N(x) \le b + C\).
(a) A program producing \(x\) within \(t\) steps also does within \(t'\). (b) The embedded machine’s runs do not depend on the oracle. (c) Compile a witnessing program of length at most \(b\) and bound the simulation clock using that length.
\(\mathrm{cd}^{s,t}_M(x) = C^s_M(x) - C^t_M(x)\) and \(\mathrm{cd}^{s}_M(x) = C^s_M(x) - C_M(x)\), where the difference is \(\infty \) if either term is \(\infty \) and truncated natural subtraction otherwise. Both are defined for all clocks; the second subtraction is always exact, and the first is exact when \(s \le t\) (then \(C^t_M(x) \le C^s_M(x)\)), the case in which its laws are stated.
Suppose a compiler \(\kappa \) turns every program for \(y\) (on machine \(M_1\), clock \(t_1\), length at most \(b_1\)) and every conditional program for \(x\) given \(y\) (on \(N\), clock \(t_2\), length at most \(b_2\)) into a program on which \(M\) produces \(\mathrm{pair}(x, y)\) within \(t\) steps, with \(|\kappa (p, q)| \le |p| + |q| + c\) for all such \(p, q\). If \(C^{t_1}_{M_1}(y) \le b_1\) and \(C^{t_2}_N(x \mid y) \le b_2\) (both finite), then \(C^t_M(\mathrm{pair}(x,y)) \le C^{t_2}_N(x \mid y) + C^{t_1}_{M_1}(y) + c\).
Compile attaining programs.
For an ordinary machine \(M\), a conditional oracle machine \(N\), a clock transformation \(\kappa \) and a loss \(\lambda \), \(\mathrm{SoI}(M, N, \kappa , \lambda )\) asserts, for all \(x, y, t\) with \(|x| + |y| \le t\),
The polynomial package asks for some \(\kappa \) with \(\kappa (t) \ge t\) and \(\kappa (t) \le a(t+1)^k\) for all \(t\), and \(\lambda (t) = \lfloor \log _2 \kappa (t) \rfloor + c\) for a constant \(c\). The inequality holds trivially wherever \(C^t_M(\mathrm{pair}(x,y)) = \infty \), in particular whenever \(t\) is too small for \(M\) to print \(\mathrm{pair}(x,y)\), and everywhere for a machine \(M\) that describes nothing; so SoI has content only for machines constrained by other hypotheses. (An earlier version also required \(C^t_M(\mathrm{pair}(x,y)) {\lt} \infty \) whenever \(|x| + |y| \le t\). That is impossible, since a run of \(t\) steps writes at most \(t\) output bits while \(|\mathrm{pair}(x,y)| = 2|x| + 2 + |y| {\gt} t\) at \(t = |x| + |y|\), and the requirement was removed.) SoI is a hypothesis; nothing in the library asserts it.
(a) Assume \(\mathrm{SoI}(M, N, \kappa , \lambda )\), \(|x| + |y| \le t\), \(t' \le \kappa (t)\), and a paired upper bound \(C^t_M(\mathrm{pair}(x,y)) \le C^{t''}_{N'}(x \mid y) + C^{t'}_M(y) + u\) for some oracle machine \(N'\) and clock \(t''\). Then
(b) In particular the same conclusion holds with \(u = c\) when the paired upper bound is replaced by the hypotheses of Theorem 488 for joint machine \(M\) at clock \(t\), condition machine \(M\) at clock \(t'\) and conditional machine \(N'\) at clock \(t''\). Neither part assumes \(C^t_M(\mathrm{pair}(x,y)) {\lt} \infty \): when \(C^{\kappa (t)}_M(y) = \infty \), the depth term, and with it the right-hand side, is \(\infty \).
If \(C^{\kappa (t)}_M(y) = \infty \) the conclusion is trivial. Otherwise substitute the upper bound into the SoI inequality and cancel \(C^{\kappa (t)}_M(y)\) using the exact additive decomposition of depth; for (b), obtain the upper bound from Theorem 488.
There are an efficiently universal ordinary machine and an efficiently universal conditional oracle machine satisfying the condition-first composition contract of Theorem 488 with a constant additive loss and a polynomial clock, on all instances with \(|x| + |y| \le t\).
If \(\mathsf{DistNP} \subseteq \mathsf{AvgP}\), then the polynomial time-bounded SoI holds for the evaluators of Theorem 491 (Hirahara 2022).
Split into a dense-string module, a language-compression module and clock accounting.
12.5 Gap problems and the conditional collapse
Hirahara 2022, Definition 3.3: for a widening clock \(\tau (n, t) \ge t\), the promise on canonical \((x, 1^t, 1^s)\) with yes side \(C^t_U(x) \le s\) and no side \(C^{\tau }_U(x) {\gt} s + \lfloor \log _2 \tau \rfloor \), where \(\tau = \tau (|x|, t)\). An estimator \(B\) satisfies Fact 3.4’s sandwich if \(B(x, 1^t) \le C^t_U(x)\) and \(C^{\tau }_U(x) \le B(x, 1^t) + \lfloor \log _2 \tau \rfloor \) on every instance \((x, 1^t)\); it satisfies it on a set \(E\) of instances if these hold for every instance in \(E\).
Fix a machine \(U\) and a widening clock \(\tau \). (a) If an estimator satisfies the sandwich on every instance and its threshold language \(\{ (x,1^t,1^s) : B(x,1^t) \le s\} \) is in \(\mathsf{P}\), then logarithmic \(\mathsf{GapMINKT}\) is in \(\mathsf{PromiseP}\). (b) Conversely, let a Boolean function \(d\) solve logarithmic \(\mathsf{GapMINKT}\) (accepting yes instances and rejecting no instances) with \(x \mapsto [d(x)]\) in \(\mathsf{FP}\). The unary threshold sweep built from \(d\) is in \(\mathsf{FP}\), and its output length satisfies the sandwich on every set of instances on which \(C^t_U(x) {\lt} \infty \); in particular on the paper’s domain \(|x| \le t\) provided \(C^t_U(x) {\lt} \infty \) for every such instance. If \(U\) is efficiently universal, no finiteness proviso is needed on a printer-clock domain instead: there are \(a, k\) depending only on \(U\) such that, for every widening clock \(\tau \) and every such \(d\), the sweep satisfies the sandwich on every instance with \(a(2|x|+3)^k \le t\).
(a) Threshold the estimator. (b) Scan \(s = 0, \dots , t\) and return the least accepted threshold, whose sandwich needs only \(C^t_U(x) {\lt} \infty \) (then \(C^t_U(x) \le t\)); efficient universality supplies that finiteness above the printer clock.
Hirahara 2022, Definitions 6.1 and 6.5. Fix an ordinary machine \(M\) and a conditional oracle machine \(N\). For a widening trivariate clock \(\tau (|x|, |y|, t) \ge t\), the promise \(\mathsf{GapMINcKT}\) on canonical \((x, y, 1^t, 1^s)\) has yes side \(C^t_N(x \mid y) + \mathrm{cd}^{t,\tau }_M(y) \le s\) and no side \(C^{\tau }_N(x \mid y) {\gt} s + \lfloor \log _2 \tau \rfloor \). The multiplicative version with factor \(\phi \colon \mathbb {N} \to \mathbb {N}\), \(\phi \ge 1\), has the same yes side and no side \(C^{\tau }_N(x \mid y) {\gt} \phi (|x|) \cdot s + \lfloor \log _2 \tau \rfloor \). A conditional estimator \(B\) satisfies Proposition 6.2’s sandwich if \(B(x, y, 1^t) \le C^t_N(x \mid y) + \mathrm{cd}^{t,\tau }_M(y)\) and \(C^{\tau }_N(x \mid y) \le B(x, y, 1^t) + \lfloor \log _2 \tau \rfloor \) on every instance.
Fix \(M\), \(N\) and a widening clock \(\tau \). (a) If an estimator \(B\) satisfies \(B \le C^t_N(x \mid y) + \mathrm{cd}^{t,\tau }_M(y)\) and \(C^{\tau }_N(x \mid y) \le B + \lfloor \log _2 \tau \rfloor \) on every instance and its threshold language \(\{ (x, y, 1^t, 1^s) : B(x, y, 1^t) \le s\} \) is in \(\mathsf{P}\), then \(\mathsf{GapMINcKT} \in \mathsf{PromiseP}\). (b) Promise-\(\mathsf{NP}\)-hardness of the multiplicative problem with factor \(\phi \ge 1\) implies promise-\(\mathsf{NP}\)-hardness of the additive one with the same clock. (c) Consequently, multiplicative hardness together with such an estimator implies \(\mathsf{P} = \mathsf{NP}\). The second half of the sandwich forces \(C^{\tau }_N(x \mid y) {\lt} \infty \) on every instance, a genuine restriction on \(\tau \) and \(N\).
(a) Threshold the estimator. (b) The identity is a promise reduction, since the multiplicative no side is contained in the additive one. (c) Combine with Theorem 426.
For every machine \(U\) and every function \(p \colon \mathbb {N} \to \mathbb {N}\), take the ordinary parameters of the iterated plan, whose transformed clock is \(\tau (n, t) = p(t)\) regardless of output length. No estimator satisfies Fact 3.4’s sandwich for \(U\) and \(\tau \) on every instance: at source time \(0\), no machine prints a string of length \(p(0) + 1\) within \(p(0)\) steps. The estimator hypotheses below are therefore restricted to the plan’s own queries.
The output cell at position \(p(0) + 1\) is untouched by any run of at most \(p(0)\) steps, so it stays blank.
Fix an ordinary machine \(M\), a conditional oracle machine \(N\), a monotone primitive clock \(p\) with \(p(t) \ge t\) and \(p(t) \le a(t+1)^k\) for all \(t\), and constants \(c_{\mathrm{SoI}}, c_{\mathrm{pair}}\). The plan queries the ordinary estimator on \((\mathrm{pair}(x,y), 1^{p(t')})\) and on \((y, 1^{p^3(t')})\), where \(t' = \max (t, |x|+|y|)\). From \(p\), \(c_{\mathrm{SoI}}\) and \(c_{\mathrm{pair}}\) the library builds an explicit slack-amplified clock \(\tau (|x|, |y|, t) = 2^{e}\, (p^4(t+|x|+|y|)+1) (t+|x|+|y|+1)\), whose exponent \(e\) collects the logarithmic losses and the two constants, and proves it widening and polynomially bounded. Assume: (i) a pair-composition hypothesis: a compiler producing \(\mathrm{pair}(x,y)\) on \(M\) within \(p(t')\) steps from a program for \(y\) on \(M\) and a conditional program for \(x\) given \(y\) on \(N\) (each running within \(t\) steps), with length loss \(c_{\mathrm{pair}}\) and program budgets that contain \(C^t_M(y)\) and \(C^t_N(x \mid y)\) whenever these minima are finite; (ii) \(\mathrm{SoI}(M, N, p, \lambda )\) with \(\lambda (t) = \lfloor \log _2 p(t) \rfloor + c_{\mathrm{SoI}}\); (iii) promise-\(\mathsf{NP}\)-hardness of the multiplicative \(\mathsf{GapMINcKT}\) for \(M\), \(N\) (factor \(\phi \ge 1\)) at the slack-amplified clock \(\tau \); and (iv) either an ordinary estimator satisfying Fact 3.4’s sandwich for \(M\) at the ordinary clock \((n, t) \mapsto p(t)\) on the plan’s queries, whose induced two-query threshold language is in \(\mathsf{P}\) (or which has an \(\mathsf{FP}\) implementation whose output length is the estimate, together with \(\mathsf{FP}\) query and ruler builders for the plan), or a Boolean function \(d\) with \(x \mapsto [d(x)]\) in \(\mathsf{FP}\) solving logarithmic \(\mathsf{GapMINKT}\) for \(M\) at that clock, together with those \(\mathsf{FP}\) builders and the premise that every query of the plan has finite complexity on \(M\). Then \(\mathsf{P} = \mathsf{NP}\). Equivalently, if \(\mathsf{P} \neq \mathsf{NP}\), then (i), (iii) and each form of (iv) rule out (ii).
Query the ordinary estimator on \(\mathrm{pair}(x,y)\) at clock \(p\) and on \(y\) at clock \(p^{3}\), subtract with an explicit rounding correction, and use SoI and the upper chain to verify both halves of the conditional sandwich (the cancellation of Theorem 490 is redone inline from inequality (ii) and the depth decomposition), then apply Theorem 496(c); in the solver form, the threshold sweep of Theorem 494(b) supplies the estimator. The final clock is \(p^{4}\) amplified by a power-of-two slack that pays all logarithmic and additive losses and is proved polynomially bounded. When \(C^t_M(y)\) or \(C^t_N(x \mid y)\) is infinite, the upper chain holds trivially, so hypothesis (i) needs no finiteness.
An earlier formalization demanded finite minima at every instance, an estimator correct on every instance, and (inside SoI) a finite joint complexity at every clock \(t \ge |x| + |y|\). All three are unsatisfiable (no machine prints a nonempty string in zero steps, Lemma 497, and the output-length bound of Definition 489), and the current statements avoid all three. No instance of hypothesis (i) for concrete universal machines is constructed yet.
If, for the evaluators of Theorem 491 and every admissible polynomial clock, the multiplicative conditional gap problem is \(\mathsf{NP}\)-hard under the exact reductions of the paper, then \(\mathsf{DistNP} \subseteq \mathsf{AvgP}\) implies \(\mathsf{P} = \mathsf{NP}\). Published \(\mathsf{NP}\)-hardness reaches only a sublinear-time regime, so this hypothesis is open.
\(\mathsf{DistNP} \subseteq \mathsf{AvgP}\) gives SoI and, through the paper’s worst-case to average-case step, an efficient logarithmic \(\mathsf{GapMINKT}\) solver; apply Theorem 498.
12.6 Further theorems of the program
(a) If \((\mathsf{MINKT}[r], D^u)\) is easy on average in the randomized errorless sense of the paper, then \(\mathsf{GapMINKT}\) with description loss of order \(\sqrt{s}\) (up to logarithmic factors) and polynomial clock blow-up has a zero-error randomized worst-case search algorithm. (b) Hence, if that gap problem is \(\mathsf{NP}\)-hard under the paper’s randomized reductions, average-case easiness of \(\mathsf{DistNP}\) in the paper’s randomized sense implies worst-case easiness of \(\mathsf{NP}\) in the corresponding randomized sense.
The heuristic’s rejections form a dense random test; NW reconstruction turns it into a description search; search to decision gives the gap solver.
At the randomized complexity level of the paper, average-case easiness of \(\mathsf{MCSP}[2^{\varepsilon n}]\) on uniform truth tables is equivalent to worst-case solvability of a very-large-gap \(\mathsf{MCSP}\) approximation problem, with arity \(n\) and input length \(N = 2^n\) kept distinct. This is not a statement about exact \(\mathsf{MCSP}\).
If \(\mathsf{UP} \not\subseteq \mathsf{DTIME}(2^{O(n/\log n)})\), then \(\mathsf{DistNP} \not\subseteq \mathsf{AvgP}\). The class \(\mathsf{UP}\) and universal heuristic schemes are not yet defined.
Partial \(\mathsf{MCSP}\) and the partial variants \(\mathsf{MINKT}^{*}\) and \(\mathsf{MKTP}^{*}\) are \(\mathsf{NP}\)-hard under randomized reductions (Hirahara 2022, NP-Hardness of Learning Programs and Partial MCSP). The extension from partial to total problems is isolated as an open hypothesis, not assumed.
Distributional Kolmogorov complexity, approximation-preserving padding, and the Meta-Complexity Padding Conjecture of Hirahara 2023 stated as an explicit hypothesis, together with its conditional characterization of one-way functions. It is never used as an unconditional theorem.
12.7 Open directions
Relativization, oracle-independence, natural-reduction and black-box-reduction barriers for this program should be recorded as formal oracle implications or countermodels once the oracle layer supports them. They constrain which proof interfaces can work and do not license assuming a nonrelativizing result.