Introduction
TFNP is the class of total search problems in NP, those for which solutions always exist and can be efficiently verified. TFNP is studied through its subclasses, each capturing a principle of totality . The smallest, FP, consists of the total problems solvable in polynomial time; every other subclass is defined by reduction to a canonical complete problem. Four well-studied classes are PPP, PWPP, PLS and PPAD. In PPP, for the pigeonhole principle [60 ] , the complete problem is to find a collision C ( x ) = C ( x ′ ) C(x)=C(x') C ( x ) = C ( x ′ ) C : [ 2 n ] → [ 2 n − 1 ] C:[2^n]\to[2^n-1] C : [ 2 n ] → [ 2 n − 1 ] weak pigeonhole principle [Jeř16], has the same complete problem but now, C : [ 2 n ] → [ 2 n − 1 ] C:[2^n]\to[2^{n-1}] C : [ 2 n ] → [ 2 n − 1 ] local search [43 ] : given a monotonically increasing function f : [ 2 n ] → [ 2 n ] f:[2^n]\to[2^n] f : [ 2 n ] → [ 2 n ] Nash equilibrium in bimatrix games [23 , 16 ] , although the original complete problem rests on a parity argument on directed graphs [60 ] . Formal definitions are in Section A.
TFNP hardness and cryptography. The theory of total search problems studies under what conditions TFNP subclasses are hard , or hard on average , as evidence for the computational intractability of total problems such as finding a Nash equilibrium. It is unlikely that NP-hardness alone will suffice: if TFNP contains an NP-hard problem, then NP = co-NP [59 ] . Over the past decade, researchers have studied cryptographic assumptions as a source of hardness for TFNP. Conversely, this maps to studying which total problems are hard in each of Impagliazzo’s “worlds” [37 ] . All cryptographic assumptions trivially imply the hardness of NP, and are believed to in fact imply more, e.g. hardness of some NP-intermediate classes. TFNP is a candidate for such a class.
The main line of work in this field has centered on proving UEoPL average-case hardness from strong cryptographic assumptions, i.e. in the higher worlds. UEoPL [27 ] is the lowest of the standard TFNP subclasses: it is contained in every class mentioned so far. Average-case hardness of UEoPL was first shown from indistinguishability obfuscation [13 ] (see also [5 ] ), that is, in Obfustopia, and later from public-key assumptions [31 , 55 , 50 , 41 BCH+22, 46 , 18 ] , that is, in Cryptomania.
In Minicrypt, the world where one-way functions (OWFs) exist but no public-key assumptions hold, TFNP itself is hard on average, either non-uniformly or under an additional derandomization assumption [35 ] . However, no problem in any of its standard subclasses is known to be hard in Minicrypt, not even in the worst case, whereas the stronger assumptions above give average-case hardness of UEoPL, the most structured class of all. Barriers against restricted black-box constructions suggest that OWFs may not suffice [RSS21, HKKS20, FGH+24].
The random oracle model. Is public-key cryptography necessary? A natural starting point for this question is the random oracle model (ROM) [14 ] , a setting often studied in cryptography when OWFs appear to be insufficient. Briefly, in the ROM, all parties (instance samplers, solvers, verifiers, etc.) have query-access to a randomly sampled function (see § 3.1 for a complete definition). A random function is itself one-way, so morally, the ROM “contains” Minicrypt. On the other hand, public-key cryptography cannot be built in the ROM in a black-box way [39 ] (and hence not from OWFs either). The world with a random oracle, which we call Romantica ♡, therefore sits roughly between Minicrypt and Cryptomania.1 [7 ] . If moreover #SAT is hard, then UEoPL, and hence every class above it, is hard on average in Romantica [19 BCH+22] . Whether any other subclass, in particular PPAD, UEoPL, PPA or EoPL, is hard in Romantica without additional assumptions has been open until now.
Our results
We resolve, for every standard TFNP subclass, whether it is hard on average in Romantica; Figure 1 summarizes the results. Overall we show: PPAD is hard on average, and hence so is EoPL = PPAD ∩ \cap ∩ black-box sense: a solver making polynomially many oracle-queries exists. Finally, we initiate the study of separations between TFNP subclasses in Romantica: neither PWPP nor PPA reduces to PLS under public-coin reductions. We now state these results more fully in turn.
Figure 1. Separations, inclusions, and equivalences in the ROM (Romantica ), red arrows are average-case separations and are the results of this paper. Average-case hardness is equivalent to average-case separation from FP.
Theorem (Theorem 1, Informal). PPAD is hard on average in the random oracle model. The hard distribution is efficiently samplable, and any solver making polynomially many oracle queries finds a solution with negligible probability.
The proof modifies the Yamakawa–Zhandry hypergraph [YZ24], originally used to separate quantum from classical query algorithms, so that the search problem becomes total while remaining hard; see § 3.2 . Theorem 1 and the known hardness of PLS [7 ] imply, via a simple or-composition, average-case hardness of PLS ∩ \cap ∩ [25 , 28 ] , the class of problems reducible to finding the end of a potential line [27 ] .
Corollary (Corollary 14, Informal). PPAD ∩ \cap ∩
Since PPA ⊇ \supseteq ⊇ Figure 1 except UEoPL is now known to be hard on average in Romantica. The remaining question is whether UEoPL, the lowest widely studied non-trivial TFNP subclass (and in particular a subclass of EoPL = PPAD ∩ \cap ∩ negative , highlighting a key structural difference between UEoPL and EoPL with respect to random oracles:
Theorem (Theorem 15, Informal). In the random oracle model, given any poly-time samplable distribution over instances of UEoPL, there exists an algorithm that finds solutions with probability ≥ 2 / 3 \ge2/3 ≥ 2/3
Theorem 15 concerns query efficiency, not time efficiency: the solver makes polynomially many oracle queries, but its computation need not be efficient. Indeed, as mentioned previously, UEoPL is known to be hard on average in Romantica with the additional assumption that #SAT is hard on average [19 ] . This suggests that in Romantica, a computational assumption is necessary (and sufficient) to establish UEoPL-hardness. The proof rests on a recent dichotomy lemma [3 ] ; see § 3.3 .
To our knowledge, all previous average-case hardness results for PPAD and EoPL establish hardness of UEoPL and inherit it by containment. In Romantica, Theorem 15 rules out this route, so Theorem 1 is the first PPAD hardness result that does not go through UEoPL.
Finally, we also initiate the study of separations between different TFNP subclasses in Romantica: PWPP and PPA, the class for parity arguments on undirected graphs [60 ] , cannot be reduced to PLS under public reductions , whose only randomness is the random oracle itself:
Theorem (Theorem 36, Informal). In the random oracle model, there is no efficient public reduction from a PWPP-complete problem to a PLS-complete problem.
Theorem (Theorem 39, Informal). In the random oracle model, there is no efficient public reduction from a PPA-complete problem to a PLS-complete problem.
Our proofs reduce these separations to proof-complexity lower bounds; see § 3.4 . This step relies on the reductions being public. The oracle is visible to the solver of the target problem, so a public reduction hides nothing from the solver, who may choose which solution to return with full knowledge of the reduction. A private-coin reduction may in addition toss coins hidden from the solver, which may help the reduction. Separating TFNP subclasses in Romantica under private-coin reductions remains open, as do separations between other pairs of subclasses.
A proof-complexity perspective. Black-box TFNP subclasses correspond exactly to proof systems [BIK+96, BFI23, GHJ+22], and passing to the random oracle model, a reduction may now fail on a small fraction of oracles. From the proof side, this corresponds to proofs that are approximately sound , meaning that they are correct on all but a small fraction of uniformly random inputs. In particular, a ROM reduction to PLS is a narrow random resolution refutation with respect to a locally samplable distribution (see § 6 ) so Theorems 36 and 39 are lower bounds for approximately sound proofs. We note that for stronger proof systems such as bounded-depth Frege systems, a recurring issue is how to define approximate soundness in a meaningful way. Note that for any Frege proof (even of low depth) of a tautology, every line in the proof is semantically equivalent to “1” so any useful notion of an approximate proof must incorporate the local nature of the rules in order to avoid this pitfall.
More generally lower bounds for approximate proofs have many applications outside of cryptography: (i) they underlie lower bounds on the extension complexity of LP and SDP relaxations for approximating NP-hard problems; (ii) they are the object of study in random resolution, with applications to theories of approximate counting; (iii) they are exactly the missing ingredient in the Razborov–Smolensky approach to A C 0 [ p ] \mathrm{AC}^{0}[p] AC 0 [ p ] § 2.2 .
Related work
Average-case TFNP and cryptography
Unconditional hardness of TFNP subclasses in Romantica. It is not hard to see that the existence of collision-resistant hash functions (CRHFs) implies the average-case hardness of the weak pigeonhole principle. Hence, the average-case hardness of PPP and PWPP in the ROM follows from the fact that CRHFs exist in the ROM. Apart from this, the only TFNP-subclass that is known to be hard (and in fact, average-case hard) prior to our work is PLS [7 ] . Their result is obtained by combining the construction of proofs of work in the ROM [22 ] and ideas from the Fiat–Shamir heuristics.
On the pursuit of PPAD hardness. Showing hardness of PPAD in the ROM has been a long-standing open problem. Prior to our work, the best known results were conditional hardness for UEoPL (and hence PPAD) which, in addition to the random oracle, involved a complexity-theoretic assumption like #SAT being hard on average [19 Theorem 2] , or hardness of EoPL from the iterated squaring assumption [20 ] . As mentioned previously, this does not contradict our new UEoPL upper-bound since Theorem 15 only proves a query -complexity upper bound (i.e., a black-box upper-bound); the algorithm we give is not computationally efficient in the white-box sense. Theorem 1 is proved in a very different way compared to previous conditional hardness results. [19 Theorem 2] is proved by applying Fiat-Shamir to the sum-check protocol for # S A T \#\mathrm{SAT} # SAT [55 , 41 BCH+22, 46 , 18 ] ). It remains an open problem whether one can replace the random oracle model in Theorem 1 with well-studied cryptographic assumptions; black-box hardness does not translate into white-box hardness in general [49 ] .
Average-case TFNP and proof complexity
Proof complexity and black-box TFNP classes are intimately connected: each T F N P d t \mathrm{TFNP}^{\mathrm{dt}} TFNP dt [6 ] , with PLS corresponding to resolution width [BKT14, Kam19], PPA to Nullstellensatz over F 2 \mathbb{F}_2 F 2 [30 ] , and PPAD to unary Nullstellensatz [29 ] .
When extending these equivalences to the ROM, the relevant new feature is error, which we model by a low-width “advice” DNF B B B 1 / 3 1/3 1/3 ω ( u ) \omega(u) ω ( u ) u u u F F F F ∨ B F \vee B F ∨ B B B B [26 ] . The key distinction is that in our case, the distribution ω ( u ) \omega(u) ω ( u )
Our separations are thus lower bounds for approximately sound proofs. We briefly survey three settings in which such proofs arise.
Extension complexity. Lower bounds on the size of LP and SDP relaxations for approximating CSPs [21 , 54 , 47 ] convert, via query-to-communication lifting, a small relaxation into a low-degree Sherali–Adams or Sum-of-Squares certificate. The extracted certificate is correct only up to a small error, measured on average over assignments, which is absorbed into the approximation guarantee. At the core of such a result is therefore a degree lower bound for approximate low-degree refutations of a particular gap statement.
Random resolution. Random resolution, defined in [BKT14] following a suggestion of Dantchev, formalizes resolution refutations that may err on a small fraction of assignments; it arose as the propositional counterpart of Jeřábek’s theories of approximate counting. The first lower bounds for random resolution were obtained for the colored polynomial local search principle CPLS, and for the pigeonhole principle [61 , 52 ] .
The relation to the random oracle model is as follows. A ROM reduction from a totality principle F F F F F F ω ( u ) \omega(u) ω ( u ) u u u ω \omega ω locally samplable distribution, and a ROM lower bound against PLS is a random resolution lower bound over that particular distribution. The converse does not always hold. For example, the previously established lower bounds for random resolution [61 , 52 ] yield distributions that are hard for random resolution, but these distributions are not known to be locally samplable from uniform bits, so they do not imply ROM separations. Separations between TFNP subclasses under deterministic black-box reductions are well understood [2 Mór01, 12 , 36 , 30 , 15 , 29 ] . Similarly the randomized separations between pairs of TFNP subclasses in [Li24, JLRX24, Kis26], and the oracle separations of the multi-collision classes in [48 ] , do not apply to the ROM. In contrast, Bitansky and Gerichter Bitansky and Gerichter [7 ] obtained a ROM separation of PLS from FP; that is, they constructed a distribution over PLS instances that is efficiently samplable from a uniformly random oracle, but that is hard for FP. Similarly we obtain the following ROM separations: (i) PWPP vs. PLS (Theorem 36), (ii) PPA vs. PLS (Theorem 39) and (iii) EoPL vs. FP (Corollary 14).
AC0 ^{0} 0 p p p Nullstellensatz [BIK+96] and Polynomial Calculus [17 ] were introduced in large part to obtain an analogue, for AC0 ^{0} 0 p p p [62 Smo87] , which replaces each gate of a circuit by a low-degree polynomial over F p \mathbb{F}_p F p 0 ^{0} 0 p p p F p \mathbb{F}_p F p
Techniques
We overview the techniques behind our results. § 3.1 recalls the decision-tree formulation of the random oracle model used throughout. § 3.2 sketches the proof of PPAD hardness (Theorem 1), § 3.3 the UEoPL algorithm (Theorem 15), and § 3.4 the separations from PLS (Theorems 36 and 39).
TFNP in the ROM briefing
In the cryptographic formulation, a TFNP problem in the ROM is specified by a verifier , a polynomial-time algorithm with oracle access that, given an instance and a candidate solution, decides whether the candidate is a solution; totality means that every instance has at least one solution. An instance is a circuit C C C { 0 , 1 } poly ( n ) \{0,1\}^{\operatorname{poly}(n)} { 0 , 1 } poly ( n ) Σ \Sigma Σ ∣ Σ ∣ ≤ 2 poly ( n ) |\Sigma| \le2^{\operatorname{poly}(n)} ∣Σ∣ ≤ 2 poly ( n ) sampler with oracle access outputs instances that no polynomial-time solver with oracle access solves with probability 2 / 3 2/3 2/3 u ∈ { 0 , 1 } N u \in\{0,1\}^{N} u ∈ { 0 , 1 } N C C C x ∈ Σ N x \in\Sigma^{N} x ∈ Σ N N = 2 poly ( n ) N = 2^{\operatorname{poly}(n)} N = 2 poly ( n ) u u u x x x C C C poly ( n ) = polylog ( N ) \operatorname{poly}(n) = \operatorname{polylog}(N) poly ( n ) = polylog ( N ) u u u C C C § 11 for a formal definition of the cryptographic formulation of the ROM model.
Note that only these query counts matter for our lower bound proofs, which leads to the following decision-tree formulation , used throughout the paper. A TFNP d t \operatorname{TFNP}^{\mathrm{dt}} TFNP dt S ⊆ Σ N × O S \subseteq\Sigma^{N} \times\mathcal{O} S ⊆ Σ N × O ∣ O ∣ ≤ 2 polylog ( N ) |\mathcal{O}| \le2^{\operatorname{polylog}(N)} ∣ O ∣ ≤ 2 polylog ( N ) o ∈ O o \in\mathcal{O} o ∈ O ( x , o ) ∈ S (x,o) \in S ( x , o ) ∈ S polylog ( N ) \operatorname{polylog}(N) polylog ( N ) x x x instance distribution is a forest ω = ( ω 1 , … , ω N ) \omega= (\omega_1,\ldots,\omega_N) ω = ( ω 1 , … , ω N ) ω i : { 0 , 1 } N → Σ \omega_i : \{0,1\}^{N} \to\Sigma ω i : { 0 , 1 } N → Σ polylog ( N ) \operatorname{polylog}(N) polylog ( N ) u u u ω ( u ) ∈ Σ N \omega(u) \in\Sigma^{N} ω ( u ) ∈ Σ N solver is a decision tree A : { 0 , 1 } N → O A : \{0,1\}^{N} \to\mathcal{O} A : { 0 , 1 } N → O
We say that S ∈ F P S \in\mathrm{FP} S ∈ FP in the black-box ROM if for every decision forest ω \omega ω A A A polylog ( N ) \operatorname{polylog}(N) polylog ( N )
Pr u ∼ { 0 , 1 } N [ ( ω ( u ) , A ( u ) ) ∈ S ] ≥ 2 / 3 , \Pr_{u \sim\{0,1\}^{N}}[(\omega(u), A(u)) \in S] \ge2/3, u ∼ { 0 , 1 } N Pr [( ω ( u ) , A ( u )) ∈ S ] ≥ 2/3 , and that S S S hard on average in Romantica otherwise. A polynomial-time solver with oracle access makes polynomially many queries, so it is a solver of depth polylog ( N ) \operatorname{polylog}(N) polylog ( N )
Since ω \omega ω u u u S ′ = { ( u , o ) ∣ ( ω ( u ) , o ) ∈ S } S' = \{(u,o) \mid(\omega(u),o) \in S\} S ′ = {( u , o ) ∣ ( ω ( u ) , o ) ∈ S } TFNP d t \operatorname{TFNP}^{\mathrm{dt}} TFNP dt u ∼ Σ N u \sim\Sigma^{N} u ∼ Σ N 2
PPAD lower bound
Consider the following search problem template: given a large hypergraph with a labeling of the vertices, find an edge whose vertex labels satisfy a constraint. This yields a search problem for every choice of hypergraph and constraint. For several simple choices of the two, it is easy to show that the problem is total , but then it is also easy to solve. Our proof takes the Yamakawa–Zhandry hypergraph , originally used to separate quantum and classical algorithms [YZ24]. The constraint part of their search problem does not guarantee totality, but the search problem is hard for classical algorithms. The key idea is to tweak their construction, which sits at the hard-but-not-total end of this spectrum, toward the total-but-easy end, stopping at a problem that is total (in fact, in PPAD) while still hard.
Which class the resulting problem lands in is determined by how its totality is proved. We first show hardness-on-average in Romantica of the class PPA, for parity arguments , which contains the subclass PPAD. We then refine the construction to obtain a hard-on-average problem in PPAD. Informally, problems in PPA are exactly the problems whose totality can be proven by an efficient parity argument, and the problems in PPAD are the ones whose totality can be proven by an efficient signed counting argument. In our construction, these arguments simply sum local constraints modulo 2 or over Z \mathbb{Z} Z ± 1 \pm1 ± 1 [30 ] and [29 ] respectively. The corresponding polynomial refutations must have suitably bounded degree and size, with coefficients measured in unary over Z \mathbb{Z} Z
Find a problem that is hard on average given random access to a uniformly random string, and whose totality can be proven by counting in F 2 \mathbb{F}_2 F 2 Z \mathbb{Z} Z
PPA worst-case hardness. A canonical PPA problem is finding a falsified equation in an unsatisfiable system of linear equations over F 2 \mathbb{F}_2 F 2 N = 2 n N = 2^n N = 2 n x 1 , … , x N x_1,\ldots,x_N x 1 , … , x N ∑ v ∈ e x v = 1 \sum_{v\in e} x_v = 1 ∑ v ∈ e x v = 1 F 2 \mathbb{F}_2 F 2 hyperedge e ⊆ [ N ] e \subseteq[N] e ⊆ [ N ] x ∈ { 0 , 1 } N x \in\{0,1\}^N x ∈ { 0 , 1 } N N N N G = ( [ N ] , E ) G = ([N],E) G = ([ N ] , E ) G G G ∣ e ∣ ≤ poly ( n ) |e| \le\operatorname{poly}(n) ∣ e ∣ ≤ poly ( n )
L i n G : = { ( x , e ) | ∑ v ∈ e x v = 0 } (1) \mathrm{Lin}_G := \left\{(x,e)\ \middle|\ \sum_{v\in e} x_v = 0\right\} \tag*{(1)} Lin G := { ( x , e ) v ∈ e ∑ x v = 0 } (1) Of course, this NP-relation is only total if we can guarantee the unsatisfiability of the linear system. One way is to enforce that each node v ∈ [ N ] v \in[N] v ∈ [ N ] even number (at most poly ( n ) \operatorname{poly}(n) poly ( n ) ∣ E ∣ |E| ∣ E ∣ odd . Then, one can show that the problem lies in PPA.
However, these conditions do not make the problem LinG _G G G G G worst-case hardness holds if G G G expansion properties [Tse70, Urq87]. However, it is not clear how to extend this to average-case hardness; for instance, if the labeling x ∼ { 0 , 1 } N x \sim\{0,1\}^N x ∼ { 0 , 1 } N ( ⋆ ) (\star) ( ⋆ ) every G G G 1 / 2 1/2 1/2
Yamakawa–Zhandry problem. Our second key ingredient is an NP-search problem defined by Yamakawa and Zhandry [YZ24] in order to separate quantum and classical algorithms for search problems in the ROM. Let G = ( [ N ] , E ) G = ([N],E) G = ([ N ] , E ) E ⊆ ( [ N ] ℓ ) E \subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) ℓ = poly ( n ) \ell= \operatorname{poly}(n) ℓ = poly ( n ) G _G G x ∈ { 0 , 1 } N x \in\{0,1\}^N x ∈ { 0 , 1 } N e ∈ E e \in E e ∈ E x v = 0 x_v = 0 x v = 0 v ∈ e v \in e v ∈ e x ∼ { 0 , 1 } N x \sim\{0,1\}^N x ∼ { 0 , 1 } N
The key property of their construction is well-spreadness : G = ( [ N ] , E ) G = ([N],E) G = ([ N ] , E ) ( r , a , b ) (r,a,b) ( r , a , b ) S ⊆ ( [ N ] a ) S \subseteq\binom{[N]}{a} S ⊆ ( a [ N ] ) e ∈ E e \in E e ∈ E ∣ e ∩ S ∣ ≥ r |e \cap S| \ge r ∣ e ∩ S ∣ ≥ r b b b G _G G a a a x x x b b b r r r r r r 2 r − ℓ 2^{r-\ell} 2 r − ℓ b ⋅ 2 r − ℓ ≪ 1 b \cdot2^{r-\ell} \ll1 b ⋅ 2 r − ℓ ≪ 1
PPA-hard problem. One obvious issue with Yamakawa–Zhandry's G G G x = 1 N x=1^{N} x = 1 N parity argument must guarantee that at least one edge satisfies our chosen condition. For a given graph G G G p e : { 0 , 1 } N → { 0 , 1 } p_e:\{0,1\}^{N}\to\{0,1\} p e : { 0 , 1 } N → { 0 , 1 } verifier of e e e p e ( x ) = 1 p_e(x)=1 p e ( x ) = 1 e e e x x x p e p_e p e
∑ e ∈ E p e ( x ) ≡ 1 ( m o d 2 ) . \sum_{e\in E}p_e(x)\equiv1\pmod2. e ∈ E ∑ p e ( x ) ≡ 1 ( mod 2 ) . As witnessed by Lin, a choice of condition p e = 1 + ∑ v ∈ e x v p_e=1+\sum_{v\in e}x_v p e = 1 + ∑ v ∈ e x v F 2 \mathbb{F}_2 F 2 Pr [ p e ( x ) = 1 ] = 1 / 2 \Pr[p_e(x)=1]=1/2 Pr [ p e ( x ) = 1 ] = 1/2 G G G
There is a natural fix for that: suppose that instead of binary labels, we used labels x 1 , … , x N ∈ { 0 , 1 } r x_1,\ldots,x_N\in\{0,1\}^r x 1 , … , x N ∈ { 0 , 1 } r p e ( x ) = ⟦ ⨁ v ∈ e x v = 0 r ⟧ p_e(x)=\llbracket\bigoplus_{v\in e}x_v=0^r\rrbracket p e ( x ) = [ [ ⨁ v ∈ e x v = 0 r ] ] Pr [ p e ( x ) = 1 ] = 2 − r \Pr[p_e(x)=1]=2^{-r} Pr [ p e ( x ) = 1 ] = 2 − r G G G e e e p e ( x ) = 1 p_e(x)=1 p e ( x ) = 1
In order to see what is needed from G G G e ∗ ∈ E e^*\in E e ∗ ∈ E 0 r 0^r 0 r e ∗ e^* e ∗ G G G ∑ e ∈ E p e ( x ) ≡ 0 ( m o d 2 ) \sum_{e\in E}p_e(x)\equiv0\pmod2 ∑ e ∈ E p e ( x ) ≡ 0 ( mod 2 ) p e ∗ ( x ) = 1 p_{e^*}(x)=1 p e ∗ ( x ) = 1 ∑ e ≠ e ∗ p e ( x ) ≡ 1 ( m o d 2 ) \sum_{e\ne e^*}p_e(x)\equiv1\pmod2 ∑ e = e ∗ p e ( x ) ≡ 1 ( mod 2 ) G G G p e p_e p e
∑ e ∈ E ∏ i ∈ [ r ] ( 1 + ∑ v ∈ e x v , i ) ≡ 0 ( m o d 2 ) . \sum_{e\in E}\prod_{i\in[r]}\left(1+\sum_{v\in e}x_{v,i}\right)\equiv0\pmod2. e ∈ E ∑ i ∈ [ r ] ∏ ( 1 + v ∈ e ∑ x v , i ) ≡ 0 ( mod 2 ) . Expanding the brackets we get that the coefficient of monomial x v 1 , i 1 ⋯ x v k , i k x_{v_1,i_1}\cdots x_{v_k,i_k} x v 1 , i 1 ⋯ x v k , i k i 1 , … , i k i_1,\ldots,i_k i 1 , … , i k { v 1 , … , v k } \{v_1,\ldots,v_k\} { v 1 , … , v k } G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) r r r S ∈ ( [ N ] ≤ r ) S\in\binom{[N]}{\le r} S ∈ ( ≤ r [ N ] ) e ⊇ S e\supseteq S e ⊇ S S = ∅ S=\varnothing S = ∅ § 4.4 , we show that a variant of the Yamakawa–Zhandry hypergraph is r r r r = Θ ( ℓ ) r=\Theta(\ell) r = Θ ( ℓ )
PPAD-hard problem. To obtain a problem in PPAD, we replace the parity argument above with an integer cancellation argument. The input to the new hyperedge-search problem is a labeling x ∈ ( [ r ] ∪ { ⊥ } ) N x\in([r]\cup\{\perp\})^N x ∈ ([ r ] ∪ { ⊥ } ) N ⊥ \perp ⊥ e ∗ e^* e ∗ ⊥ \perp ⊥ e ∗ e^* e ∗
p e : = ∏ i ∈ [ r ] ( 1 − ∑ v ∈ e ⟦ x v = i ⟧ ) . p_e:=\prod_{i\in[r]}\left(1-\sum_{v\in e}\llbracket x_v=i\rrbracket\right). p e := i ∈ [ r ] ∏ ( 1 − v ∈ e ∑ [ [ x v = i ] ] ) . Thus, p e ( x ) ≠ 0 p_e(x)\ne0 p e ( x ) = 0 ⊥ \perp ⊥ e e e p e p_e p e ε e ∈ { ± 1 } \varepsilon_e\in\{\pm1\} ε e ∈ { ± 1 } ∑ e ∈ E ε e p e ≡ 0 \sum_{e\in E}\varepsilon_ep_e\equiv0 ∑ e ∈ E ε e p e ≡ 0 k k k S = { v 1 , … , v k } S=\{v_1,\ldots,v_k\} S = { v 1 , … , v k } ( − 1 ) k ∑ e ⊇ S ε e (-1)^k\sum_{e\supseteq S}\varepsilon_e ( − 1 ) k ∑ e ⊇ S ε e 0 ≤ k ≤ r 0\le k\le r 0 ≤ k ≤ r S ∈ ( [ N ] ≤ r ) S\in\binom{[N]}{\le r} S ∈ ( ≤ r [ N ] ) S S S § 4.4 that the Yamakawa–Zhandry hypergraph admits such signing.
Since all labels on e ∗ e^* e ∗ ⊥ \perp ⊥ p e ∗ ( x ) = 1 p_{e^*}(x)=1 p e ∗ ( x ) = 1 ε e ∗ = 1 \varepsilon_{e^*}=1 ε e ∗ = 1
− ∑ e ∈ E ∖ { e ∗ } ε e p e ( x ) = 1. -\sum_{e\in E\setminus\{e^*\}}\varepsilon_ep_e(x)=1. − e ∈ E ∖ { e ∗ } ∑ ε e p e ( x ) = 1. At least one non-forbidden edge therefore has p e ( x ) ≠ 0 p_e(x)\ne0 p e ( x ) = 0 counting over integers . We make this formal in § 4.3 .
UEoPL upper bound
The problem setup. It is convenient to use the grid form of UEoPL from [29 ] . The nodes are the cells ( i , j ) (i,j) ( i , j ) N × N N \times N N × N i i i Succ ( i , j ) ∈ [ N ] ∪ { ⊥ } \operatorname{Succ}_{(i,j)} \in[N] \cup\{\perp\} Succ ( i , j ) ∈ [ N ] ∪ { ⊥ } ( i + 1 , Succ ( i , j ) ) (i+1,\operatorname{Succ}_{(i,j)}) ( i + 1 , Succ ( i , j ) ) active if its successor’s predecessor points back to it: Succ ( i , j ) = k \operatorname{Succ}_{(i,j)} = k Succ ( i , j ) = k Pred ( i + 1 , k ) = j \operatorname{Pred}_{(i+1,k)} = j Pred ( i + 1 , k ) = j Succ ≠ ⊥ \operatorname{Succ} \ne\perp Succ = ⊥ ( 1 , 1 ) (1,1) ( 1 , 1 ) line that descends one row per step, so it must end at an inactive node that an active node points to (a proper sink ) or at an active node of row N N N ( 1 , 1 ) (1,1) ( 1 , 1 ) N N N ( 1 , 1 ) (1,1) ( 1 , 1 ) two active nodes in the same row . The last kind is what makes this UEoPL rather than EoPL: proof of a second line is also a solution. Activity is the only notion our algorithm uses, and testing it costs at most two pointer reads.
In the random oracle model an instance is generated from the oracle u ∈ { 0 , 1 } N u \in\{0,1\}^{N} u ∈ { 0 , 1 } N q q q u u u O ( q 5 log N ) O(q^{5}\log N) O ( q 5 log N ) u u u 2 / 3 2/3 2/3 u u u black-box statement: it counts queries, not computation.
Jumping and a win-win argument. The obvious strategy is to begin at the active cell ( 1 , 1 ) (1,1) ( 1 , 1 ) 2 q 2q 2 q Θ ( q N ) \Theta(qN) Θ ( q N ) poly ( q ) log N \operatorname{poly}(q)\log N poly ( q ) log N 2 r 2^r 2 r 2 r − 1 2^{r-1} 2 r − 1 log N \log N log N dichotomy lemma (Lemma 16, originally proved in [3 ] ): an algorithm that finds solutions, whatever its query cost, can be collapsed either to a query-efficient one or to one that outputs two solutions . In our setting it says the following about any tree D D D b b b O ( q 2 ) O(q^2) O ( q 2 ) D D D b b b 1 / 2 1/2 1/2 D D D two active nodes of row b b b Ω ( 1 / q ) \Omega(1/q) Ω ( 1/ q )
Why the dichotomy holds. Think of each accepting leaf of the activity tree of a node y y y b b b certificate : at most 2 q 2q 2 q y y y D D D u u u D D D O ( q 2 ) O(q^2) O ( q 2 ) b b b D D D D D D
The algorithm. A subroutine Jump ( v , r ) \operatorname{Jump}(v,r) Jump ( v , r ) v v v 2 r 2^r 2 r defines , but does not run, the tree C C C C C C C C C C C C O ( q ) O(q) O ( q ) r r r r = ⌈ log 2 N ⌉ r = \lceil\log_2 N\rceil r = ⌈ log 2 N ⌉
Separations from PLS
The known worst-case separations from PLS are obtained by proving resolution-width lower bounds. A low-width resolution refutation can be viewed as a generalization of a low-height decision tree. In particular, let F ⊆ Σ n × O F \subseteq\Sigma^n \times\mathcal{O} F ⊆ Σ n × O x ∈ Σ n x \in\Sigma^n x ∈ Σ n o ∈ O o \in\mathcal{O} o ∈ O ( x , o ) ∈ F (x,o) \in F ( x , o ) ∈ F w w w F F F x ∈ Σ n x \in\Sigma^n x ∈ Σ n w w w o ∈ O o \in\mathcal{O} o ∈ O ( x , o ) ∈ F (x,o) \in F ( x , o ) ∈ F x x x x x x w w w ρ ∈ ( Σ ∪ { ⋆ } ) n \rho\in(\Sigma\cup\{\star\})^n ρ ∈ ( Σ ∪ { ⋆ } ) n w w w w w w x x x ρ \rho ρ o ρ ∈ O o_\rho\in\mathcal{O} o ρ ∈ O ( x ′ , o ρ ) ∈ F (x',o_\rho) \in F ( x ′ , o ρ ) ∈ F x ′ x' x ′ ρ \rho ρ
We now describe a width-w w w F F F F F F x x x ≤ w \leq w ≤ w ρ \rho ρ x x x o o o purely a function of the current known partial assignment (and cannot depend otherwise on the history of the query procedure). To allow this process to run for more than w w w w w w w w w < w < w < w
Fact 1. ([BKT14, Kam19]). For any F ∈ T F N P d t F \in\mathrm{TFNP}^{\mathrm{dt}} F ∈ TFNP dt F ∈ P L S d t F \in\mathrm{PLS}^{\mathrm{dt}} F ∈ PLS dt ( log n ) (\log n) ( log n ) ( F , S ) (\mathcal{F},S) ( F , S ) F F F
Definition 1. A resolution refutation of width w w w F ⊆ ( Σ ∪ { ⋆ } ) n \mathcal{F} \subseteq(\Sigma\cup\{\star\})^n F ⊆ ( Σ ∪ { ⋆ } ) n S : F × Σ → F S:\mathcal{F} \times\Sigma\to\mathcal{F} S : F × Σ → F ⋆ n ∈ F \star^n \in\mathcal{F} ⋆ n ∈ F ρ ∈ F \rho\in\mathcal{F} ρ ∈ F
ρ \rho ρ w w w
If ∣ ρ ∣ = w |\rho| = w ∣ ρ ∣ = w fixes a solution : there is some o ∈ O o \in\mathcal{O} o ∈ O ( x , o ) ∈ F (x,o) \in F ( x , o ) ∈ F x ∈ Σ n x \in\Sigma^n x ∈ Σ n ρ \rho ρ
If ∣ ρ ∣ < w |\rho| < w ∣ ρ ∣ < w i = i ( ρ ) ∈ [ n ] i=i(\rho) \in[n] i = i ( ρ ) ∈ [ n ] ρ ( i ) = ⋆ \rho(i)=\star ρ ( i ) = ⋆ a ∈ Σ a \in\Sigma a ∈ Σ S ( ρ , a ) ⊆ ρ ∪ { i ↦ a } S(\rho,a) \subseteq\rho\cup\{i \mapsto a\} S ( ρ , a ) ⊆ ρ ∪ { i ↦ a }
Finally, there is a strict total ordering ≺ \prec ≺ F \mathcal{F} F ρ ≺ S ( ρ , a ) \rho\prec S(\rho,a) ρ ≺ S ( ρ , a ) ρ ∈ F \rho\in\mathcal{F} ρ ∈ F ∣ ρ ∣ < w |\rho| < w ∣ ρ ∣ < w a ∈ Σ a \in\Sigma a ∈ Σ
In the terminology of our previously described query procedure, F \mathcal{F} F S S S
With this perspective we can easily describe the classical separation P P P d t ⊈ P L S d t \mathrm{PPP}^{\mathrm{dt}} \not\subseteq\mathrm{PLS}^{\mathrm{dt}} PPP dt ⊆ PLS dt [2 ] . Let Σ = { 0 , 1 } n ∖ { 0 n } \Sigma=\{0,1\}^n \setminus\{0^n\} Σ = { 0 , 1 } n ∖ { 0 n } N = 2 n N=2^n N = 2 n x ∈ Σ N x \in\Sigma^N x ∈ Σ N x ( v ) x(v) x ( v ) v ∈ { 0 , 1 } n v \in\{0,1\}^n v ∈ { 0 , 1 } n w = polylog ( N ) w=\operatorname{polylog}(N) w = polylog ( N ) x x x N − 2 N-2 N − 2 ρ \rho ρ ⋆ \star ⋆ v v v ρ ( v ) = ⋆ \rho(v)=\star ρ ( v ) = ⋆ a ∈ Σ a \in\Sigma a ∈ Σ ρ ∪ { v ↦ a } \rho\cup\{v \mapsto a\} ρ ∪ { v ↦ a } a a a Σ ∖ { ρ ( v ′ ) ∣ v ′ ≤ N } \Sigma\setminus\{\rho(v') \mid v' \leq N\} Σ ∖ { ρ ( v ′ ) ∣ v ′ ≤ N }
To prove our actual separation, we need to somehow extend this argument to show that it holds “on average over a random x ∼ Σ N x \sim\Sigma^N x ∼ Σ N w = polylog ( N ) w=\operatorname{polylog}(N) w = polylog ( N ) F , S \mathcal{F},S F , S with high probability over x ∼ Σ N x \sim\Sigma^N x ∼ Σ N ρ ∈ F \rho\in\mathcal{F} ρ ∈ F x ⊇ ρ x \supseteq\rho x ⊇ ρ ρ \rho ρ v ≠ v ′ ∈ [ N ] v \ne v' \in[N] v = v ′ ∈ [ N ] ρ ( v ) = ρ ( v ′ ) ∈ Σ \rho(v)=\rho(v') \in\Sigma ρ ( v ) = ρ ( v ′ ) ∈ Σ ρ \rho ρ polylog ( N ) \operatorname{polylog}(N) polylog ( N ) v ∈ [ N ] v \in[N] v ∈ [ N ] ρ ∪ { v ↦ a } \rho\cup\{v \mapsto a\} ρ ∪ { v ↦ a } with overwhelming probability over a random a ∼ Σ a \sim\Sigma a ∼ Σ polylog ( N ) N − 1 \frac{\operatorname{polylog}(N)}{N-1} N − 1 polylog ( N ) robustness ; it implies that for any nonterminal ρ \rho ρ
Pr x ∼ Σ N [ S ( ρ , x i ( ρ ) ) fixes a solution ∣ x ⊇ ρ ] ≤ polylog ( N ) N − 1 \Pr_{x \sim\Sigma^N}\left[S(\rho,x_{i(\rho)})\text{ fixes a solution}\mid x\supseteq\rho\right]\leq\frac{\operatorname{polylog}(N)}{N-1} x ∼ Σ N Pr [ S ( ρ , x i ( ρ ) ) fixes a solution ∣ x ⊇ ρ ] ≤ N − 1 polylog ( N ) A naive strategy would be to start at ρ = ⋆ N \rho= \star^N ρ = ⋆ N S S S N N N ⋆ N \star^N ⋆ N any terminal x ⊇ ρ ∈ F x \supseteq\rho\in\mathcal{F} x ⊇ ρ ∈ F x x x
Our approach will instead be more global. Let E ⊆ F \mathcal{E} \subseteq\mathcal{F} E ⊆ F F \mathcal{F} F B ⊆ Σ N B \subseteq\Sigma^N B ⊆ Σ N ρ ∈ E \rho\in\mathcal{E} ρ ∈ E x ⊇ ρ x \supseteq\rho x ⊇ ρ Pr [ x ∈ B ] ≥ 1 − ( log N ) − ω ( 1 ) \Pr[x \in B] \ge1 - (\log N)^{-\omega(1)} Pr [ x ∈ B ] ≥ 1 − ( log N ) − ω ( 1 ) x x x F ′ \mathcal{F}' F ′ x ∈ Σ N x \in\Sigma^N x ∈ Σ N x x x ρ ∈ E \rho\in\mathcal{E} ρ ∈ E x ⊇ ρ x \supseteq\rho x ⊇ ρ F \mathcal{F} F worst-case resolution refutation for the relation F ′ \mathcal{F}' F ′ F ⊆ Σ N × O \mathcal{F} \subseteq\Sigma^N \times\mathcal{O} F ⊆ Σ N × O T F N P d t \mathsf{TFNP}^{\mathrm{dt}} TFNP dt T F N P d t \mathsf{TFNP}^{\mathrm{dt}} TFNP dt F ′ ⊆ Σ N × ( O ⊔ O ′ ) \mathcal{F}' \subseteq\Sigma^N \times(\mathcal{O} \sqcup\mathcal{O}') F ′ ⊆ Σ N × ( O ⊔ O ′ ) x ∈ Σ N x \in\Sigma^N x ∈ Σ N o ∈ O o \in\mathcal{O} o ∈ O ( x , o ) ∈ F ′ ⟺ ( x , o ) ∈ F (x,o) \in\mathcal{F}' \Longleftrightarrow(x,o) \in\mathcal{F} ( x , o ) ∈ F ′ ⟺ ( x , o ) ∈ F Pr [ ∃ o ′ ∈ O ′ , ( x , o ′ ) ∈ F ′ ] ≤ 1 − ( polylog ( N ) ) − 1 \Pr[\exists o' \in\mathcal{O}', (x,o') \in\mathcal{F}'] \le1 - (\operatorname{polylog}(N))^{-1} Pr [ ∃ o ′ ∈ O ′ , ( x , o ′ ) ∈ F ′ ] ≤ 1 − ( polylog ( N ) ) − 1 F ′ \mathcal{F}' F ′ polylog ( N ) \operatorname{polylog}(N) polylog ( N )
The key is that we have offloaded the “average case” condition into a modification of the search problem itself, and the remaining task is to prove a “worst case” resolution width lower bound for this modified search problem.
To prove this resolution bound we utilize a linear-algebraic embedding originally developed by Razborov [Raz03] as a key step in his pseudo-width method. To prove a resolution lower bound for F ′ \mathcal{F}' F ′ ρ \rho ρ O ′ \mathcal{O}' O ′ F ′ \mathcal{F}' F ′ w w w F ′ \mathcal{F}' F ′ ∣ ρ ∣ < w |\rho| < w ∣ ρ ∣ < w i i i ρ ( i ) = ⋆ \rho(i) = \star ρ ( i ) = ⋆ a ∈ Σ a \in\Sigma a ∈ Σ ρ ∪ { i ↦ a } \rho\cup\{i \mapsto a\} ρ ∪ { i ↦ a }
As alluded to above, the only property of PPP we will use is its “robustness” (we have not defined robustness formally at this point). This property is easily shown to hold for the subclass PWPP, and so in § 6.3 we prove the stronger ROM separation PWPP ⊈ \not\subseteq ⊆ § 6.4 we exhibit a problem in the class P P A d t \mathsf{PPA}^{\mathrm{dt}} PPA dt ⊈ \not\subseteq ⊆ ⊈ \not\subseteq ⊆
Average-case separation between PPAD and FP
In this section we prove the following theorem, giving an exponential separation between PPAD and FP in the ROM setting.
Theorem 1. There exists a TFNP search problem F = { F N ⊆ Σ N × O } \mathcal{F} = \{F_N \subseteq\Sigma^N \times\mathcal{O}\} F = { F N ⊆ Σ N × O } T T T exp ( ( log N ) o ( 1 ) ) \exp((\log N)^{o(1)}) exp (( log N ) o ( 1 ) ) F \mathcal{F} F
Pr u ∼ Σ N [ ( u , T ( u ) ) ∈ F N ] ≤ exp ( − ( log N ) Ω ( 1 ) ) . \Pr_{u \sim\Sigma^N}[(u,T(u)) \in F_N] \le\exp\left(-(\log N)^{\Omega(1)}\right). u ∼ Σ N Pr [( u , T ( u )) ∈ F N ] ≤ exp ( − ( log N ) Ω ( 1 ) ) . In particular, PPAD ̸ ⊆ R O M \not\subseteq_{\mathrm{ROM}} ⊆ ROM
We start by defining the hard problem. Let G = ( [ N ] , E ) G = ([N], E) G = ([ N ] , E ) ℓ \ell ℓ E ⊆ ( [ N ] ℓ ) E \subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) h : [ N ] → [ τ ] h: [N] \to[\tau] h : [ N ] → [ τ ] e = { v 1 , … , v ℓ } ∈ E e = \{v_1,\ldots,v_\ell\} \in E e = { v 1 , … , v ℓ } ∈ E h ( v 1 ) , … , h ( v ℓ ) h(v_1),\ldots,h(v_\ell) h ( v 1 ) , … , h ( v ℓ ) i ∈ [ τ ] i \in[\tau] i ∈ [ τ ] i ∉ { h ( v 1 ) , … , h ( v ℓ ) } i \notin\{h(v_1),\ldots,h(v_\ell)\} i ∈ / { h ( v 1 ) , … , h ( v ℓ )} ( ⊥ ) (\perp) ( ⊥ ) e ∗ = [ ℓ ] e^* = [\ell] e ∗ = [ ℓ ] [ ℓ ] [\ell] [ ℓ ] ⊥ \perp ⊥ e ∗ e^* e ∗ another solution.
Formally, let H \mathcal{H} H h : [ N ] → ( { ⊥ } ∪ [ τ ] ) h : [N] \to(\{\perp\} \cup[\tau]) h : [ N ] → ({ ⊥ } ∪ [ τ ]) h ( [ ℓ ] ) = { ⊥ } h([\ell]) = \{\perp\} h ([ ℓ ]) = { ⊥ } Singleton G ⊆ H × ( E ∖ { e ∗ } ) \operatorname{Singleton}_{G} \subseteq\mathcal{H} \times(E \setminus\{e^*\}) Singleton G ⊆ H × ( E ∖ { e ∗ }) h ∈ H h \in\mathcal{H} h ∈ H e = { v 1 , … , v ℓ } ∈ E ∖ { e ∗ } e = \{v_1,\ldots,v_\ell\} \in E \setminus\{e^*\} e = { v 1 , … , v ℓ } ∈ E ∖ { e ∗ } ⊥ \perp ⊥ h ( v 1 ) , … , h ( v ℓ ) h(v_1),\ldots,h(v_\ell) h ( v 1 ) , … , h ( v ℓ ) G G G
Hardness For h ∼ H h \sim\mathcal{H} h ∼ H T T T 2 ℓ 1 / 4 2^{\ell^{1/4}} 2 ℓ 1/4 h h h Singleton G \operatorname{Singleton}_{G} Singleton G
Pr [ ( h , T ( h ) ) ∈ Singleton G ] ≤ exp ( − ℓ Ω ( 1 ) ) . \Pr[(h,T(h)) \in\operatorname{Singleton}_{G}] \le\exp(-\ell^{\Omega(1)}). Pr [( h , T ( h )) ∈ Singleton G ] ≤ exp ( − ℓ Ω ( 1 ) ) . PPAD-inclusion Singleton G ∈ PPAD \operatorname{Singleton}_{G} \in\operatorname{PPAD} Singleton G ∈ PPAD
In § 4.1 we prove that Singleton G \operatorname{Singleton}_{G} Singleton G E E E E ⊆ ( [ N ] ℓ ) E \subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) ( r , a , b ) (r,a,b) ( r , a , b ) S ⊆ [ N ] S \subseteq[N] S ⊆ [ N ] a a a e ∈ E e \in E e ∈ E ∣ e ∩ S ∣ ≥ r |e \cap S| \ge r ∣ e ∩ S ∣ ≥ r b b b Figure 2 for an illustration.
Figure 2. This figure illustrates the setting of the problem Singleton.
Then in § 4.3 we show that Singleton G ∈ PPAD \operatorname{Singleton}_{G} \in\operatorname{PPAD} Singleton G ∈ PPAD E E E E ⊆ ( [ N ] ℓ ) E \subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) r r r ε ∈ { ± 1 } E \varepsilon\in\{\pm1\}^{E} ε ∈ { ± 1 } E R ∈ ( [ N ] r ) R \in\binom{[N]}{r} R ∈ ( r [ N ] ) ∑ e ⊇ R ε e = 0 \sum_{e \supseteq R} \varepsilon_e = 0 ∑ e ⊇ R ε e = 0
Finally, in § 4.4 we show that there is an efficient construction of G G G
PPAD hardness
Theorem 2. Fix τ \tau τ [ ℓ / 4 , ℓ / 2.6 ] [\ell/4,\ell/2.6] [ ℓ /4 , ℓ /2.6 ] E E E ( 3 τ / 2 , q , b ) (3\tau/2,q,b) ( 3 τ /2 , q , b ) T : H → E ∖ { e ∗ } T : \mathcal{H} \to E \setminus\{e^*\} T : H → E ∖ { e ∗ } q q q e ∈ E ∖ { e ∗ } e \in E \setminus\{e^*\} e ∈ E ∖ { e ∗ } ∣ e ∩ [ ℓ ] ∣ ≤ τ |e \cap[\ell]| \le\tau ∣ e ∩ [ ℓ ] ∣ ≤ τ ( h , T ( h ) ) ∈ Singleton ( [ N ] , E ) (h,T(h)) \in\operatorname{Singleton}_{([N],E)} ( h , T ( h )) ∈ Singleton ([ N ] , E ) O ( b ) ⋅ exp ( − Ω ( τ ) ) O(b) \cdot\exp(-\Omega(\tau)) O ( b ) ⋅ exp ( − Ω ( τ ))
Proof. Associated with each path in T T T ρ ∈ ( { ⋆ , ⊥ } ∪ [ τ ] ) N \rho\in(\{\star,\perp\} \cup[\tau])^N ρ ∈ ({ ⋆ , ⊥ } ∪ [ τ ] ) N fix ( ρ ) \operatorname{fix}(\rho) fix ( ρ ) ρ \rho ρ fix ( ρ ) : = ρ − 1 ( [ τ ] ∪ { ⊥ } ) \operatorname{fix}(\rho) := \rho^{-1}([\tau] \cup\{\perp\}) fix ( ρ ) := ρ − 1 ([ τ ] ∪ { ⊥ }) v ∈ T v \in T v ∈ T ρ v \rho_v ρ v T T T v v v ρ \rho ρ Leaf ( ρ ) \operatorname{Leaf}(\rho) Leaf ( ρ )
Let T ( ρ ) T(\rho) T ( ρ ) T T T Leaf ( ρ ) \operatorname{Leaf}(\rho) Leaf ( ρ ) T T T h ∼ H h \sim\mathcal{H} h ∼ H
∑ ρ a root-to-leaf path in T Pr [ h is consistent with ρ ] ⋅ Pr [ ( h , T ( ρ ) ) ∈ SINGLETON G ∣ h is consistent with ρ ] \sum_{\rho\ \text{a root-to-leaf path in }T} \Pr[h\text{ is consistent with }\rho]\cdot\Pr[(h,T(\rho))\in\operatorname{SINGLETON}_G\mid h\text{ is consistent with }\rho] ρ a root-to-leaf path in T ∑ Pr [ h is consistent with ρ ] ⋅ Pr [( h , T ( ρ )) ∈ SINGLETON G ∣ h is consistent with ρ ] For a path ρ \rho ρ T T T e ∈ E e \in E e ∈ E e e e exposed by ρ \rho ρ 3 τ / 2 3\tau/2 3 τ /2 e e e h h h ρ \rho ρ
The following Lemma states that for any path ρ \rho ρ T T T e ≠ e ∗ e \ne e^* e = e ∗ 3 τ / 2 3\tau/2 3 τ /2 h h h e e e ρ \rho ρ e e e § 4.2 .
Lemma 3. Let G , e ∗ , ℓ , τ G,e^*,\ell,\tau G , e ∗ , ℓ , τ ρ \rho ρ e ≠ e ∗ e \ne e^* e = e ∗ ∣ fix ( ρ ) ∩ e ∣ ≤ 3 τ / 2 |\operatorname{fix}(\rho)\cap e|\le3\tau/2 ∣ fix ( ρ ) ∩ e ∣ ≤ 3 τ /2 ℓ ≥ 2.6 τ \ell\ge2.6\tau ℓ ≥ 2.6 τ ℓ = O ( τ ) \ell=O(\tau) ℓ = O ( τ )
Pr [ ( h , e ) ∈ SINGLETON G ∣ h extends ρ ] ≤ exp ( − Ω ( τ ) ) . \Pr[(h,e)\in\operatorname{SINGLETON}_G\mid h\text{ extends }\rho]\le\exp(-\Omega(\tau)). Pr [( h , e ) ∈ SINGLETON G ∣ h extends ρ ] ≤ exp ( − Ω ( τ )) . Equipped with Lemma 3, we proceed with the lower bound. There are two cases to consider.
Case I. The first case is if the path ρ \rho ρ T T T T ( ρ ) T(\rho) T ( ρ ) not exposed. This is the easy case, and we can apply Lemma 3 directly to deduce that Pr [ ( h , T ( ρ ) ) ∈ SINGLETON G ∣ h extends ρ ] ≤ exp ( − Ω ( τ ) ) \Pr[(h,T(\rho))\in\operatorname{SINGLETON}_G\mid h\text{ extends }\rho]\le\exp(-\Omega(\tau)) Pr [( h , T ( ρ )) ∈ SINGLETON G ∣ h extends ρ ] ≤ exp ( − Ω ( τ ))
Case II. The second case is the harder and more interesting case, where ρ \rho ρ T T T T ( ρ ) T(\rho) T ( ρ ) ρ \rho ρ ρ \rho ρ e e e h h h T ( ρ ) T(\rho) T ( ρ ) and that ( h , T ( ρ ) ) ∈ SINGLETON G (h,T(\rho))\in\operatorname{SINGLETON}_G ( h , T ( ρ )) ∈ SINGLETON G h h h solutions .
The rest of the proof will focus on Case II. First, the following claim bounds the number of exposed edges on any given path of T T T
Claim 4. For every path ρ \rho ρ T T T b b b ρ \rho ρ
Proof. Recall that fix ( ρ ) \operatorname{fix}(\rho) fix ( ρ ) ρ \rho ρ ∣ fix ( ρ ) ∣ ≤ q |\operatorname{fix}(\rho)|\le q ∣ fix ( ρ ) ∣ ≤ q ( 3 τ / 2 , q , b ) (3\tau/2,q,b) ( 3 τ /2 , q , b ) b b b e ∈ E e\in E e ∈ E ∣ e ∩ fix ( ρ ) ∣ ≥ 3 τ / 2 |e\cap\operatorname{fix}(\rho)|\ge3\tau/2 ∣ e ∩ fix ( ρ ) ∣ ≥ 3 τ /2
For each path ρ \rho ρ T T T List ( ρ ) \operatorname{List}(\rho) List ( ρ ) ( v , e ) (v,e) ( v , e ) e ≠ e ∗ e\ne e^* e = e ∗ e e e ρ \rho ρ v v v ∣ List ( ρ ) ∣ ≤ b |\operatorname{List}(\rho)|\le b ∣ List ( ρ ) ∣ ≤ b v v v v v v List ( ρ ) \operatorname{List}(\rho) List ( ρ ) ρ \rho ρ List ( ρ ) \operatorname{List}(\rho) List ( ρ ) b b b
Now let ρ \rho ρ ( v , e ) (v,e) ( v , e ) List ( ρ ) \operatorname{List}(\rho) List ( ρ ) v v v ρ \rho ρ e e e ρ v \rho_v ρ v ρ \rho ρ T T T v v v ρ v \rho_v ρ v 3 τ / 2 3\tau/2 3 τ /2 h h h e e e ℓ − 3 τ / 2 \ell-3\tau/2 ℓ − 3 τ /2
Now we can apply Lemma 3 here to obtain:
Pr [ ( h , e ) ∈ SINGLETON G ∣ ρ v ] ≤ exp ( − Ω ( τ ) ) . \Pr[(h,e)\in\operatorname{SINGLETON}_G\mid\rho_v]\le\exp(-\Omega(\tau)). Pr [( h , e ) ∈ SINGLETON G ∣ ρ v ] ≤ exp ( − Ω ( τ )) . Therefore, conditioned on extending ρ v \rho_v ρ v T T T e e e exp ( − Ω ( τ ) ) \exp(-\Omega(\tau)) exp ( − Ω ( τ ))
Now consider the entire collection of ordered lists { List ( ρ ) } ρ ∈ T \{\operatorname{List}(\rho)\}_{\rho\in T} { List ( ρ ) } ρ ∈ T ρ ∈ T \rho\in T ρ ∈ T j ∈ [ b ] j\in[b] j ∈ [ b ]
V j : = { ( v , e ) ∣ ρ is a path in T and ( v , e ) is the j th element of the list List ( ρ ) } . (2) V_j:=\{(v,e)\mid\rho\text{ is a path in }T\text{ and }(v,e)\text{ is the }j^{\text{th}}\text{ element of the list }\operatorname{List}(\rho)\}. \tag*{(2)} V j := {( v , e ) ∣ ρ is a path in T and ( v , e ) is the j th element of the list List ( ρ )} . (2) Note that although we have shown that along any single path ρ \rho ρ b b b V j V_j V j j t h j^{\mathrm{th}} j th ρ \rho ρ V j V_j V j v ∈ T v \in T v ∈ T E v E_v E v h h h ρ v \rho_v ρ v
E v : = { h ∈ H ∣ h extends ρ v } . E_v := \{h \in\mathcal{H} \mid h\text{ extends }\rho_v\}. E v := { h ∈ H ∣ h extends ρ v } . Claim 5. For every j ≤ b j \le b j ≤ b ( v , e ) , ( v ′ , e ′ ) ∈ V j (v,e),(v',e') \in V_j ( v , e ) , ( v ′ , e ′ ) ∈ V j E v E_v E v E v ′ E_{v'} E v ′
∑ ( v , e ) ∈ V j Pr [ E v ] ≤ 1. \sum_{(v,e)\in V_j} \Pr[E_v] \le1. ( v , e ) ∈ V j ∑ Pr [ E v ] ≤ 1. Proof. Let ( v , e ) ≠ ( v ′ , e ′ ) ∈ V j (v,e) \ne(v',e') \in V_j ( v , e ) = ( v ′ , e ′ ) ∈ V j ( v , e ) (v,e) ( v , e ) j t h j^{\mathrm{th}} j th List ( ρ ) \operatorname{List}(\rho) List ( ρ ) ( v ′ , e ′ ) (v',e') ( v ′ , e ′ ) j t h j^{\mathrm{th}} j th List ( ρ ′ ) \operatorname{List}(\rho') List ( ρ ′ ) ρ v \rho_v ρ v ρ v ′ \rho_{v'} ρ v ′ E v , E v ′ E_v,E_{v'} E v , E v ′ ρ v ′ \rho_{v'} ρ v ′ ρ v \rho_v ρ v ρ v \rho_v ρ v ρ v ′ \rho_{v'} ρ v ′ j j j List ( ρ ) \operatorname{List}(\rho) List ( ρ ) List ( ρ ′ ) \operatorname{List}(\rho') List ( ρ ′ ) j t h j^{\mathrm{th}} j th
Now fix j ∈ [ b ] j \in[b] j ∈ [ b ] ∑ ( v , e ) ∈ V j Pr [ E v ] ≤ 1 \sum_{(v,e)\in V_j}\Pr[E_v] \le1 ∑ ( v , e ) ∈ V j Pr [ E v ] ≤ 1 h h h j t h j^{\mathrm{th}} j th
∑ ( v , e ) ∈ V j Pr [ E v ] ⋅ Pr [ ( h , e ) ∈ Singleton G ∣ E v ] . \sum_{(v,e)\in V_j}\Pr[E_v]\cdot\Pr[(h,e)\in\operatorname{Singleton}_G\mid E_v]. ( v , e ) ∈ V j ∑ Pr [ E v ] ⋅ Pr [( h , e ) ∈ Singleton G ∣ E v ] . We can use Lemma 3 to bound each second term by exp ( − Ω ( τ ) ) \exp(-\Omega(\tau)) exp ( − Ω ( τ )) j ∈ [ b ] j \in[b] j ∈ [ b ] b ⋅ exp ( − Ω ( τ ) ) b\cdot\exp(-\Omega(\tau)) b ⋅ exp ( − Ω ( τ ))
Proof of the main lemma
Finally, we prove Lemma 3, that we restate here for convenience.
Lemma 3. Let G , e ∗ , ℓ , τ G,e^*,\ell,\tau G , e ∗ , ℓ , τ ρ \rho ρ e ≠ e ∗ e \ne e^* e = e ∗ ∣ fix ( ρ ) ∩ e ∣ ≤ 3 τ / 2 |\operatorname{fix}(\rho)\cap e|\le3\tau/2 ∣ fix ( ρ ) ∩ e ∣ ≤ 3 τ /2 ℓ ≥ 2.6 τ \ell\ge2.6\tau ℓ ≥ 2.6 τ ℓ = O ( τ ) \ell=O(\tau) ℓ = O ( τ )
Pr [ ( h , e ) ∈ Singleton G ∣ h extends ρ ] ≤ exp ( − Ω ( τ ) ) . \Pr[(h,e)\in\operatorname{Singleton}_G\mid h\text{ extends }\rho]\le\exp(-\Omega(\tau)). Pr [( h , e ) ∈ Singleton G ∣ h extends ρ ] ≤ exp ( − Ω ( τ )) . The key probabilistic fact we need here is McDiarmid’s inequality:
Theorem 6 ([56 ] ). Let f : Σ m → R f:\Sigma^m\to\mathbb{R} f : Σ m → R c c c x , x ′ ∈ Σ m x,x'\in\Sigma^m x , x ′ ∈ Σ m ∣ f ( x ) − f ( x ′ ) ∣ ≤ c |f(x)-f(x')|\le c ∣ f ( x ) − f ( x ′ ) ∣ ≤ c
Pr x ∼ Σ m [ ∣ f ( x ) − E [ f ( x ) ] ∣ ≥ λ ] ≤ 2 exp ( − λ 2 / ( c 2 m ) ) . \Pr_{x\sim\Sigma^m}[|f(x)-\mathbb{E}[f(x)]|\ge\lambda]\le2\exp(-\lambda^2/(c^2m)). x ∼ Σ m Pr [ ∣ f ( x ) − E [ f ( x )] ∣ ≥ λ ] ≤ 2 exp ( − λ 2 / ( c 2 m )) . Proof of Lemma 3. Let e = { u 1 , … , u ℓ } e=\{u_1,\ldots,u_\ell\} e = { u 1 , … , u ℓ } h ( u 1 ) , … , h ( u k ) h(u_1),\ldots,h(u_k) h ( u 1 ) , … , h ( u k ) ρ \rho ρ h ( 1 ) = ⋯ = h ( ℓ ) = ⊥ h(1)=\cdots=h(\ell)=\bot h ( 1 ) = ⋯ = h ( ℓ ) = ⊥ k ≤ 2.5 τ k\le2.5\tau k ≤ 2.5 τ 3 τ / 2 3\tau/2 3 τ /2 ρ \rho ρ τ \tau τ ρ \rho ρ [ ℓ ] [\ell] [ ℓ ] ρ ′ \rho' ρ ′
Then h ( u k + 1 ) , … , h ( u ℓ ) h(u_{k+1}),\ldots,h(u_\ell) h ( u k + 1 ) , … , h ( u ℓ ) [ τ ] ∪ { ⊥ } [\tau]\cup\{\bot\} [ τ ] ∪ { ⊥ } ρ \rho ρ D ⊆ [ τ ] D\subseteq[\tau] D ⊆ [ τ ] d d d i ∈ [ k ] i\in[k] i ∈ [ k ] ρ ′ ( u i ) = d \rho'(u_i)=d ρ ′ ( u i ) = d D D D τ / 4 \tau/4 τ /4 [ τ ] ∖ D [\tau]\setminus D [ τ ] ∖ D ⊥ \bot ⊥ h ( u 1 ) , … , h ( u k ) h(u_1),\ldots,h(u_k) h ( u 1 ) , … , h ( u k ) ∣ [ τ ] ∖ D ∣ ≤ 3 τ / 4 |[\tau]\setminus D|\le3\tau/4 ∣ [ τ ] ∖ D ∣ ≤ 3 τ /4 ⊥ \bot ⊥ ρ \rho ρ
We show that at least one label remains a singleton. Define f d ( x k + 1 , … , x ℓ ) f_d(x_{k+1},\ldots,x_\ell) f d ( x k + 1 , … , x ℓ ) d d d ρ ′ ( u 1 ) , … , ρ ′ ( u k ) , x k + 1 , … , x ℓ \rho'(u_1),\ldots,\rho'(u_k),x_{k+1},\ldots,x_\ell ρ ′ ( u 1 ) , … , ρ ′ ( u k ) , x k + 1 , … , x ℓ I d = { i ≤ k ∣ ρ ′ ( u i ) = d } I_d=\{i\le k\mid\rho'(u_i)=d\} I d = { i ≤ k ∣ ρ ′ ( u i ) = d }
Pr [ f d ( h ( u k + 1 ) , … , h ( u ℓ ) ) = 1 ] = { ( 1 − 1 / ( τ + 1 ) ) ℓ − k If ∣ I d ∣ = 1 ; ( ℓ − k ) / ( τ + 1 ) ⋅ ( 1 − 1 / ( τ + 1 ) ) ℓ − k − 1 If I d = ∅ . \Pr[f_d(h(u_{k+1}),\ldots,h(u_\ell))=1]=
\begin{cases}
(1-1/(\tau+1))^{\ell-k} & \text{If } |I_d|=1;\\
(\ell-k)/(\tau+1)\cdot(1-1/(\tau+1))^{\ell-k-1} & \text{If } I_d=\varnothing.
\end{cases} Pr [ f d ( h ( u k + 1 ) , … , h ( u ℓ )) = 1 ] = { ( 1 − 1/ ( τ + 1 ) ) ℓ − k ( ℓ − k ) / ( τ + 1 ) ⋅ ( 1 − 1/ ( τ + 1 ) ) ℓ − k − 1 If ∣ I d ∣ = 1 ; If I d = ∅ . In both cases the probability is exp ( − Θ ( ( ℓ − k ) / τ ) ) = Ω ( 1 ) \exp(-\Theta((\ell-k)/\tau))=\Omega(1) exp ( − Θ (( ℓ − k ) / τ )) = Ω ( 1 ) ℓ − k = Θ ( τ ) \ell-k=\Theta(\tau) ℓ − k = Θ ( τ )
Defining f = f 1 + ⋯ + f τ f=f_1+\cdots+f_\tau f = f 1 + ⋯ + f τ f f f h ( u i ) h(u_i) h ( u i ) E [ f ( h ( u k + 1 ) , … , h ( u ℓ ) ) ] = Ω ( τ ) \mathbb{E}[f(h(u_{k+1}),\ldots,h(u_\ell))]=\Omega(\tau) E [ f ( h ( u k + 1 ) , … , h ( u ℓ ))] = Ω ( τ ) Theorem 6 gives
Pr [ f ( h ( u k + 1 ) , … , h ( u ℓ ) ) = 0 ] ≤ exp ( − Ω ( ( τ / 4 ) 2 / ( ℓ − k ) ) ) = exp ( − Ω ( τ ) ) . \Pr[f(h(u_{k+1}),\ldots,h(u_\ell))=0]\le\exp(-\Omega((\tau/4)^2/(\ell-k)))=\exp(-\Omega(\tau)). Pr [ f ( h ( u k + 1 ) , … , h ( u ℓ )) = 0 ] ≤ exp ( − Ω (( τ /4 ) 2 / ( ℓ − k ))) = exp ( − Ω ( τ )) . PPAD containment
Recall that E ⊆ ( [ N ] r ) E \subseteq\binom{[N]}{r} E ⊆ ( r [ N ] ) r r r ϵ ∈ { ± 1 } E \epsilon\in\{\pm1\}^{E} ϵ ∈ { ± 1 } E I ∈ ( [ N ] ℓ ) I \in\binom{[N]}{\ell} I ∈ ( ℓ [ N ] ) ∑ e ∈ E I ϵ e = 0 \sum_{e\in E_I}\epsilon_e = 0 ∑ e ∈ E I ϵ e = 0 E I : = { e ∈ E ∣ e ⊇ I } E_I := \{e \in E \mid e \supseteq I\} E I := { e ∈ E ∣ e ⊇ I } E E E r r r e ↦ ϵ e e \mapsto\epsilon_e e ↦ ϵ e I I I σ I : E I → E I \sigma_I : E_I \to E_I σ I : E I → E I ϵ σ I ( e ) = − ϵ e \epsilon_{\sigma_I(e)}=-\epsilon_e ϵ σ I ( e ) = − ϵ e I I I e e e σ I ( e ) \sigma_I(e) σ I ( e ) ϵ e ∗ = 1 \epsilon_{e^*}=1 ϵ e ∗ = 1
Theorem 7. Let G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) E ⊆ ( [ N ] ℓ ) E \subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) ℓ = poly ( log N ) \ell=\operatorname{poly}(\log N) ℓ = poly ( log N ) E E E τ \tau τ Singleton G ∈ PPAD \operatorname{Singleton}_G \in\operatorname{PPAD} Singleton G ∈ PPAD
We reduce Singleton G \operatorname{Singleton}_G Singleton G τ \tau τ G G G [29 ] then immediately implies Singleton G ∈ PPAD \operatorname{Singleton}_G \in\operatorname{PPAD} Singleton G ∈ PPAD black-box model. Our proof does not formally rely on this theorem. We will show that efficient τ \tau τ
Polynomial encoding of Singleton G \operatorname{Singleton}_G Singleton G We define an unsatisfiable system of polynomials, P G \mathcal{P}_G P G h v , j h_{v,j} h v , j v ∈ [ N ] v \in[N] v ∈ [ N ] j ∈ [ w ] j \in[w] j ∈ [ w ] w = ⌈ log ( τ + 1 ) ⌉ w=\lceil\log(\tau+1)\rceil w = ⌈ log ( τ + 1 )⌉ h v , 1 , … , h v , w h_{v,1},\ldots,h_{v,w} h v , 1 , … , h v , w h ( v ) ∈ { ⊥ } ∪ [ τ ] h(v)\in\{\bot\}\cup[\tau] h ( v ) ∈ { ⊥ } ∪ [ τ ] [ τ ] [\tau] [ τ ] ⊥ \bot ⊥ h ∈ H h\in\mathcal{H} h ∈ H h i , j = 0 h_{i,j}=0 h i , j = 0 i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] j ∈ [ w ] j\in[w] j ∈ [ w ]
We need to represent the fact that ( h , e ) ∉ Singleton G (h,e)\notin\operatorname{Singleton}_G ( h , e ) ∈ / Singleton G { h v , j } v ∈ [ N ] , j ∈ [ w ] \{h_{v,j}\}_{v\in[N],j\in[w]} { h v , j } v ∈ [ N ] , j ∈ [ w ] e = { v 1 , … , v ℓ } e=\{v_1,\ldots,v_\ell\} e = { v 1 , … , v ℓ } ⊥ \bot ⊥ h ( v 1 ) , … , h ( v ℓ ) h(v_1),\ldots,h(v_\ell) h ( v 1 ) , … , h ( v ℓ ) β ∈ [ τ ] \beta\in[\tau] β ∈ [ τ ]
n β ( e ; h ) : = ∣ { v ∈ e ∣ h ( v ) = β } ∣ , n_\beta(e;h):=\left|\{v\in e\mid h(v)=\beta\}\right|, n β ( e ; h ) := ∣ { v ∈ e ∣ h ( v ) = β } ∣ , n β ( e ; h ) n_\beta(e;h) n β ( e ; h ) β \beta β
The function n β ( e ; h ) n_\beta(e;h) n β ( e ; h ) { h v , j } \{h_{v,j}\} { h v , j } [ h ( v ) = β ] [h(v)=\beta] [ h ( v ) = β ] h v , j h_{v,j} h v , j h ( v ) = β h(v)=\beta h ( v ) = β n β ( e ; h ) n_\beta(e;h) n β ( e ; h ) ∑ v ∈ e [ h ( v ) = β ] \sum_{v\in e}[h(v)=\beta] ∑ v ∈ e [ h ( v ) = β ] w w w
Now we define the following system of polynomial equations:
P G = { p e ( h ) = 0 ∣ e ∈ E ∖ { e ∗ } } , where p e ( h ) : = ∏ β ∈ [ τ ] ( 1 − ∑ v ∈ e [ h ( v ) = β ] ) . \mathcal{P}_G=\{p_e(h)=0\mid e\in E\setminus\{e^*\}\},\qquad\text{where}\quad p_e(h):=\prod_{\beta\in[\tau]}\left(1-\sum_{v\in e}[h(v)=\beta]\right). P G = { p e ( h ) = 0 ∣ e ∈ E ∖ { e ∗ }} , where p e ( h ) := β ∈ [ τ ] ∏ ( 1 − v ∈ e ∑ [ h ( v ) = β ] ) . Note that each p e p_e p e τ w \tau w τ w h v , j h_{v,j} h v , j 1 − ∑ v ∈ e [ h ( v ) = β ] 1-\sum_{v\in e}[h(v)=\beta] 1 − ∑ v ∈ e [ h ( v ) = β ] β \beta β
p e ( h ) ≠ 0 ⟺ no value in [ τ ] occurs exactly once . p_e(h)\ne0\quad\Longleftrightarrow\quad\text{no value in }[\tau]\text{ occurs exactly once}. p e ( h ) = 0 ⟺ no value in [ τ ] occurs exactly once . Unary Nullstellensatz and PPAD. Göös, Hollender, Jain, Maystre, Pires, Robere, and Tao [29 Lemma 5] prove that PPAD d t \operatorname{PPAD}^{\mathrm{dt}} PPAD dt Unary Nullstellensatz (uNS) proof. More precisely, suppose that a 1 , … , a M ∈ Z [ x 1 , … , x N ] a_1,\ldots,a_M\in\mathbb{Z}[x_1,\ldots,x_N] a 1 , … , a M ∈ Z [ x 1 , … , x N ] poly ( log N ) \operatorname{poly}(\log N) poly ( log N ) c i ∈ Z [ x 1 , … , x N ] c_i\in\mathbb{Z}[x_1,\ldots,x_N] c i ∈ Z [ x 1 , … , x N ] d 1 , … , d N ∈ Z [ x 1 , … , x N ] d_1,\ldots,d_N\in\mathbb{Z}[x_1,\ldots,x_N] d 1 , … , d N ∈ Z [ x 1 , … , x N ] ∑ i ∈ [ M ] a i ⋅ c i + ∑ i ∈ [ N ] ( x i 2 − x i ) d i = 1 \sum_{i\in[M]}a_i\cdot c_i+\sum_{i\in[N]}(x_i^2-x_i)d_i=1 ∑ i ∈ [ M ] a i ⋅ c i + ∑ i ∈ [ N ] ( x i 2 − x i ) d i = 1 a i c i a_i c_i a i c i c 1 , … , c M c_1,\ldots,c_M c 1 , … , c M
Lemma 8 ([29 Lemma 5] ). Let S : = { ( x , i ) ∈ { 0 , 1 } N × [ M ] ∣ a i ( x ) ≠ 0 } S:=\{(x,i)\in\{0,1\}^N\times[M]\mid a_i(x)\ne0\} S := {( x , i ) ∈ { 0 , 1 } N × [ M ] ∣ a i ( x ) = 0 } { a i } i ∈ [ M ] \{a_i\}_{i\in[M]} { a i } i ∈ [ M ] poly ( log N ) \operatorname{poly}(\log N) poly ( log N ) 2 poly ( log N ) 2^{\operatorname{poly}(\log N)} 2 poly ( l o g N ) S ∈ PPAD d t S\in\operatorname{PPAD}^{\mathrm{dt}} S ∈ PPAD dt 3
Totality of SingletonG _G G First we show that SingletonG _G G P G \mathcal{P}_G P G G _G G
Lemma 9 (Totality of SingletonG _G G Theorem 7 the system P G \mathcal{P}_G P G G _G G P G \mathcal{P}_G P G x 2 − x x^2-x x 2 − x x x x
1 = − ∑ e ∈ E ∖ { e ∗ } ε e p e . 1=-\sum_{e\in E\setminus\{e^*\}}\varepsilon_e p_e. 1 = − e ∈ E ∖ { e ∗ } ∑ ε e p e . Proof. Expand the τ \tau τ p e p_e p e
p e = ∑ B ⊆ [ τ ] ; κ ∈ e B ( − 1 ) ∣ B ∣ ∏ β ∈ B [ h ( κ β ) = β ] . p_e=\sum_{\substack{B\subseteq[\tau];\\ \kappa\in e_B}}(-1)^{|B|}\prod_{\beta\in B}[h(\kappa_\beta)=\beta]. p e = B ⊆ [ τ ] ; κ ∈ e B ∑ ( − 1 ) ∣ B ∣ β ∈ B ∏ [ h ( κ β ) = β ] . That is, each term specifies a subset B ⊆ [ τ ] B\subseteq[\tau] B ⊆ [ τ ] ∣ B ∣ |B| ∣ B ∣ κ \kappa κ e e e I I I
I : = { κ β ∣ β ∈ B } ⊆ [ N ] , ∣ I ∣ ≤ ∣ B ∣ ≤ τ . I:=\{\kappa_\beta\mid\beta\in B\}\subseteq[N],\qquad|I|\leq|B|\leq\tau. I := { κ β ∣ β ∈ B } ⊆ [ N ] , ∣ I ∣ ≤ ∣ B ∣ ≤ τ . If ∣ I ∣ < ∣ B ∣ |I|<|B| ∣ I ∣ < ∣ B ∣ p e p_e p e ∣ I ∣ = ∣ B ∣ |I|=|B| ∣ I ∣ = ∣ B ∣ ( − 1 ) ∣ B ∣ (-1)^{|B|} ( − 1 ) ∣ B ∣ e ⊇ I e\supseteq I e ⊇ I ∣ I ∣ ≤ τ |I|\leq\tau ∣ I ∣ ≤ τ τ \tau τ ∑ e ∈ E ε e p e \sum_{e\in E}\varepsilon_e p_e ∑ e ∈ E ε e p e ( − 1 ) ∣ B ∣ ⋅ ∑ e ⊇ I ε e = 0 (-1)^{|B|}\cdot\sum_{e\supseteq I}\varepsilon_e=0 ( − 1 ) ∣ B ∣ ⋅ ∑ e ⊇ I ε e = 0
On the other hand, for e ∗ = [ ℓ ] e^*=[\ell] e ∗ = [ ℓ ] n β ( e ∗ ; h ) = 0 n_\beta(e^*;h)=0 n β ( e ∗ ; h ) = 0 h ( v ) = ⊥ h(v)=\perp h ( v ) =⊥ v ∈ e ∗ v\in e^* v ∈ e ∗ n β ( e ∗ ; h ) n_\beta(e^*;h) n β ( e ∗ ; h ) p e ∗ ( h ) = 1 p_{e^*}(h)=1 p e ∗ ( h ) = 1 ε e ∗ = 1 \varepsilon_{e^*}=1 ε e ∗ = 1 p e ∗ ( h ) p_{e^*}(h) p e ∗ ( h ) 1 = − ∑ e ∈ E ∖ { e ∗ } ε e p e ( h ) 1=-\sum_{e\in E\setminus\{e^*\}}\varepsilon_ep_e(h) 1 = − ∑ e ∈ E ∖ { e ∗ } ε e p e ( h )
Now this implies that P G = { p e ( h ) ∣ e ∈ E ∖ { e ∗ } } \mathcal{P}_G=\{p_e(h)\mid e\in E\setminus\{e^*\}\} P G = { p e ( h ) ∣ e ∈ E ∖ { e ∗ }} h h h e ∈ E ∖ { e ∗ } e\in E\setminus\{e^*\} e ∈ E ∖ { e ∗ } p e ( h ) = 0 p_e(h)=0 p e ( h ) = 0 ∑ e ∈ E ∖ { e ∗ } ε e p e ( h ) = 0 \sum_{e\in E\setminus\{e^*\}}\varepsilon_ep_e(h)=0 ∑ e ∈ E ∖ { e ∗ } ε e p e ( h ) = 0
Thus, we have not only shown that P G \mathcal{P}_G P G ∑ e ∈ E ∖ { e ∗ } ε e p e = − 1 \sum_{e\in E\setminus\{e^*\}}\varepsilon_ep_e=-1 ∑ e ∈ E ∖ { e ∗ } ε e p e = − 1 ε e ∈ { ± 1 } \varepsilon_e\in\{\pm1\} ε e ∈ { ± 1 } p e p_e p e ( 1 + ℓ 2 ) τ (1+\ell^2)^\tau ( 1 + ℓ 2 ) τ e ∈ E e\in E e ∈ E poly ( ℓ ) \operatorname{poly}(\ell) poly ( ℓ ) ∣ E ∣ ( 1 + ℓ 2 ) τ ≤ 2 O ( ℓ log N + τ log ℓ ) = 2 polylog N |E|(1+\ell^2)^\tau\leq2^{O(\ell\log N+\tau\log\ell)}=2^{\operatorname{polylog}N} ∣ E ∣ ( 1 + ℓ 2 ) τ ≤ 2 O ( ℓ l o g N + τ l o g ℓ ) = 2 polylog N
Efficiency of inclusion. By Lemma 8 and Lemma 9, Singleton ∈ \in ∈ d t ^{\mathrm{dt}} dt τ \tau τ [29 ] exactly. Let us introduce the canonical PPAD-complete problem:
Definition 2. End-of-Line problem is defined with two arrays Succ, Pred ∈ [ N ] N \in[N]^N ∈ [ N ] N
1 1 1 1 ≠ 1 _1\ne1 1 = 1 1 = 1 _1=1 1 = 1 S u c c 1 ≠ 1 _{\mathrm{Succ}_1}\ne1 Succ 1 = 1
i ∈ [ N ] ∖ { 1 } i\in[N]\setminus\{1\} i ∈ [ N ] ∖ { 1 } P r e d i ≠ i _{\mathrm{Pred}_i}\ne i Pred i = i
i ∈ [ N ] i\in[N] i ∈ [ N ] S u c c i ≠ i _{\mathrm{Succ}_i}\ne i Succ i = i
Proof of Theorem 7 . We instantiate the proof of [29 Lemma 5] in our simpler case (the refutation simply adds the axiom polynomials with coefficients { ± 1 } \{\pm1\} { ± 1 } ( e , u ) (e,u) ( e , u ) e ∈ E e\in E e ∈ E u ∈ ( { ⊥ } ∪ e ) τ u\in(\{\perp\}\cup e)^\tau u ∈ ({ ⊥ } ∪ e ) τ m u : = ∏ i ∈ [ τ ] : u i ≠ ⊥ [ h ( u i ) = i ] m_u:=\prod_{i\in[\tau]:u_i\ne\perp}[h(u_i)=i] m u := ∏ i ∈ [ τ ] : u i = ⊥ [ h ( u i ) = i ] p e p_e p e [ h ( u i ) = i ] [h(u_i)=i] [ h ( u i ) = i ] ( e , u ) (e,u) ( e , u ) p e p_e p e c ( e , u ) : = ( − 1 ) ∣ { i ∣ u i ≠ ⊥ } ∣ c(e,u):=(-1)^{|\{i\mid u_i\ne\perp\}|} c ( e , u ) := ( − 1 ) ∣ { i ∣ u i = ⊥ } ∣ p e ( h ) p_e(h) p e ( h ) Figure 3 for an example.
Figure 3. An End-of-Line instance for G = ( [ 6 ] , E ) G=([6], E) G = ([ 6 ] , E ) E = { 123 , 234 , 345 , 135 , 156 , 456 , 246 , 126 } E = \{123, 234, 345, 135, 156, 456, 246, 126\} E = { 123 , 234 , 345 , 135 , 156 , 456 , 246 , 126 } e ∗ = 123 e^* = 123 e ∗ = 123 ϵ e = ( − 1 ) ∣ e ∩ { 4 , 5 , 6 } ∣ \epsilon_e = (-1)^{|e \cap\{4,5,6\}|} ϵ e = ( − 1 ) ∣ e ∩ { 4 , 5 , 6 } ∣ a b c = { a , b , c } abc = \{a,b,c\} ab c = { a , b , c } x v = [ h ( v ) = 1 ] x_v = [h(v) = 1] x v = [ h ( v ) = 1 ] y v = [ h ( v ) = 2 ] y_v = [h(v) = 2] y v = [ h ( v ) = 2 ] ⊥ \bot ⊥ A A A B h B_h B h ( e ∗ , ⊥ 2 ) (e^*, \bot^2) ( e ∗ , ⊥ 2 )
Monomial-preserving For ( e , u ) (e,u) ( e , u ) S S S ⊥ \perp ⊥ u u u τ \tau τ σ S : E S → E S \sigma_S:E_S\to E_S σ S : E S → E S e ⊇ S e\supseteq S e ⊇ S ε e = − ε σ S ( e ) \varepsilon_e=-\varepsilon_{\sigma_S(e)} ε e = − ε σ S ( e ) A ( e , u ) : = ( σ S ( e ) , u ) A(e,u):=(\sigma_S(e),u) A ( e , u ) := ( σ S ( e ) , u )
Hyperedge-preserving. Fix a hyperedge e ∈ E e \in E e ∈ E ( e , u ) (e,u) ( e , u ) m u ( h ) = 1 m_u(h)=1 m u ( h ) = 1 B h ( e , u ) : = ( e , u ′ ) B_h(e,u):=(e,u') B h ( e , u ) := ( e , u ′ ) m u m_u m u m u ′ m_{u'} m u ′ p e ( h ) p_e(h) p e ( h ) B h ( e , u ′ ) = ( e , u ) B_h(e,u')=(e,u) B h ( e , u ′ ) = ( e , u ) B h B_h B h u u u m u ∈ p e m_u \in p_e m u ∈ p e ∏ i ∈ [ τ ] ( { ⊥ } ∪ { v ∈ e ∣ h ( v ) = i } ) \prod_{i\in[\tau]}(\{\bot\}\cup\{v\in e\mid h(v)=i\}) ∏ i ∈ [ τ ] ({ ⊥ } ∪ { v ∈ e ∣ h ( v ) = i }) m u m_u m u B h ( e , u ) = ⊥ B_h(e,u)=\bot B h ( e , u ) = ⊥ B h B_h B h + 1 +1 + 1 − 1 -1 − 1 p e ( h ) ≠ 0 p_e(h)\ne0 p e ( h ) = 0
Finally we are ready to define successors and predecessors using the matching A A A B h B_h B h m u m_u m u h h h ( e , u ) (e,u) ( e , u ) ϵ e ⋅ c ( e , u ) ⋅ m u ( h ) = 1 \epsilon_e\cdot c(e,u)\cdot m_u(h)=1 ϵ e ⋅ c ( e , u ) ⋅ m u ( h ) = 1 Succ e , u : = A ( e , u ) \operatorname{Succ}_{e,u}:=A(e,u) Succ e , u := A ( e , u ) Pred e , u : = B h ( e , u ) \operatorname{Pred}_{e,u}:=B_h(e,u) Pred e , u := B h ( e , u ) B h ( e , u ) = ⊥ B_h(e,u)=\bot B h ( e , u ) = ⊥ Pred e , u = ( e , u ) \operatorname{Pred}_{e,u}=(e,u) Pred e , u = ( e , u ) ϵ e ⋅ c ( e , u ) ⋅ m u ( h ) = − 1 \epsilon_e\cdot c(e,u)\cdot m_u(h)=-1 ϵ e ⋅ c ( e , u ) ⋅ m u ( h ) = − 1 Succ \operatorname{Succ} Succ Pred \operatorname{Pred} Pred
By the definition of the matchings A A A B h B_h B h ( e , u ) (e,u) ( e , u ) m u ( h ) = 1 m_u(h)=1 m u ( h ) = 1 p e ( h ) ≠ 0 p_e(h)\ne0 p e ( h ) = 0 ( e ∗ , ⊥ τ ) (e^*,\bot^\tau) ( e ∗ , ⊥ τ )
Construction of the graph
In this section, we construct G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E )
Theorem 10. Suppose ℓ \ell ℓ N = 2 poly ( ℓ ) N=2^{\operatorname{poly}(\ell)} N = 2 poly ( ℓ ) G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) E ⊆ ( [ N ] ℓ ) E\subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] )
( 3 τ / 2 , exp ( ( log N ) Ω ( 1 ) ) , exp ( o ( ℓ ) ) ) (3\tau/2,\exp((\log N)^{\Omega(1)}),\exp(o(\ell))) ( 3 τ /2 , exp (( log N ) Ω ( 1 ) ) , exp ( o ( ℓ )))
efficiently τ \tau τ
every e ∈ E ∖ { e ∗ } e\in E\setminus\{e^*\} e ∈ E ∖ { e ∗ } ∣ e ∩ e ∗ ∣ ≤ τ |e\cap e^*|\le\tau ∣ e ∩ e ∗ ∣ ≤ τ
where τ = 3 ℓ / 8 \tau=3\ell/8 τ = 3 ℓ /8
The code. The construction of G G G [ N ] [N] [ N ] [ ℓ ] × Γ [\ell]\times\Gamma [ ℓ ] × Γ c ∈ Γ ℓ c\in\Gamma^\ell c ∈ Γ ℓ e c : = { ( i , c i ) ∣ i ∈ [ ℓ ] } e_c:=\{(i,c_i)\mid i\in[\ell]\} e c := {( i , c i ) ∣ i ∈ [ ℓ ]} 0 ℓ 0^\ell 0 ℓ e ∗ = e 0 ℓ = [ ℓ ] e^*=e_{0^\ell}=[\ell] e ∗ = e 0 ℓ = [ ℓ ]
Then well-spreadness of E E E C C C C ⊆ Γ ℓ C \subseteq\Gamma^\ell C ⊆ Γ ℓ ( δ , a , b ) (\delta,a,b) ( δ , a , b ) S 1 , … , S ℓ ⊂ Γ S_1,\ldots,S_\ell\subset\Gamma S 1 , … , S ℓ ⊂ Γ ∣ S i ∣ ≤ a |S_i| \le a ∣ S i ∣ ≤ a ( c 1 , … , c ℓ ) ∈ C (c_1,\ldots,c_\ell) \in C ( c 1 , … , c ℓ ) ∈ C ∣ { i ∈ [ ℓ ] ∣ c i ∈ S i } ∣ ≥ ( 1 − δ ) ℓ |\{i \in[\ell] \mid c_i \in S_i\}| \ge(1-\delta)\ell ∣ { i ∈ [ ℓ ] ∣ c i ∈ S i } ∣ ≥ ( 1 − δ ) ℓ b b b
Claim 11. If C ⊆ Γ ℓ C \subseteq\Gamma^\ell C ⊆ Γ ℓ ( δ , a , b ) (\delta,a,b) ( δ , a , b ) E : = { e c ∣ c ∈ C } E := \{e_c \mid c \in C\} E := { e c ∣ c ∈ C } ( ( 1 − δ ) ℓ , a , b ) ((1-\delta)\ell,a,b) (( 1 − δ ) ℓ , a , b )
In order to verify the τ \tau τ C C C F \mathbb{F} F ∣ F ∣ = n + 1 |\mathbb{F}|=n+1 ∣ F ∣ = n + 1 γ ∈ F ∗ \gamma\in\mathbb{F}^* γ ∈ F ∗
ReedSolomon F , γ , d : = { c ∈ F n ∣ c i = f ( γ i − 1 ) where f ∈ F [ x ] with deg ( f ) ≤ d } , \operatorname{ReedSolomon}_{\mathbb{F},\gamma,d} := \{c \in\mathbb{F}^n \mid c_i=f(\gamma^{i-1}) \text{ where } f \in\mathbb{F}[x] \text{ with } \deg(f) \le d\}, ReedSolomon F , γ , d := { c ∈ F n ∣ c i = f ( γ i − 1 ) where f ∈ F [ x ] with deg ( f ) ≤ d } , FoldedRS F , γ , d m : = { ( ( c 1 , … , c m ) , ( c m + 1 , … , c 2 m ) , … , ( c n − m + 1 , … , c n ) ) ∣ c ∈ ReedSolomon F , γ , d } . \operatorname{FoldedRS}^{m}_{\mathbb{F},\gamma,d} := \{((c_1,\ldots,c_m),(c_{m+1},\ldots,c_{2m}),\ldots,(c_{n-m+1},\ldots,c_n)) \mid c \in\operatorname{ReedSolomon}_{\mathbb{F},\gamma,d}\}. FoldedRS F , γ , d m := {(( c 1 , … , c m ) , ( c m + 1 , … , c 2 m ) , … , ( c n − m + 1 , … , c n )) ∣ c ∈ ReedSolomon F , γ , d } . The following fact is a specialization of [Rud07, Section 3.6] used (with slightly different parameters) in [YZ24].
Corollary 12. Let ℓ \ell ℓ 4 4 4 Γ = F ℓ 2 ℓ − 1 \Gamma=\mathbb{F}_{\ell^2}^{\ell-1} Γ = F ℓ 2 ℓ − 1 FoldedRS F ℓ 2 , γ , 3 ℓ ( ℓ − 1 ) / 8 ℓ − 1 ⊆ Γ ℓ + 1 \operatorname{FoldedRS}^{\ell-1}_{\mathbb{F}_{\ell^2},\gamma,3\ell(\ell-1)/8} \subseteq\Gamma^{\ell+1} FoldedRS F ℓ 2 , γ , 3 ℓ ( ℓ − 1 ) /8 ℓ − 1 ⊆ Γ ℓ + 1 ( 9 / 16 , ℓ ℓ / 4 , ℓ 2 ℓ ) (9/16,\ell^{\ell/4},\ell^{2\sqrt{\ell}}) ( 9/16 , ℓ ℓ /4 , ℓ 2 ℓ )
We are now ready to prove the theorem.
Proof of Theorem 10 . By applying Corollary 12 we get Γ = F ℓ 2 ℓ − 1 \Gamma=\mathbb{F}_{\ell^2}^{\ell-1} Γ = F ℓ 2 ℓ − 1 C ′ : = FoldedRS F ℓ 2 , γ , 3 ℓ ( ℓ − 1 ) / 8 ℓ − 1 ⊆ Γ ℓ + 1 C' := \operatorname{FoldedRS}^{\ell-1}_{\mathbb{F}_{\ell^2},\gamma,3\ell(\ell-1)/8} \subseteq\Gamma^{\ell+1} C ′ := FoldedRS F ℓ 2 , γ , 3 ℓ ( ℓ − 1 ) /8 ℓ − 1 ⊆ Γ ℓ + 1 ( 9 / 16 , ℓ ℓ / 4 , ℓ 2 ℓ ) (9/16,\ell^{\ell/4},\ell^{2\sqrt{\ell}}) ( 9/16 , ℓ ℓ /4 , ℓ 2 ℓ ) C : = { ( c 1 , … , c ℓ ) ∣ ( c 1 , … , c ℓ + 1 ) ∈ C ′ } C := \{(c_1,\ldots,c_\ell) \mid(c_1,\ldots,c_{\ell+1}) \in C'\} C := {( c 1 , … , c ℓ ) ∣ ( c 1 , … , c ℓ + 1 ) ∈ C ′ } C ′ C' C ′ C ′ C' C ′ C C C 1 − ( 1 − 9 / 16 ) ( ℓ + 1 ) / ℓ = 9 / 16 − 7 / ( 16 ℓ ) 1-(1-9/16)(\ell+1)/\ell= 9/16-7/(16\ell) 1 − ( 1 − 9/16 ) ( ℓ + 1 ) / ℓ = 9/16 − 7/ ( 16 ℓ ) Claim 11 we have that E C : = { e c ∣ c ∈ C } E_C := \{e_c \mid c \in C\} E C := { e c ∣ c ∈ C } ( 7 ℓ / 16 + O ( 1 ) , ℓ ℓ / 4 , ℓ 2 ℓ ) (7\ell/16+O(1),\ell^{\ell/4},\ell^{2\sqrt{\ell}}) ( 7 ℓ /16 + O ( 1 ) , ℓ ℓ /4 , ℓ 2 ℓ ) 3 τ / 2 = 9 ℓ / 16 ≥ 7 ℓ / 16 + O ( 1 ) 3\tau/2=9\ell/16 \ge7\ell/16+O(1) 3 τ /2 = 9 ℓ /16 ≥ 7 ℓ /16 + O ( 1 ) ℓ \ell ℓ
Let us check the distance property of E C E_C E C e ≠ e ′ ∈ E C e \ne e' \in E_C e = e ′ ∈ E C c c c c ′ c' c ′ C C C ∣ e ∩ e ′ ∣ ≤ ∣ { i ∈ [ ℓ ] ∣ c i = c i ′ } ∣ ≤ d / m = τ |e \cap e'| \le|\{i \in[\ell] \mid c_i=c'_i\}| \le d/m=\tau ∣ e ∩ e ′ ∣ ≤ ∣ { i ∈ [ ℓ ] ∣ c i = c i ′ } ∣ ≤ d / m = τ > d >d > d c = c ′ c=c' c = c ′
Finally, we establish efficient τ \tau τ E C E_C E C x = γ m ℓ + 1 ∈ F ℓ 2 x=\gamma^{m\ell+1}\in\mathbb{F}_{\ell^2} x = γ m ℓ + 1 ∈ F ℓ 2 κ : F ℓ 2 → { ± 1 } \kappa:\mathbb{F}_{\ell^2}\to\{\pm1\} κ : F ℓ 2 → { ± 1 } ∑ y ∈ F ℓ 2 κ ( y ) = 0 \sum_{y\in\mathbb{F}_{\ell^2}}\kappa(y)=0 ∑ y ∈ F ℓ 2 κ ( y ) = 0 e e e p e p_e p e ϵ e : = κ ( p e ( x ) ) \epsilon_e:=\kappa(p_e(x)) ϵ e := κ ( p e ( x )) R ∈ ( [ ℓ ] × Γ < τ ) R\in\binom{[\ell]\times\Gamma}{<\tau} R ∈ ( < τ [ ℓ ] × Γ ) ∣ R ∣ < τ |R|<\tau ∣ R ∣ < τ ∑ e ⊇ R ϵ e = 0 \sum_{e\supseteq R}\epsilon_e=0 ∑ e ⊇ R ϵ e = 0 R R R R R R R R R { i } × Γ \{i\}\times\Gamma { i } × Γ e ⊇ R e\supseteq R e ⊇ R p e p_e p e τ m = d \tau m=d τ m = d p e ( x ) = y p_e(x)=y p e ( x ) = y y ∈ F ℓ 2 y\in\mathbb{F}_{\ell^2} y ∈ F ℓ 2 p e p_e p e q y q_y q y y y y ∑ e ⊇ R ϵ e = ∑ y ∈ F ℓ 2 κ ( y ) = 0 \sum_{e\supseteq R}\epsilon_e=\sum_{y\in\mathbb{F}_{\ell^2}}\kappa(y)=0 ∑ e ⊇ R ϵ e = ∑ y ∈ F ℓ 2 κ ( y ) = 0
In order to show that there is an efficient involution that matches the edges of opposite signs, choose κ ( y ) : = ( − 1 ) \kappa(y):=(-1) κ ( y ) := ( − 1 ) y y y e e e R R R y = p e ( x ) y=p_e(x) y = p e ( x ) y ′ y' y ′ y y y e ′ e' e ′ p e ′ ( x ) = y ′ p_{e'}(x)=y' p e ′ ( x ) = y ′ d d d R R R
Now let us verify τ \tau τ R ∈ ( [ ℓ ] × Γ ≤ τ ) R\in\binom{[\ell]\times\Gamma}{\le\tau} R ∈ ( ≤ τ [ ℓ ] × Γ ) R R R { i } × Γ \{i\}\times\Gamma { i } × Γ I : = { i ∈ [ ℓ ] ∣ R ∩ ( { i } × Γ ) ≠ ∅ } I:=\{i\in[\ell]\mid R\cap(\{i\}\times\Gamma)\ne\varnothing\} I := { i ∈ [ ℓ ] ∣ R ∩ ({ i } × Γ ) = ∅ } I ′ ⊇ I I'\supseteq I I ′ ⊇ I τ \tau τ σ R ( e ) : = σ R ′ ( e ) \sigma_R(e):=\sigma_{R'}(e) σ R ( e ) := σ R ′ ( e ) R ′ : = ( I ′ × Γ ) ∩ e R':=(I'\times\Gamma)\cap e R ′ := ( I ′ × Γ ) ∩ e
Proof of Corollary 12 We use the following fact.
Fact 2 (restatement of [YZ24, Lemma 4.3], originally from [Rud07, Section 3.6]). Suppose m m m n = ∣ F ∣ − 1 n=|\mathbb{F}|-1 n = ∣ F ∣ − 1 α , β \alpha,\beta α , β s ≤ m s\le m s ≤ m δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 )
( 1 − δ ) n m ≥ ( 1 + s β ) ⋅ ( n α s ) 1 / ( s + 1 ) m − s + 1 ( β + s ) ( n α d ) 1 / ( s + 1 ) < ∣ F ∣ . \frac{(1-\delta)n}{m} \ge\left(1+\frac{s}{\beta}\right)\cdot\frac{(n\alpha^s)^{1/(s+1)}}{m-s+1}
\qquad
(\beta+s)\left(\frac{n\alpha}{d}\right)^{1/(s+1)}<|\mathbb{F}|. m ( 1 − δ ) n ≥ ( 1 + β s ) ⋅ m − s + 1 ( n α s ) 1/ ( s + 1 ) ( β + s ) ( d n α ) 1/ ( s + 1 ) < ∣ F ∣. Then FoldedRS F , γ , d m \operatorname{FoldedRS}^{m}_{\mathbb{F},\gamma,d} FoldedRS F , γ , d m ( δ , α , ∣ F ∣ s ) (\delta,\alpha,|\mathbb{F}|^s) ( δ , α , ∣ F ∣ s )
Proof of Corollary 12. Instantiate Fact 2 with the following parameters:
∣ F ∣ = ℓ 2 ; m = ℓ − 1 ; τ = 3 ℓ / 8 ; s = ℓ ; β = ℓ ; d = τ m . |F| = \ell^2;\quad m = \ell- 1;\quad\tau= 3\ell/8;\quad s = \sqrt{\ell};\quad\beta= \ell;\quad d = \tau m. ∣ F ∣ = ℓ 2 ; m = ℓ − 1 ; τ = 3 ℓ /8 ; s = ℓ ; β = ℓ ; d = τ m . Then for δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) α ∈ Z > 0 \alpha\in\mathbb{Z}_{>0} α ∈ Z > 0
( 1 − δ ) ≥ 3 / 8 ( 1 + o ( 1 ) ) α 1 / ( 1 + ℓ ) (1-\delta) \geq3/8(1+o(1))\alpha^{1/(1+\sqrt{\ell})} ( 1 − δ ) ≥ 3/8 ( 1 + o ( 1 )) α 1/ ( 1 + ℓ ) ( 1 + o ( 1 ) ) ( 8 α / 3 ) 1 / ( 1 + ℓ ) < ℓ , (1+o(1))(8\alpha/3)^{1/(1+\sqrt{\ell})} < \ell, ( 1 + o ( 1 )) ( 8 α /3 ) 1/ ( 1 + ℓ ) < ℓ , for the conclusion of Fact 2 to hold. Setting α = ℓ ℓ 1 / 4 \alpha= \ell^{\ell^{1/4}} α = ℓ ℓ 1/4 δ = 9 / 16 \delta= 9/16 δ = 9/16
Assembling the proof of Theorem 1
Proof of Theorem 1. Let ℓ \ell ℓ Theorem 10 , with parameters N = ℓ ∣ Γ ∣ = ℓ 2 ℓ − 1 N = \ell|\Gamma| = \ell^{2\ell-1} N = ℓ ∣Γ∣ = ℓ 2 ℓ − 1 τ = 3 ℓ / 8 \tau= 3\ell/8 τ = 3 ℓ /8 a = ℓ ℓ 1 / 4 a = \ell^{\ell^{1/4}} a = ℓ ℓ 1/4 b = ℓ 2 ℓ b = \ell^{2\sqrt{\ell}} b = ℓ 2 ℓ a a a Singleton G \operatorname{Singleton}_{G} Singleton G
O ( b ) exp ( − Ω ( τ ) ) = exp ( O ( ℓ log ℓ ) − Ω ( ℓ ) ) = exp ( − Ω ( ℓ ) ) . O(b)\exp(-\Omega(\tau)) = \exp(O(\sqrt{\ell}\log\ell)-\Omega(\ell)) = \exp(-\Omega(\ell)). O ( b ) exp ( − Ω ( τ )) = exp ( O ( ℓ log ℓ ) − Ω ( ℓ )) = exp ( − Ω ( ℓ )) . Since log N = Θ ( ℓ log ℓ ) \log N = \Theta(\ell\log\ell) log N = Θ ( ℓ log ℓ ) exp ( ( log N ) o ( 1 ) ) \exp((\log N)^{o(1)}) exp (( log N ) o ( 1 ) ) exp ( − ( log N ) Ω ( 1 ) ) \exp(-(\log N)^{\Omega(1)}) exp ( − ( log N ) Ω ( 1 ) ) τ \tau τ ℓ = poly ( log N ) \ell= \operatorname{poly}(\log N) ℓ = poly ( log N ) Singleton G ∈ PPAD \operatorname{Singleton}_{G} \in\operatorname{PPAD} Singleton G ∈ PPAD Theorem 7 .
Set Σ = { ⊥ } ∪ [ τ ] \Sigma= \{\bot\} \cup[\tau] Σ = { ⊥ } ∪ [ τ ] ( u , e ) ∈ F N (u,e) \in F_N ( u , e ) ∈ F N ( h u , e ) ∈ Singleton G (h_u,e) \in\operatorname{Singleton}_{G} ( h u , e ) ∈ Singleton G h u ( i ) = ⊥ h_u(i) = \bot h u ( i ) = ⊥ i ∈ [ ℓ ] i \in[\ell] i ∈ [ ℓ ] h u ( i ) = u i h_u(i) = u_i h u ( i ) = u i F N ∈ PPAD F_N \in\operatorname{PPAD} F N ∈ PPAD u ∈ Σ N u \in\Sigma^N u ∈ Σ N h u ∈ H h_u \in\mathcal{H} h u ∈ H u 1 , … , u ℓ u_1,\ldots,u_\ell u 1 , … , u ℓ F N F_N F N
Corollary: EoPL is not in FP
We will use the following claim that allows us to combine two TFNP search problems. The proof is straightforward.
Claim 13. Let F = { F N ⊆ Σ N × O } F = \{F_N \subseteq\Sigma^N \times\mathcal{O}\} F = { F N ⊆ Σ N × O } G = { G N ⊆ Σ N × O ′ } G = \{G_N \subseteq\Sigma^N \times\mathcal{O}'\} G = { G N ⊆ Σ N × O ′ } H = { H N ⊆ Σ N × ( O ∪ O ′ ) } H = \{H_N \subseteq\Sigma^N \times(\mathcal{O} \cup\mathcal{O}')\} H = { H N ⊆ Σ N × ( O ∪ O ′ )}
( u , v ) ∈ H N ⟺ ( u , v ) ∈ F N or ( u , v ) ∈ G N . (u,v) \in H_N \Longleftrightarrow(u,v) \in F_N \text{ or } (u,v) \in G_N. ( u , v ) ∈ H N ⟺ ( u , v ) ∈ F N or ( u , v ) ∈ G N . Then,
H H H F F F G G G
If any depth-q q q F F F G G G ϵ F \epsilon_F ϵ F ϵ G \epsilon_G ϵ G u ∼ Σ N u \sim\Sigma^N u ∼ Σ N q q q H H H ϵ F + ϵ G \epsilon_F + \epsilon_G ϵ F + ϵ G u ∼ Σ N u \sim\Sigma^N u ∼ Σ N
The following is a direct corollary from the hardness of PPAD (Theorem 1), the hardness of PLS ([BG20])4 PPAD ∩ PLS = EoPL \operatorname{PPAD} \cap\operatorname{PLS} = \operatorname{EoPL} PPAD ∩ PLS = EoPL Claim 13 . We note that ϵ PLS \epsilon_{\operatorname{PLS}} ϵ PLS [7 Theorems 36 and 43] is o ( 1 ) o(1) o ( 1 )
Corollary 14. There exists a TFNP search problem F = { F N ⊆ Σ N × O } F = \{F_N \subseteq\Sigma^N \times\mathcal{O}\} F = { F N ⊆ Σ N × O } EoPL \operatorname{EoPL} EoPL T T T exp ( ( log N ) o ( 1 ) ) \exp((\log N)^{o(1)}) exp (( log N ) o ( 1 ) ) F F F
Pr u ∼ Σ N [ ( u , T ( u ) ) ∈ F N ] = o ( 1 ) . \Pr_{u \sim\Sigma^N}[(u,T(u)) \in F_N] = o(1). u ∼ Σ N Pr [( u , T ( u )) ∈ F N ] = o ( 1 ) . In particular, EoPL ̸ ⊆ ROM FP \operatorname{EoPL} \not\subseteq_{\operatorname{ROM}} \operatorname{FP} EoPL ⊆ ROM FP
Efficient search for UEoPL in the black-box ROM
In this section we show that UEoPL is easy in the random oracle model: every instance that is generated from the oracle by shallow decision trees can be solved, with high probability over the oracle, by a shallow decision tree. We use the definition of UEoPL from [29 Section 3.2] , which we reproduce here.
Definition 3 (UEoPLN _N N [29 Section 3.2] ). Let N ≥ 2 N \ge2 N ≥ 2 Succ u ∈ [ N ] ∪ { ⊥ } \operatorname{Succ}_u \in[N] \cup\{\perp\} Succ u ∈ [ N ] ∪ { ⊥ } u ∈ [ N ] × [ N ] u \in[N] \times[N] u ∈ [ N ] × [ N ] Pred u ∈ [ N ] ∪ { ⊥ } \operatorname{Pred}_u \in[N] \cup\{\perp\} Pred u ∈ [ N ] ∪ { ⊥ } u ∈ { 2 , … , N } × [ N ] u \in\{2,\ldots,N\} \times[N] u ∈ { 2 , … , N } × [ N ] ( i , j ) ∈ [ N − 1 ] × [ N ] (i,j) \in[N-1] \times[N] ( i , j ) ∈ [ N − 1 ] × [ N ] Succ i j = k ≠ ⊥ \operatorname{Succ}_{ij}=k \ne\perp Succ ij = k = ⊥ Pred i + 1 , k = j \operatorname{Pred}_{i+1,k}=j Pred i + 1 , k = j ( i , j ) ∈ { N } × [ N ] (i,j) \in\{N\} \times[N] ( i , j ) ∈ { N } × [ N ] Succ i j ≠ ⊥ \operatorname{Succ}_{ij} \ne\perp Succ ij = ⊥ u u u u u u u u u ( i , j ) (i,j) ( i , j ) i < N i<N i < N ( i , j ) (i,j) ( i , j )
( 1 , 1 ) (1,1) ( 1 , 1 ) ( 1 , 1 ) (1,1) ( 1 , 1 )
( N , j ) (N,j) ( N , j ) ( N , j ) (N,j) ( N , j )
( i , j ) (i,j) ( i , j ) ( i , j ) (i,j) ( i , j )
( i , j ) (i,j) ( i , j ) ( i , j ) ≠ ( 1 , 1 ) (i,j) \ne(1,1) ( i , j ) = ( 1 , 1 ) ( i , j ) (i,j) ( i , j )
( i , j ) (i,j) ( i , j ) ( i , j ′ ) (i,j') ( i , j ′ ) j ≠ j ′ j \ne j' j = j ′
Formally, UEoPLN _N N ( x , z ) (x,z) ( x , z ) x x x z z z x x x x x x instance and z z z solution of x x x
Here the successor Succ v = k ≠ ⊥ \operatorname{Succ}_v=k \ne\perp Succ v = k = ⊥ v = ( i , j ) v=(i,j) v = ( i , j ) i < N i<N i < N ( i + 1 , k ) (i+1,k) ( i + 1 , k ) v v v ( 1 , 1 ) (1,1) ( 1 , 1 ) ( 1 , 1 ) (1,1) ( 1 , 1 )
A proper sink u = ( i , j ) u=(i,j) u = ( i , j ) i > 1 i>1 i > 1 Pred u = p ≠ ⊥ \operatorname{Pred}_u=p \ne\perp Pred u = p = ⊥ Succ i − 1 , p = j \operatorname{Succ}_{i-1,p}=j Succ i − 1 , p = j u u u
Instances in the random oracle model. An instance is generated from the oracle u ∈ { 0 , 1 } N u \in\{0,1\}^{N} u ∈ { 0 , 1 } N ω \omega ω Succ v \operatorname{Succ}_v Succ v Pred v \operatorname{Pred}_v Pred v ω ( u ) \omega(u) ω ( u ) u u u [ N ] ∪ { ⊥ } [N] \cup\{\perp\} [ N ] ∪ { ⊥ } q q q ω \omega ω
Theorem 15. Let N ≥ 2 N \ge2 N ≥ 2 q ≥ 1 q \ge1 q ≥ 1 ω \omega ω N _N N q q q T T T poly ( q ) ⋅ log N \operatorname{poly}(q) \cdot\log N poly ( q ) ⋅ log N
Pr u ∼ { 0 , 1 } N [ ( ω ( u ) , T ( u ) ) ∈ U E o P L N ] ≥ 2 3 . \Pr_{u \sim\{0,1\}^{N}}\left[(\omega(u),T(u)) \in\mathrm{UEoPL}_N\right] \ge\frac{2}{3}. u ∼ { 0 , 1 } N Pr [ ( ω ( u ) , T ( u )) ∈ UEoPL N ] ≥ 3 2 . Moreover, for every u ∈ { 0 , 1 } N u \in\{0,1\}^{N} u ∈ { 0 , 1 } N T ( u ) T(u) T ( u ) ω ( u ) \omega(u) ω ( u )
Remark on upper bounds in the decision tree setting. Theorem 15 bounds the number of oracle queries, not the computation: the tree T T T [19 ] .
Restrictions. A restriction ρ \rho ρ cube ( ρ ) ⊆ { 0 , 1 } N \operatorname{cube}(\rho) \subseteq\{0,1\}^{N} cube ( ρ ) ⊆ { 0 , 1 } N ρ \rho ρ Pr ρ \Pr_{\rho} Pr ρ E ρ \mathbb{E}_{\rho} E ρ u ∼ cube ( ρ ) u \sim\operatorname{cube}(\rho) u ∼ cube ( ρ ) cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) ρ \rho ρ
Decision tree families. Throughout, a family of decision trees f = ( f y ) y ∈ Y f=(f_y)_{y\in Y} f = ( f y ) y ∈ Y f y : { 0 , 1 } N → { 0 , 1 } f_y:\{0,1\}^{N}\to\{0,1\} f y : { 0 , 1 } N → { 0 , 1 } y ∈ Y y\in Y y ∈ Y u u u f y ( u ) = 1 f_y(u)=1 f y ( u ) = 1 D : { 0 , 1 } N → Y ∪ { f a i l } D:\{0,1\}^{N}\to Y\cup\{\mathrm{fail}\} D : { 0 , 1 } N → Y ∪ { fail } y ∈ Y y\in Y y ∈ Y u u u y y y f y f_y f y u u u f f f y y y
The proof of Theorem 15 relies on the following lemma, which does not refer to UEoPL.
Lemma 16. For every q ≥ 1 q \ge1 q ≥ 1 a = O ( q 2 ) a = O(q^2) a = O ( q 2 ) η = Θ ( 1 / q ) \eta= \Theta(1/q) η = Θ ( 1/ q ) f = ( f y ) y ∈ Y f = (f_y)_{y \in Y} f = ( f y ) y ∈ Y f y : { 0 , 1 } N → { 0 , 1 } f_y : \{0,1\}^{N} \to\{0,1\} f y : { 0 , 1 } N → { 0 , 1 } q q q D : { 0 , 1 } N → Y ∪ { f a i l } D : \{0,1\}^{N} \to Y \cup\{\mathrm{fail}\} D : { 0 , 1 } N → Y ∪ { fail } t t t
Pr u ∼ { 0 , 1 } N [ f accepts D ( u ) on u ] ≥ 1 − η . \Pr_{u \sim\{0,1\}^{N}}[f\text{ accepts }D(u)\text{ on }u] \ge1-\eta. u ∼ { 0 , 1 } N Pr [ f accepts D ( u ) on u ] ≥ 1 − η . Then at least one of the following holds.
There is a decision tree T 1 : { 0 , 1 } N → Y ∪ { f a i l } T_1 : \{0,1\}^{N} \to Y \cup\{\mathrm{fail}\} T 1 : { 0 , 1 } N → Y ∪ { fail } a a a Pr u [ T 1 ( u ) ≠ f a i l ] ≥ 1 / 2 \Pr_u[T_1(u) \ne\mathrm{fail}] \ge1/2 Pr u [ T 1 ( u ) = fail ] ≥ 1/2 T 1 T_1 T 1 T 1 ( u ) T_1(u) T 1 ( u ) u u u T 1 ( u ) ≠ f a i l T_1(u) \ne\mathrm{fail} T 1 ( u ) = fail
There is a decision tree T 2 : { 0 , 1 } N → ( Y 2 ) ∪ { f a i l } T_2 : \{0,1\}^{N} \to\binom{Y}{2} \cup\{\mathrm{fail}\} T 2 : { 0 , 1 } N → ( 2 Y ) ∪ { fail } O ( t + a ) O(t+a) O ( t + a ) Pr u [ T 2 ( u ) ≠ f a i l ] ≥ η \Pr_u[T_2(u) \ne\mathrm{fail}] \ge\eta Pr u [ T 2 ( u ) = fail ] ≥ η T 2 T_2 T 2 T 2 ( u ) T_2(u) T 2 ( u ) u u u T 2 ( u ) ≠ f a i l T_2(u) \ne\mathrm{fail} T 2 ( u ) = fail
In both cases the tree queries only bits that D D D f y f_y f y
Remark 1. Lemma 16 is a decision-tree form of [3 Corollary 5.4] . The idea that a search problem with (almost) unique solutions cannot be hard relative to a random oracle goes back to Rudich [Rud88]; his conjecture was proved by Kahn, Saks, and Smyth [51 ] via the dual BKR inequality, which [32 ] and then [3 ] applied to verifiable delay functions and proofs of work. The proof below does not use the BKR inequality.
Intuition behind Lemma 16. In § 5.1 we prove our UEoPL upper bound (Theorem 15) by applying Lemma 16 recursively, where Y Y Y ( f y ) y ∈ Y (f_y)_{y \in Y} ( f y ) y ∈ Y 2 q 2q 2 q y y y f f f y ∈ Y y \in Y y ∈ Y u u u y y y u u u D D D y y y u u u D D D y y y y y y Lemma 16 gives a win-win dichotomy applied to this row of nodes. Informally it states: Let D D D t ≫ q t \gg q t ≫ q 1 − η 1-\eta 1 − η T 1 T_1 T 1 O ( q 2 ) O(q^2) O ( q 2 ) T 1 ( u ) T_1(u) T 1 ( u ) 1 / 2 1/2 1/2 T 1 ( u ) T_1(u) T 1 ( u ) T 2 T_2 T 2 O ( t + a ) O(t+a) O ( t + a ) T 2 ( u ) T_2(u) T 2 ( u ) η \eta η T 2 ( u ) T_2(u) T 2 ( u )
Why should we expect such a win-win situation? Think of each accepting leaf of an activity tree f y f_y f y ρ \rho ρ y y y u u u ρ \rho ρ D D D u u u D ( u ) D(u) D ( u ) ( f y ) y ∈ Y (f_y)_{y \in Y} ( f y ) y ∈ Y D D D T 1 T_1 T 1 q q q O ( q 2 ) O(q^2) O ( q 2 ) u u u D ( u ) D(u) D ( u ) u u u u u u T 2 T_2 T 2 D D D u u u u u u T 2 T_2 T 2 D D D T 2 T_2 T 2
Proof of Theorem 15
Fix ω \omega ω q q q ρ \rho ρ A A A Q ( A ) Q(A) Q ( A ) A A A E ρ [ Q ( A ) ] \mathbb{E}_{\rho}[Q(A)] E ρ [ Q ( A )] A A A cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) ω ( u ) \omega(u) ω ( u ) cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) u ∈ cube ( ρ ) u \in\operatorname{cube}(\rho) u ∈ cube ( ρ )
Activity trees. For a node v v v act v ( u ) ∈ { 0 , 1 } \operatorname{act}_{v}(u) \in\{0,1\} act v ( u ) ∈ { 0 , 1 } v v v ω ( u ) \omega(u) ω ( u ) 2 q 2q 2 q Succ v \operatorname{Succ}_{v} Succ v v v v Succ v ≠ ⊥ \operatorname{Succ}_{v} \ne\bot Succ v = ⊥ v v v b ∈ [ N ] b \in[N] b ∈ [ N ] act b : = ( act ( b , j ) ) j ∈ [ N ] \operatorname{act}^{b} := (\operatorname{act}_{(b,j)})_{j \in[N]} act b := ( act ( b , j ) ) j ∈ [ N ] b b b a = O ( q 2 ) a = O(q^{2}) a = O ( q 2 ) η = Θ ( 1 / q ) \eta= \Theta(1/q) η = Θ ( 1/ q ) Lemma 16 provides for verifier depth 2 q 2q 2 q
We apply Lemma 16 to a tree D D D cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) act b \operatorname{act}^{b} act b ρ \rho ρ T 1 T_{1} T 1 T 2 T_{2} T 2 ρ \rho ρ E E E Pr u ∼ cube ( ρ ) [ E ] = Pr u ∼ { 0 , 1 } N [ E ] \Pr_{u \sim\operatorname{cube}(\rho)}[E] = \Pr_{u \sim\{0,1\}^{N}}[E] Pr u ∼ cube ( ρ ) [ E ] = Pr u ∼ { 0 , 1 } N [ E ] T 1 T_{1} T 1 T 2 T_{2} T 2
High-level description of the algorithm. The backbone of the algorithm is the recursive subroutine Jump ( v , r ) \operatorname{Jump}(v,r) Jump ( v , r ) v = ( i , j ) v = (i,j) v = ( i , j ) i i i b : = min { i + 2 r , N } b := \min\{i + 2^{r}, N\} b := min { i + 2 r , N } cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) b b b η \eta η
For r = 0 r = 0 r = 0 v v v r ≥ 1 r \ge1 r ≥ 1 b b b 2 r − 1 2^{r-1} 2 r − 1 Figure 4 ): let C C C Jump ( v , r − 1 ) \operatorname{Jump}(v,r-1) Jump ( v , r − 1 ) v ′ v' v ′ Jump ( v ′ , r − 1 ) \operatorname{Jump}(v',r-1) Jump ( v ′ , r − 1 ) C C C log N \log N log N Θ ( N ) \Theta(N) Θ ( N ) C C C D D D Lemma 16 , applied with the activity trees of row b b b C C C b b b
Figure 4. One iteration of the loop in Algorithm 1: the two jumps on the left form C C C T 1 T_1 T 1 T 2 T_2 T 2 w , w ′ w,w' w , w ′ i + 2 r i+2^r i + 2 r
In the compression case it provides a tree T 1 T_{1} T 1 a a a r r r b b b 1 / 2 1/2 1/2 Figure 4 ). We then jump by running T 1 T_{1} T 1 C C C T 1 T_{1} T 1
In the collision case it provides a tree T 2 T_{2} T 2 b b b η \eta η T 2 T_{2} T 2 1 / η 1/\eta 1/ η C C C 1 / η 1/\eta 1/ η log N \log N log N Jump \operatorname{Jump} Jump T 2 T_{2} T 2 T 2 T_{2} T 2 C C C T 2 T_{2} T 2 Jump ( ( 1 , 1 ) , r ∗ ) \operatorname{Jump}((1,1),r^{*}) Jump (( 1 , 1 ) , r ∗ ) 1 / η 1/\eta 1/ η
The only situation in which C C C η / 2 \eta/2 η /2 Jump ( v , r ) \operatorname{Jump}(v,r) Jump ( v , r ) O ( 1 / η ) O(1/\eta) O ( 1/ η ) C C C b b b 1 − η / 2 1-\eta/2 1 − η /2 t = ⌈ 2 E ρ [ Q ( C ) ] / η ⌉ t = \lceil2\mathbb{E}_{\rho}[Q(C)]/\eta\rceil t = ⌈ 2 E ρ [ Q ( C )] / η ⌉ η / 2 \eta/2 η /2 D D D Lemma 16 needs.
It is important for the accounting that lines 7, 9, 10 and 11 of Algorithm 1 make no oracle queries: they define trees and compute probabilities and expectations on cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ )
Algorithm 1 Subroutine JUMP in Algorithm 2.
Input: a node v = ( i , j ) v=(i,j) v = ( i , j ) ( ρ ) (\rho) ( ρ ) r ≥ 0 r\geq0 r ≥ 0
Output: an active node of row min { i + 2 r , N } \min\{i+2^r,N\} min { i + 2 r , N }
if i = N i=N i = N return the node v v v
Set b : = min { i + 2 r , N } b:=\min\{i+2^r,N\} b := min { i + 2 r , N }
if r = 0 r=0 r = 0
Query Succ v \operatorname{Succ}_v Succ v act v ′ \operatorname{act}_{v'} act v ′ v ′ : = ( i + 1 , Succ v ) v':=(i+1,\operatorname{Succ}_v) v ′ := ( i + 1 , Succ v ) v v v
return the solution v ′ v' v ′ v ′ v' v ′ v ′ v' v ′
loop
Let C C C ( ρ ) (\rho) ( ρ ) ( v , r − 1 ) (v,r-1) ( v , r − 1 ) v ′ v' v ′ ( v ′ , r − 1 ) (v',r-1) ( v ′ , r − 1 ) C C C
if Pr ρ [ C \Pr_\rho[C Pr ρ [ C u ] ≥ η / 2 u]\geq\eta/2 u ] ≥ η /2 C C C return its output.
Set t : = ⌈ 2 E ρ [ Q ( C ) ] / η ⌉ t:=\lceil2\mathbb{E}_\rho[Q(C)]/\eta\rceil t := ⌈ 2 E ρ [ Q ( C )] / η ⌉
Let D D D C C C t t t C C C
Apply Lemma 16 on cube( ρ ) (\rho) ( ρ ) act b \operatorname{act}_b act b D D D T 1 T_1 T 1 return the tree T 2 T_2 T 2
Run T 1 T_1 T 1 T 1 T_1 T 1 v ′ v' v ′ return the node v ′ v' v ′
Algorithm 2 The main algorithm.
Input: u ∈ { 0 , 1 } N u\in\{0,1\}^{N} u ∈ { 0 , 1 } N
Output: a solution of ω ( u ) \omega(u) ω ( u )
Query act ( 1 , 1 ) \operatorname{act}_{(1,1)} act ( 1 , 1 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) return ( 1 , 1 ) (1,1) ( 1 , 1 )
Set r ∗ : = ⌈ log 2 N ⌉ r^*:=\lceil\log_2 N\rceil r ∗ := ⌈ log 2 N ⌉
loop
Run JUMP( ( 1 , 1 ) , r ∗ ) ((1,1),r^*) (( 1 , 1 ) , r ∗ )
If it outputs a node or a solution z z z return z z z
If it outputs a decision tree G G G G G G return its output if it is a solution.
Let r ≥ 0 r\geq0 r ≥ 0 ρ \rho ρ v = ( i , j ) v=(i,j) v = ( i , j ) ( ρ ) (\rho) ( ρ ) ( v , r ) (v,r) ( v , r ) ρ \rho ρ r r r
Claim 17. Jump( v , r ) (v,r) ( v , r ) u ∈ cube ( ρ ) u \in\operatorname{cube}(\rho) u ∈ cube ( ρ )
Claim 18. Jump( v , r ) (v,r) ( v , r ) ρ ′ \rho' ρ ′
a node of its target row that is active on cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ )
a solution on cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ )
a decision tree G G G cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ ) G ( u ) G(u) G ( u ) ω ( u ) \omega(u) ω ( u ) u ∈ cube ( ρ ′ ) u \in\operatorname{cube}(\rho') u ∈ cube ( ρ ′ ) Pr ρ ′ [ G ( u ) ≠ f a i l ] ≥ η \Pr_{\rho'}[G(u) \ne\mathrm{fail}] \ge\eta Pr ρ ′ [ G ( u ) = fail ] ≥ η
Proof of Claim 17. The cases i = N i=N i = N r = 0 r=0 r = 0 i < N i<N i < N r ≥ 1 r\ge1 r ≥ 1 r − 1 r-1 r − 1
the tree C C C b b b
Equation not extracted
(3) Consider an iteration of the loop, at a restriction ρ \rho ρ C C C η / 2 \eta/2 η /2 cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) t t t η / 2 \eta/2 η /2 D D D t t t b b b 1 − η 1-\eta 1 − η cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) act b \operatorname{act}_b act b D D D ( v , r ) (v,r) ( v , r ) T 1 T_1 T 1 Pr ρ [ T 1 ( u ) ≠ f a i l ] ≥ 1 / 2 \Pr_{\rho}[T_1(u)\ne\mathrm{fail}]\ge1/2 Pr ρ [ T 1 ( u ) = fail ] ≥ 1/2 T 1 T_1 T 1 ω ( u ) \omega(u) ω ( u ) u u u
Proof of Claim 18. If i = N i=N i = N v v v b = N b=N b = N i < N i<N i < N r = 0 r=0 r = 0 v _v v v ′ v' v ′ b b b cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ ) v v v cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ ) ρ ′ \rho' ρ ′ v ′ v' v ′ cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ ) v v v v ′ v' v ′ v ′ v' v ′ cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ ) v ′ v' v ′ i < N i<N i < N r ≥ 1 r\ge1 r ≥ 1 ( v , r ) (v,r) ( v , r )
In line 8 it outputs the output of C C C
In line 11 it outputs T 2 T_2 T 2 b b b η \eta η
In line 12 it outputs a node of row b b b T 1 T_1 T 1 cube ( ρ ′ ) \operatorname{cube}(\rho') cube ( ρ ′ )
Claim 19. E ρ [ Q ( J u m p ( v , r ) ) ] = O ( a ( r + 1 ) / η ) \mathbb{E}_{\rho}[\mathrm{Q}(\mathrm{Jump}(v,r))]=O(a(r+1)/\eta) E ρ [ Q ( Jump ( v , r ))] = O ( a ( r + 1 ) / η )
Proof. For k ≤ r k\le r k ≤ r N k N_k N k ( ⋅ , k ) (\cdot,k) ( ⋅ , k ) ( v , r ) (v,r) ( v , r ) M k ≤ N k M_k\le N_k M k ≤ N k C C C N r = 1 N_r=1 N r = 1 N k − 1 ≤ 2 M k N_{k-1}\le2M_k N k − 1 ≤ 2 M k k ∈ [ r ] k\in[r] k ∈ [ r ] ( ⋅ , k − 1 ) (\cdot,k-1) ( ⋅ , k − 1 ) C C C C C C η / 2 \eta/2 η /2 ( v , r ) (v,r) ( v , r ) E ρ [ M k ] = O ( 1 / η ) \mathbb{E}_{\rho}[M_k]=O(1/\eta) E ρ [ M k ] = O ( 1/ η ) k ∈ [ r ] k\in[r] k ∈ [ r ] E ρ [ ∑ k = 1 r N k ] = O ( 1 + r / η ) \mathbb{E}_{\rho}[\sum_{k=1}^{r}N_k]=O(1+r/\eta) E ρ [ ∑ k = 1 r N k ] = O ( 1 + r / η )
Each time Jump( ⋅ , k ) (\cdot,k) ( ⋅ , k ) O ( q ) = O ( a ) O(q)=O(a) O ( q ) = O ( a ) T 1 T_1 T 1 T 1 T_1 T 1 a a a 1 / 2 1/2 1/2 ( ⋅ , k ) (\cdot,k) ( ⋅ , k ) O ( a ) O(a) O ( a ) E ρ [ Q ( J u m p ( v , r ) ) ] = O ( a ) ⋅ O ( 1 + r / η ) = O ( a ( r + 1 ) / η ) \mathbb{E}_{\rho}[\mathrm{Q}(\mathrm{Jump}(v,r))]=O(a)\cdot O(1+r/\eta)=O(a(r+1)/\eta) E ρ [ Q ( Jump ( v , r ))] = O ( a ) ⋅ O ( 1 + r / η ) = O ( a ( r + 1 ) / η )
Claim 20. Every tree that Jump( v , r ) (v,r) ( v , r ) O ( a ( r + 1 ) / η 2 ) O(a(r+1)/\eta^2) O ( a ( r + 1 ) / η 2 )
Proof. A tree that Jump( v , r ) (v,r) ( v , r ) T 2 T_2 T 2 ( ⋅ , k ) (\cdot,k) ( ⋅ , k ) k ∈ [ r ] k\in[r] k ∈ [ r ] O ( t + a ) O(t+a) O ( t + a ) t = O ( E ρ [ Q ( C ) ] / η ) = O ( a k / η 2 ) t=O(\mathbb{E}_{\rho}[\mathrm{Q}(C)]/\eta)=O(ak/\eta^2) t = O ( E ρ [ Q ( C )] / η ) = O ( ak / η 2 )
Proof of Theorem 15. Consider an iteration of the loop in Algorithm 2 that starts from a restriction ρ \rho ρ ( 1 , 1 ) , r ∗ (1,1),r^* ( 1 , 1 ) , r ∗ O ( a r ∗ / η ) O(ar^*/\eta) O ( a r ∗ / η ) G G G O ( a r ∗ / η 2 ) O(ar^*/\eta^2) O ( a r ∗ / η 2 ) η \eta η O ( a r ∗ / η 2 ) O(ar^*/\eta^2) O ( a r ∗ / η 2 ) η \eta η cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) u u u ω ( u ) \omega(u) ω ( u )
B = O ( q ) + 1 η ⋅ O ( a r ∗ η 2 ) = poly ( q ) ⋅ log N . B = O(q) + \frac{1}{\eta}\cdot O\left(\frac{ar^*}{\eta^2}\right) = \operatorname{poly}(q)\cdot\log N. B = O ( q ) + η 1 ⋅ O ( η 2 a r ∗ ) = poly ( q ) ⋅ log N . Let T T T 3 B 3B 3 B 3 B 3B 3 B cube ( ρ ) \operatorname{cube}(\rho) cube ( ρ ) T T T 1 / 3 1/3 1/3
Proof of Lemma 16
Let f f f D D D Lemma 16 ; the parameters a a a η \eta η Lemma 16 below. The trees f y f_y f y D D D 1 , … , K 1,\ldots,K 1 , … , K u u u { 0 , 1 } K \{0,1\}^K { 0 , 1 } K A ⊆ { 0 , 1 } K A\subseteq\{0,1\}^K A ⊆ { 0 , 1 } K Pr [ A ] \Pr[A] Pr [ A ] Pr [ u ∈ A ] \Pr[u\in A] Pr [ u ∈ A ]
α : = Pr [ f does not accept D ( u ) on u ] , ε : = max E Pr [ f accepts E ( u ) on u , and E ( u ) ≠ D ( u ) ] , \alpha:= \Pr\left[f\text{ does not accept }D(u)\text{ on }u\right],\qquad
\varepsilon:= \max_E \Pr\left[f\text{ accepts }E(u)\text{ on }u,\text{ and }E(u)\ne D(u)\right], α := Pr [ f does not accept D ( u ) on u ] , ε := E max Pr [ f accepts E ( u ) on u , and E ( u ) = D ( u ) ] , where the maximum is over all decision trees E : { 0 , 1 } K → Y ∪ { fail } E:\{0,1\}^K\to Y\cup\{\operatorname{fail}\} E : { 0 , 1 } K → Y ∪ { fail } t t t
Let Λ \Lambda Λ f y f_y f y τ ∈ Λ \tau\in\Lambda τ ∈ Λ y τ y_\tau y τ τ \tau τ B τ ⊆ { 0 , 1 } K B_\tau\subseteq\{0,1\}^K B τ ⊆ { 0 , 1 } K f y τ f_{y_\tau} f y τ τ \tau τ q q q
Claim 21. There is a set Λ ′ ⊆ Λ \Lambda'\subseteq\Lambda Λ ′ ⊆ Λ m ( u ) : = ∣ { τ ∈ Λ ′ : u ∈ B τ } ∣ m(u):=\lvert\{\tau\in\Lambda':u\in B_\tau\}\rvert m ( u ) := ∣{ τ ∈ Λ ′ : u ∈ B τ }∣
E ∣ m ( u ) − 1 ∣ ≤ α + O ( q ε ) . \mathbb{E}\lvert m(u)-1\rvert\le\alpha+O(q\varepsilon). E ∣ m ( u ) − 1 ∣ ≤ α + O ( q ε ) . Claim 22. There is an absolute constant c > 0 c>0 c > 0 ( B τ ) τ ∈ Λ ′ (B_\tau)_{\tau\in\Lambda'} ( B τ ) τ ∈ Λ ′ { 0 , 1 } K \{0,1\}^K { 0 , 1 } K q q q m ( u ) : = ∣ { τ ∈ Λ ′ : u ∈ B τ } ∣ m(u):=\lvert\{\tau\in\Lambda':u\in B_\tau\}\rvert m ( u ) := ∣{ τ ∈ Λ ′ : u ∈ B τ }∣ E ∣ m ( u ) − 1 ∣ ≤ c \mathbb{E}\lvert m(u)-1\rvert\le c E ∣ m ( u ) − 1 ∣ ≤ c O ( q 2 ) O(q^2) O ( q 2 ) u u u τ \tau τ u ∈ B τ u\in B_\tau u ∈ B τ 1 / 2 1/2 1/2
We prove Claim 21 in § 5.3 and Claim 22 in § 5.4 .
Proof of Lemma 16 . Let c c c Claim 22 . We choose η = Θ ( 1 / q ) \eta=\Theta(1/q) η = Θ ( 1/ q ) α + O ( q ε ) \alpha+O(q\varepsilon) α + O ( q ε ) Claim 21 is at most c c c α ≤ η \alpha\le\eta α ≤ η ε ≤ 2 η \varepsilon\le2\eta ε ≤ 2 η a = O ( q 2 ) a=O(q^2) a = O ( q 2 ) Claim 22 , which we may assume to be at least 2 q 2q 2 q D D D α ≤ η \alpha\le\eta α ≤ η
Suppose first that ε ≤ 2 η \varepsilon\le2\eta ε ≤ 2 η Claim 21 , there is a set Λ ′ \Lambda' Λ ′ E ∣ m ( u ) − 1 ∣ ≤ c \mathbb{E}\lvert m(u)-1\rvert\le c E ∣ m ( u ) − 1 ∣ ≤ c T 1 T_1 T 1 Claim 22 for this family, and output y τ y_\tau y τ τ \tau τ T 1 T_1 T 1 a a a 1 / 2 1/2 1/2 y τ y_\tau y τ B τ B_\tau B τ u ∈ B τ u\in B_\tau u ∈ B τ T 1 T_1 T 1 y τ y_\tau y τ u u u
Suppose now that ε > 2 η \varepsilon>2\eta ε > 2 η E E E ε \varepsilon ε T 2 T_2 T 2 D D D E E E D ( u ) D(u) D ( u ) E ( u ) E(u) E ( u ) Y Y Y f D ( u ) f_{D(u)} f D ( u ) f E ( u ) f_{E(u)} f E ( u ) { D ( u ) , E ( u ) } \{D(u),E(u)\} { D ( u ) , E ( u )} T 2 T_2 T 2 2 t + 2 q = O ( t + a ) 2t+2q=O(t+a) 2 t + 2 q = O ( t + a )
Pr [ T 2 ( u ) ≠ fail ] ≥ ε − α > η . \Pr[T_2(u)\ne\operatorname{fail}]\ge\varepsilon-\alpha>\eta. Pr [ T 2 ( u ) = fail ] ≥ ε − α > η . Proof of Claim 21
For τ ∈ Λ \tau\in\Lambda τ ∈ Λ
A τ : = { u ∈ B τ : D ( u ) = y τ } , θ τ : = Pr [ A τ ] / Pr [ B τ ] , Γ : = ∑ τ ∈ Λ Pr [ A τ ] ( 1 − θ τ ) . A_\tau:=\{u\in B_\tau:D(u)=y_\tau\},\qquad
\theta_\tau:=\Pr[A_\tau]/\Pr[B_\tau],\qquad
\Gamma:=\sum_{\tau\in\Lambda}\Pr[A_\tau](1-\theta_\tau). A τ := { u ∈ B τ : D ( u ) = y τ } , θ τ := Pr [ A τ ] / Pr [ B τ ] , Γ := τ ∈ Λ ∑ Pr [ A τ ] ( 1 − θ τ ) . The sets A τ A_\tau A τ u ∈ A τ u\in A_\tau u ∈ A τ τ \tau τ f D ( u ) f_{D(u)} f D ( u ) u u u f f f D ( u ) D(u) D ( u ) ∑ τ Pr [ A τ ] = 1 − α \sum_\tau\Pr[A_\tau]=1-\alpha ∑ τ Pr [ A τ ] = 1 − α
Definition 4. Let β ∈ [ 0 , 1 ] \beta\in[0,1] β ∈ [ 0 , 1 ] u ∈ { 0 , 1 } K \mathbf{u} \in\{0,1\}^{K} u ∈ { 0 , 1 } K β \beta β u \mathbf{u} u x \mathbf{x} x u \mathbf{u} u β \beta β
Claim 23. Let x \mathbf{x} x β \beta β u \mathbf{u} u A ⊆ { 0 , 1 } K A \subseteq\{0,1\}^{K} A ⊆ { 0 , 1 } K p : = Pr [ A ] p := \Pr[A] p := Pr [ A ]
Pr [ u ∈ A , x ∉ A ] ≥ β p ( 1 − p ) . \Pr[\mathbf{u} \in A,\ \mathbf{x} \notin A] \ge\beta p(1-p). Pr [ u ∈ A , x ∈ / A ] ≥ β p ( 1 − p ) . Proof. Let g g g A A A g ^ ( J ) \widehat{g}(J) g ( J ) J ⊆ [ K ] J \subseteq[K] J ⊆ [ K ] g ^ ( ∅ ) = p \widehat{g}(\varnothing)=p g ( ∅ ) = p ∑ J g ^ ( J ) 2 = p \sum_J \widehat{g}(J)^2=p ∑ J g ( J ) 2 = p
Pr [ u ∈ A , x ∈ A ] = ∑ J ( 1 − β ) ∣ J ∣ g ^ ( J ) 2 ≤ p 2 + ( 1 − β ) ( p − p 2 ) . \Pr[\mathbf{u} \in A,\ \mathbf{x} \in A] = \sum_J (1-\beta)^{|J|}\widehat{g}(J)^2 \le p^2+(1-\beta)(p-p^2). Pr [ u ∈ A , x ∈ A ] = J ∑ ( 1 − β ) ∣ J ∣ g ( J ) 2 ≤ p 2 + ( 1 − β ) ( p − p 2 ) . Subtracting this from p p p
Claim 24. Γ = O ( q ε ) \Gamma=O(q\varepsilon) Γ = O ( q ε )
Proof. Let x \mathbf{x} x β \beta β u \mathbf{u} u β : = 1 / ( 2 q ) \beta:=1/(2q) β := 1/ ( 2 q ) D D D x \mathbf{x} x ( u , x ) (\mathbf{u},\mathbf{x}) ( u , x ) ( x , u ) (\mathbf{x},\mathbf{u}) ( x , u ) τ ∈ Λ \tau\in\Lambda τ ∈ Λ H τ H_\tau H τ q q q B τ B_\tau B τ Pr [ H τ ] ≥ 1 − q β = 1 / 2 \Pr[H_\tau]\ge1-q\beta=1/2 Pr [ H τ ] ≥ 1 − q β = 1/2 H τ H_\tau H τ u ∈ B τ \mathbf{u}\in B_\tau u ∈ B τ x ∈ B τ \mathbf{x}\in B_\tau x ∈ B τ B τ B_\tau B τ ( u , x ) (\mathbf{u},\mathbf{x}) ( u , x ) Claim 23 inside the subcube B τ B_\tau B τ A τ A_\tau A τ u \mathbf{u} u x \mathbf{x} x
Pr [ x ∈ A τ , u ∈ B τ ∖ A τ ] ≥ Pr [ B τ ] ⋅ Pr [ H τ ] ⋅ β θ τ ( 1 − θ τ ) ≥ β 2 Pr [ A τ ] ( 1 − θ τ ) . \Pr[\mathbf{x}\in A_\tau,\ \mathbf{u}\in B_\tau\setminus A_\tau]\ge\Pr[B_\tau]\cdot\Pr[H_\tau]\cdot\beta\theta_\tau(1-\theta_\tau)\ge\frac{\beta}{2}\Pr[A_\tau](1-\theta_\tau). Pr [ x ∈ A τ , u ∈ B τ ∖ A τ ] ≥ Pr [ B τ ] ⋅ Pr [ H τ ] ⋅ β θ τ ( 1 − θ τ ) ≥ 2 β Pr [ A τ ] ( 1 − θ τ ) . The events on the left-hand side are disjoint for different τ \tau τ A τ A_\tau A τ D ( x ) = y τ D(\mathbf{x})=y_\tau D ( x ) = y τ u \mathbf{u} u D ( u ) D(\mathbf{u}) D ( u )
Pr [ f accepts D ( x ) on u , and D ( x ) ≠ D ( u ) ] ≥ β Γ 2 . \Pr[f\text{ accepts }D(\mathbf{x})\text{ on }\mathbf{u},\text{ and }D(\mathbf{x})\ne D(\mathbf{u})]\ge\frac{\beta\Gamma}{2}. Pr [ f accepts D ( x ) on u , and D ( x ) = D ( u )] ≥ 2 β Γ . Conditioned on which bits are replaced and on their new values, D ( x ) D(\mathbf{x}) D ( x ) u \mathbf{u} u t t t ε \varepsilon ε Γ ≤ 2 ε / β = O ( q ε ) \Gamma\le2\varepsilon/\beta=O(q\varepsilon) Γ ≤ 2 ε / β = O ( q ε )
Proof of Claim 21 . Let Λ ′ : = { τ ∈ Λ : θ τ ≥ 1 / 2 } \Lambda' := \{\tau\in\Lambda:\theta_\tau\ge1/2\} Λ ′ := { τ ∈ Λ : θ τ ≥ 1/2 } m ( u ) = 0 m(\mathbf{u})=0 m ( u ) = 0 u \mathbf{u} u A τ A_\tau A τ A τ A_\tau A τ τ ∉ Λ ′ \tau\notin\Lambda' τ ∈ / Λ ′ 1 ≤ 2 ( 1 − θ τ ) 1\le2(1-\theta_\tau) 1 ≤ 2 ( 1 − θ τ ) τ ∉ Λ ′ \tau\notin\Lambda' τ ∈ / Λ ′
Pr [ m ( u ) = 0 ] ≤ α + ∑ τ ∉ Λ ′ Pr [ A τ ] ≤ α + 2 ∑ τ ∉ Λ ′ Pr [ A τ ] ( 1 − θ τ ) . \Pr[m(\mathbf{u})=0]\le\alpha+\sum_{\tau\notin\Lambda'}\Pr[A_\tau]\le\alpha+2\sum_{\tau\notin\Lambda'}\Pr[A_\tau](1-\theta_\tau). Pr [ m ( u ) = 0 ] ≤ α + τ ∈ / Λ ′ ∑ Pr [ A τ ] ≤ α + 2 τ ∈ / Λ ′ ∑ Pr [ A τ ] ( 1 − θ τ ) . Since every u \mathbf{u} u A τ A_\tau A τ max { m ( u ) − 1 , 0 } ≤ ∣ { τ ∈ Λ ′ : u ∈ B τ ∖ A τ } ∣ \max\{m(\mathbf{u})-1,0\}\le|\{\tau\in\Lambda':\mathbf{u}\in B_\tau\setminus A_\tau\}| max { m ( u ) − 1 , 0 } ≤ ∣ { τ ∈ Λ ′ : u ∈ B τ ∖ A τ } ∣ Pr [ B τ ] = Pr [ A τ ] / θ τ ≤ 2 Pr [ A τ ] \Pr[B_\tau]=\Pr[A_\tau]/\theta_\tau\le2\Pr[A_\tau] Pr [ B τ ] = Pr [ A τ ] / θ τ ≤ 2 Pr [ A τ ] τ ∈ Λ ′ \tau\in\Lambda' τ ∈ Λ ′
E max { m ( u ) − 1 , 0 } ≤ ∑ τ ∈ Λ ′ Pr [ B τ ] ( 1 − θ τ ) ≤ 2 ∑ τ ∈ Λ ′ Pr [ A τ ] ( 1 − θ τ ) . \mathbb{E}\max\{m(\mathbf{u})-1,0\}\le\sum_{\tau\in\Lambda'}\Pr[B_\tau](1-\theta_\tau)\le2\sum_{\tau\in\Lambda'}\Pr[A_\tau](1-\theta_\tau). E max { m ( u ) − 1 , 0 } ≤ τ ∈ Λ ′ ∑ Pr [ B τ ] ( 1 − θ τ ) ≤ 2 τ ∈ Λ ′ ∑ Pr [ A τ ] ( 1 − θ τ ) . Adding the two bounds gives E ∣ m ( u ) − 1 ∣ ≤ α + 2 Γ \mathbb{E}|m(\mathbf{u})-1|\le\alpha+2\Gamma E ∣ m ( u ) − 1∣ ≤ α + 2Γ α + O ( q ε ) \alpha+O(q\varepsilon) α + O ( q ε ) Claim 24 .
Proof of Claim 22
We prove Claim 22 with c = 1 / 64 c=1/64 c = 1/64
W ( u ) : = 1 [ m ( u ) = 0 ] + m ( u ) ⋅ 1 [ m ( u ) ≥ 2 ] . W(\mathbf{u}):=\mathbf{1}[m(\mathbf{u})=0]+m(\mathbf{u})\cdot\mathbf{1}[m(\mathbf{u})\ge2]. W ( u ) := 1 [ m ( u ) = 0 ] + m ( u ) ⋅ 1 [ m ( u ) ≥ 2 ] . Since W ≤ 2 ∣ m − 1 ∣ W\le2|m-1| W ≤ 2∣ m − 1∣ E [ W ( u ) ] ≤ 1 / 32 \mathbb{E}[W(\mathbf{u})]\le1/32 E [ W ( u )] ≤ 1/32
Algorithm 3. The decision tree of Claim 22 .
Input: u ∈ { 0 , 1 } K u \in\{0,1\}^{K} u ∈ { 0 , 1 } K
Output: τ ∈ Λ ′ \tau\in\Lambda' τ ∈ Λ ′ u ∈ B τ u \in B_{\tau} u ∈ B τ
Initialize σ \sigma σ
for k ∈ [ 8 ( q + 1 ) ] k \in[8(q+1)] k ∈ [ 8 ( q + 1 )]
if E σ [ W ( u ) ] > 1 / 8 \mathbb{E}_{\sigma}[W(u)] > 1/8 E σ [ W ( u )] > 1/8
Set τ ∗ : = arg min τ Pr σ [ m ( u ) ≥ 2 ∣ u ∈ B τ ] \tau^* := \arg\min_{\tau} \Pr_{\sigma}[m(u) \ge2 \mid u \in B_{\tau}] τ ∗ := arg min τ Pr σ [ m ( u ) ≥ 2 ∣ u ∈ B τ ] τ \tau τ Λ ′ \Lambda' Λ ′ Pr σ [ B τ ] > 0 \Pr_{\sigma}[B_{\tau}] > 0 Pr σ [ B τ ] > 0
Query all bits that are fixed by B τ ∗ B_{\tau^*} B τ ∗ σ \sigma σ σ \sigma σ
if u ∈ B τ ∗ u \in B_{\tau^*} u ∈ B τ ∗ τ ∗ \tau^* τ ∗
return fail.
Algorithm 3 makes at most 8 ( q + 1 ) ⋅ q = O ( q 2 ) 8(q+1)\cdot q = O(q^2) 8 ( q + 1 ) ⋅ q = O ( q 2 ) τ \tau τ u ∈ B τ u \in B_{\tau} u ∈ B τ
Algorithm 3 halts in line 3.
Algorithm 3 halts in line 7.
We denote these two events by E 1 E_1 E 1 E 2 E_2 E 2
Claim 25. Pr [ E 1 ] ≤ 1 / 4 \Pr[E_1] \le1/4 Pr [ E 1 ] ≤ 1/4
Proof. The restrictions σ \sigma σ E σ W > 1 / 8 \mathbb{E}_{\sigma} W > 1/8 E σ W > 1/8 W ≥ 0 W \ge0 W ≥ 0
1 32 ≥ E W ( u ) ≥ ∑ σ Pr [ cube ( σ ) ] ⋅ E σ W ≥ 1 8 Pr [ E 1 ] , \frac{1}{32} \ge\mathbb{E}W(u) \ge\sum_{\sigma}\Pr[\operatorname{cube}(\sigma)]\cdot\mathbb{E}_{\sigma}W \ge\frac{1}{8}\Pr[E_1], 32 1 ≥ E W ( u ) ≥ σ ∑ Pr [ cube ( σ )] ⋅ E σ W ≥ 8 1 Pr [ E 1 ] , where the sum is over these restrictions.
Claim 26. Suppose that an iteration of Algorithm 3 reaches line 4 at a restriction σ \sigma σ τ ∗ \tau^* τ ∗ B ∗ : = B τ ∗ B^* := B_{\tau^*} B ∗ := B τ ∗ Pr σ [ m ≥ 2 ∣ B ∗ ] ≤ 1 / 7 \Pr_{\sigma}[m \ge2 \mid B^*] \le1/7 Pr σ [ m ≥ 2 ∣ B ∗ ] ≤ 1/7
Proof. Let e : = E σ W ≤ 1 / 8 e := \mathbb{E}_{\sigma} W \le1/8 e := E σ W ≤ 1/8 W ≥ 1 [ m ≠ 1 ] W \ge\mathbf{1}[m \ne1] W ≥ 1 [ m = 1 ] Pr σ [ m = 1 ] ≥ 1 − e \Pr_{\sigma}[m = 1] \ge1-e Pr σ [ m = 1 ] ≥ 1 − e
∑ τ Pr σ [ B τ ] = E σ [ m ] ≥ 1 − e and ∑ τ Pr σ [ B τ ] ⋅ Pr σ [ m ≥ 2 ∣ B τ ] = E σ [ m ⋅ 1 [ m ≥ 2 ] ] ≤ e , \sum_{\tau}\Pr_{\sigma}[B_{\tau}] = \mathbb{E}_{\sigma}[m] \ge1-e
\qquad\text{and}\qquad
\sum_{\tau}\Pr_{\sigma}[B_{\tau}]\cdot\Pr_{\sigma}[m \ge2 \mid B_{\tau}] = \mathbb{E}_{\sigma}[m\cdot\mathbf{1}[m \ge2]] \le e, τ ∑ σ Pr [ B τ ] = E σ [ m ] ≥ 1 − e and τ ∑ σ Pr [ B τ ] ⋅ σ Pr [ m ≥ 2 ∣ B τ ] = E σ [ m ⋅ 1 [ m ≥ 2 ]] ≤ e , where the second sum is over τ \tau τ Pr σ [ B τ ] > 0 \Pr_{\sigma}[B_{\tau}] > 0 Pr σ [ B τ ] > 0 τ ∗ \tau^* τ ∗ Pr σ [ m ≥ 2 ∣ B ∗ ] ≤ e / ( 1 − e ) ≤ 1 / 7 \Pr_{\sigma}[m \ge2 \mid B^*] \le e/(1-e) \le1/7 Pr σ [ m ≥ 2 ∣ B ∗ ] ≤ e / ( 1 − e ) ≤ 1/7
For u u u m ( u ) = 1 m(u)=1 m ( u ) = 1 B ( u ) B(u) B ( u ) u u u u u u m ( u ) = 1 m(u)=1 m ( u ) = 1 τ ∗ \tau^* τ ∗ B ( u ) B(u) B ( u ) B ( u ) B(u) B ( u ) q q q q + 1 q+1 q + 1 u u u
Claim 27. An iteration of Algorithm 3 that reaches line 4 at a restriction σ \sigma σ 1 / 2 1/2 1/2 u ∼ cube ( σ ) u \sim\operatorname{cube}(\sigma) u ∼ cube ( σ )
Proof. Let N \mathcal{N} N u ∈ cube ( σ ) u \in\operatorname{cube}(\sigma) u ∈ cube ( σ ) m ( u ) = 1 m(u)=1 m ( u ) = 1 B ( u ) B(u) B ( u ) B ∗ B^* B ∗ B ( u ) B(u) B ( u ) B ∗ B^* B ∗ u ∈ cube ( σ ) u \in\operatorname{cube}(\sigma) u ∈ cube ( σ ) x x x u u u B ∗ B^* B ∗ B ∗ B^* B ∗ u ∼ cube ( σ ) u \sim\operatorname{cube}(\sigma) u ∼ cube ( σ ) x x x cube ( σ ) ∩ B ∗ \operatorname{cube}(\sigma) \cap B^* cube ( σ ) ∩ B ∗ u ∈ N u \in\mathcal{N} u ∈ N x x x B ∗ B^* B ∗ B ( u ) B(u) B ( u ) m ( x ) ≥ 2 m(x) \ge2 m ( x ) ≥ 2 Claim 26 ,
Pr σ [ N ] ≤ Pr σ [ m ( x ) ≥ 2 ] = Pr σ [ m ≥ 2 ∣ B ∗ ] ≤ 1 7 . \Pr_{\sigma}[\mathcal{N}] \le\Pr_{\sigma}[m(x) \ge2] = \Pr_{\sigma}[m \ge2 \mid B^*] \le\frac{1}{7}. σ Pr [ N ] ≤ σ Pr [ m ( x ) ≥ 2 ] = σ Pr [ m ≥ 2 ∣ B ∗ ] ≤ 7 1 . Now let u ∈ cube ( σ ) ∖ N u \in\operatorname{cube}(\sigma) \setminus\mathcal{N} u ∈ cube ( σ ) ∖ N m ( u ) = 1 m(u)=1 m ( u ) = 1 B ( u ) = B ∗ B(u)=B^* B ( u ) = B ∗ τ ∗ \tau^* τ ∗ B ( u ) B(u) B ( u ) B ∗ B^* B ∗ σ \sigma σ B ( u ) B(u) B ( u ) B ∗ B^* B ∗ cube ( σ ) \operatorname{cube}(\sigma) cube ( σ ) E σ W ≤ 1 / 8 \mathbb{E}_{\sigma} W \le1/8 E σ W ≤ 1/8 W ≥ 1 [ m ≠ 1 ] W \ge\mathbf{1}[m \ne1] W ≥ 1 [ m = 1 ] Pr σ [ m = 1 ] − Pr σ [ N ] ≥ 7 / 8 − 1 / 7 > 1 / 2 \Pr_{\sigma}[m=1]-\Pr_{\sigma}[\mathcal{N}] \ge7/8-1/7 > 1/2 Pr σ [ m = 1 ] − Pr σ [ N ] ≥ 7/8 − 1/7 > 1/2
Claim 28. Pr [ E 2 ] ≤ 1 / 4 \Pr[E_2] \le1/4 Pr [ E 2 ] ≤ 1/4
Proof. For k ≤ 8 ( q + 1 ) k \le8(q+1) k ≤ 8 ( q + 1 ) R k \mathcal{R}_k R k k k k P k ⊆ R k \mathcal{P}_k \subseteq\mathcal{R}_k P k ⊆ R k Pr [ P k ] ≥ Pr [ R k ] / 2 \Pr[\mathcal{P}_k] \ge\Pr[\mathcal{R}_k]/2 Pr [ P k ] ≥ Pr [ R k ] /2 Claim 27 , and ∑ k Pr [ P k ] ≤ q + 1 \sum_k \Pr[\mathcal{P}_k] \le q+1 ∑ k Pr [ P k ] ≤ q + 1 E 2 \mathcal{E}_2 E 2 R k \mathcal{R}_k R k
8 ( q + 1 ) ⋅ Pr [ E 2 ] ≤ ∑ k Pr [ R k ] ≤ 2 ∑ k Pr [ P k ] ≤ 2 ( q + 1 ) . 8(q+1) \cdot\Pr[\mathcal{E}_2] \le\sum_k \Pr[\mathcal{R}_k] \le2\sum_k \Pr[\mathcal{P}_k] \le2(q+1). 8 ( q + 1 ) ⋅ Pr [ E 2 ] ≤ k ∑ Pr [ R k ] ≤ 2 k ∑ Pr [ P k ] ≤ 2 ( q + 1 ) . Given Claims 25 and 28 , Algorithm 3 outputs fail with probability at most 1 / 2 1/2 1/2 Claim 22 .
PLS separations from proof complexity
In this section we prove separations between TFNP classes in the random oracle model. We will work with the following notion of a ROM reduction.
Public reduction. Let F = { F n } F = \{F_n\} F = { F n } R = { R m } R = \{R_m\} R = { R m } F n ⊆ Σ n × O F_n \subseteq\Sigma^n \times\mathcal{O} F n ⊆ Σ n × O R m ⊆ Σ m × O ′ R_m \subseteq\Sigma^m \times\mathcal{O}' R m ⊆ Σ m × O ′ public (ROM) reduction from F n F_n F n R m R_m R m ( ω , f , g ) (\omega, f, g) ( ω , f , g )
The first family of decision trees, ω = { ω 1 , … , ω n } \omega= \{\omega_1, \ldots, \omega_n\} ω = { ω 1 , … , ω n } u 1 , … , u t u_1, \ldots, u_t u 1 , … , u t u ∈ Σ t u \in\Sigma^t u ∈ Σ t F n F_n F n u u u ω ( u ) = ω 1 ( u ) ⋯ ω n ( u ) ∈ Σ n \omega(u) = \omega_1(u) \cdots\omega_n(u) \in\Sigma^n ω ( u ) = ω 1 ( u ) ⋯ ω n ( u ) ∈ Σ n F n F_n F n ω \omega ω F n F_n F n
The second family of decision trees, f = { f 1 , … , f m } f = \{f_1, \ldots, f_m\} f = { f 1 , … , f m } u u u F n F_n F n R m R_m R m
The third family of decision trees g = { g o ∣ o ∈ O ′ } g = \{g_o \mid o \in\mathcal{O}'\} g = { g o ∣ o ∈ O ′ } u u u o o o f ( u ) f(u) f ( u ) R m R_m R m g o ( u ) g_o(u) g o ( u ) F n F_n F n ω ( u ) \omega(u) ω ( u )
The depth d ( ω , f , g ) d(\omega, f, g) d ( ω , f , g ) ( f , g ) (f, g) ( f , g ) complexity is c ( ω , f , g ) : = d ( ω , f , g ) + log m c(\omega, f, g) := d(\omega, f, g) + \log m c ( ω , f , g ) := d ( ω , f , g ) + log m
err ( ω , f , g ) : = Pr u ∼ Σ t [ ∃ o ∈ O ′ : ( f ( u ) , o ) ∈ R m ∧ ( ω ( u ) , g o ( u ) ) ∉ F n ] . \operatorname{err}(\omega, f, g) := \Pr_{u \sim\Sigma^t}\left[\exists o \in\mathcal{O}': (f(u), o) \in R_m \land(\omega(u), g_o(u)) \notin F_n\right]. err ( ω , f , g ) := u ∼ Σ t Pr [ ∃ o ∈ O ′ : ( f ( u ) , o ) ∈ R m ∧ ( ω ( u ) , g o ( u )) ∈ / F n ] . We say that F F F public reduces to R R R n n n ( n ) (n) ( n ) ( n ) (n) ( n ) ω \omega ω f , g f, g f , g c ( ω , f , g ) = polylog ( n ) c(\omega, f, g) = \operatorname{polylog}(n) c ( ω , f , g ) = polylog ( n ) err ( ω , f , g ) ≤ 1 / 3 \operatorname{err}(\omega, f, g) \le1/3 err ( ω , f , g ) ≤ 1/3
Note that up to a blow-up of d ( ω , f , g ) d(\omega, f, g) d ( ω , f , g ) f f f g g g ω ( u ) \omega(u) ω ( u ) ω ( u ) \omega(u) ω ( u ) u u u ω \omega ω err ( ω , f , g ) = 0 \operatorname{err}(\omega, f, g) = 0 err ( ω , f , g ) = 0
Separations in the ROM from average-case proof complexity bounds
Our TFNP separations will proceed by a reduction to proof complexity lower bounds. Proof complexity and TFNP are intimately connected in the black-box model. Characterization theorems show that black-box TFNP subclasses correspond exactly to the search problems whose totality can be proven efficiently in a corresponding proof system [30 BF23] . For example, recalling Definition 1 of a resolution refutation, the following result shows that resolution is exactly the search problems whose totality can be proven by PLS-style arguments.
Resolution = PLS [BKT14, Kam19]. For any F ∈ T F N P d t F \in\mathrm{TFNP}^{dt} F ∈ TFNP d t F ∈ P L S d t F \in\mathrm{PLS}^{dt} F ∈ PLS d t poly ( log n ) \operatorname{poly}(\log n) poly ( log n ) ( F , S ) (\mathcal{F}, S) ( F , S ) F F F t t t O ( t + v ) O(t+v) O ( t + v ) v v v [44 Theorem 8.18(1)] . We use the same characterization for alphabet-valued decision trees, replacing Boolean literals by cell equalities [ u i = a ] [u_i = a] [ u i = a ]
In this section, we extend this connection to ROM reductions. Let ( ω , f , g ) (\omega, f, g) ( ω , f , g ) F ⊆ Σ n × O F \subseteq\Sigma^n \times O F ⊆ Σ n × O R ⊆ Σ m × O ′ R \subseteq\Sigma^m \times O' R ⊆ Σ m × O ′ ω ( u ) = u \omega(u)=u ω ( u ) = u ω \omega ω B B B err ( ω , f , g ) \operatorname{err}(\omega, f, g) err ( ω , f , g ) w w w Σ \Sigma Σ B = ⋁ i ∈ [ t ] B i B = \bigvee_{i\in[t]} B_i B = ⋁ i ∈ [ t ] B i B i B_i B i w w w B i B_i B i F ∨ B F \vee B F ∨ B F F F B B B
We now define B B B o ∈ O ′ o \in O' o ∈ O ′ H o H_o H o ( f ( u ) , o ) ∈ R (f(u),o) \in R ( f ( u ) , o ) ∈ R g o g_o g o ( u , g o ( u ) ) ∉ F (u,g_o(u)) \notin F ( u , g o ( u )) ∈ / F viol ( f , g ) \operatorname{viol}(f,g) viol ( f , g ) u u u
B f , g : = ⋁ ρ ∈ viol ( f , g ) ⋀ i ∈ fix ( ρ ) [ u i = ρ i ] . B_{f,g} := \bigvee_{\rho\in\operatorname{viol}(f,g)} \bigwedge_{i\in\operatorname{fix}(\rho)} [u_i=\rho_i]. B f , g := ρ ∈ viol ( f , g ) ⋁ i ∈ fix ( ρ ) ⋀ [ u i = ρ i ] . Thus B f , g ( u ) = 1 B_{f,g}(u)=1 B f , g ( u ) = 1 d d d v R v_R v R v F v_F v F d v R + d + v F d v_R+d+v_F d v R + d + v F B f , g B_{f,g} B f , g F F F B f , g B_{f,g} B f , g
Pr u ∼ Σ n [ B f , g ( u ) = 1 ] = err ( ω , f , g ) . \Pr_{u\sim\Sigma^n}[B_{f,g}(u)=1]=\operatorname{err}(\omega,f,g). u ∼ Σ n Pr [ B f , g ( u ) = 1 ] = err ( ω , f , g ) . Therefore, if the reduction has low error, then B f , g B_{f,g} B f , g F F F F ∨ B ⊆ Σ n × ( O ∪ { ρ ∣ ρ ∈ B } ) F \vee B \subseteq\Sigma^n \times(O \cup\{\rho\mid\rho\in B\}) F ∨ B ⊆ Σ n × ( O ∪ { ρ ∣ ρ ∈ B }) F F F B B B
Lemma 29. Let F ⊆ Σ n × O F \subseteq\Sigma^n \times O F ⊆ Σ n × O w w w ( id , f , g ) (\operatorname{id},f,g) ( id , f , g ) F F F w w w B B B O ( w ) O(w) O ( w )
Pr u ∼ Σ n [ B ( u ) = 1 ] = err ( id , f , g ) . \Pr_{u\sim\Sigma^n}[B(u)=1]=\operatorname{err}(\operatorname{id},f,g). u ∼ Σ n Pr [ B ( u ) = 1 ] = err ( id , f , g ) . and F ∨ B F \vee B F ∨ B O ( w ) O(w) O ( w ) d d d v F v_F v F B B B 3 d + v F 3d+v_F 3 d + v F
In particular, if F ∈ T F N P d t F \in\mathrm{TFNP}^{\mathrm{dt}} F ∈ TFNP dt F ∨ B F \vee B F ∨ B n n n n n n B B B Pr [ B ( u ) = 1 ] ≤ 1 / 3 \Pr[B(u)=1]\leq1/3 Pr [ B ( u ) = 1 ] ≤ 1/3 F F F F F F
Proof. For each target answer o ∈ O ′ o \in O' o ∈ O ′ H o H_o H o o o o f ( u ) f(u) f ( u ) g o ( u ) g_o(u) g o ( u ) F F F 2 d 2d 2 d d d d v F v_F v F B = B f , g B=B_{f,g} B = B f , g 3 d + v F ≤ 4 w 3d+v_F\leq4w 3 d + v F ≤ 4 w err ( id , f , g ) \operatorname{err}(\operatorname{id},f,g) err ( id , f , g )
Modify the decoder to run the three stages of H o H_o H o g o ( u ) g_o(u) g o ( u ) H o H_o H o B B B F ∨ B F \vee B F ∨ B O ( w ) O(w) O ( w ) F ∨ B F \vee B F ∨ B O ( w ) O(w) O ( w ) [44 Theorem 8.18(1)] supplies the width-O ( w ) O(w) O ( w ) □ \square □
Robust strategies and average-case resolution
In this section, we develop tools for proving average case resolution lower bounds—that is, F ∨ B F \vee B F ∨ B B B B Delayer strategy ) for resolution proofs, and later extend it to the average case. For a partial assignment ρ ∈ ( Σ ∪ { ⋆ } ) m \rho\in(\Sigma\cup\{\star\})^m ρ ∈ ( Σ ∪ { ⋆ } ) m fix ( ρ ) : = { i ∈ [ m ] ∣ ρ i ≠ ⋆ } \operatorname{fix}(\rho):=\{i\in[m]\mid\rho_i\ne\star\} fix ( ρ ) := { i ∈ [ m ] ∣ ρ i = ⋆ } free ( ρ ) : = [ m ] ∖ fix ( ρ ) \operatorname{free}(\rho):=[m]\setminus\operatorname{fix}(\rho) free ( ρ ) := [ m ] ∖ fix ( ρ ) cube ( ρ ) : = { x ∈ Σ m ∣ ∀ i ∉ free ( ρ ) , x i = ρ i } \operatorname{cube}(\rho):=\{x\in\Sigma^m\mid\forall i\notin\operatorname{free}(\rho),x_i=\rho_i\} cube ( ρ ) := { x ∈ Σ m ∣ ∀ i ∈ / free ( ρ ) , x i = ρ i } ρ \rho ρ
Strategy. Let F ⊆ Σ m × O F \subseteq\Sigma^m \times O F ⊆ Σ m × O w w w strategy for F F F F ⊆ ( Σ ∪ { ⋆ } ) m \mathcal{F} \subseteq(\Sigma\cup\{\star\})^m F ⊆ ( Σ ∪ { ⋆ } ) m ρ ∈ F \rho\in\mathcal{F} ρ ∈ F ∣ fix ( ρ ) ∣ ≤ w |\operatorname{fix}(\rho)| \le w ∣ fix ( ρ ) ∣ ≤ w
For every o ∈ O o \in O o ∈ O x ∈ cube ( ρ ) x \in\operatorname{cube}(\rho) x ∈ cube ( ρ ) ( x , o ) ∉ F (x,o) \notin F ( x , o ) ∈ / F
Extension Property: If ∣ fix ( ρ ) ∣ < w |\operatorname{fix}(\rho)| < w ∣ fix ( ρ ) ∣ < w i ∈ free ( ρ ) i \in\operatorname{free}(\rho) i ∈ free ( ρ ) a ∈ Σ a \in\Sigma a ∈ Σ ρ ∪ { x i = a } ∈ F \rho\cup\{x_i = a\} \in\mathcal{F} ρ ∪ { x i = a } ∈ F
This is the dual object for resolution proofs:
Lemma 30 ([AD08]). There is a width-w w w F F F w w w
Hence, to separate F F F n n n F ∨ B F \vee B F ∨ B B B B robust strategy for F F F
Robust strategy. A width-w w w F F F k k k
Lemma 31. Suppose that F ⊆ Σ m × O F \subseteq\Sigma^m \times O F ⊆ Σ m × O w w w k k k w w w B B B Pr u ∼ Σ m [ B ( u ) = 1 ] < ( 1 − k / ∣ Σ ∣ ) w \Pr_{u \sim\Sigma^m}[B(u)=1] < (1-k/|\Sigma|)^w Pr u ∼ Σ m [ B ( u ) = 1 ] < ( 1 − k /∣Σ∣ ) w (ordinary) strategy of width w w w F ∨ B F \vee B F ∨ B
The remainder of this section is devoted to proving this lemma. Let us identify Σ = [ n ] \Sigma= [n] Σ = [ n ] F ∨ B F \vee B F ∨ B k k k F F F k k k F \mathcal{F} F F F F ρ ∈ F \rho\in\mathcal{F} ρ ∈ F
cube ( ρ ) ⊈ B − 1 ( 1 ) . (4) \operatorname{cube}(\rho) \not\subseteq B^{-1}(1). \tag*{(4)} cube ( ρ ) ⊆ B − 1 ( 1 ) . (4) Then no ρ ∈ F \rho\in\mathcal{F} ρ ∈ F F F F B B B x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m F F F ρ \rho ρ n − k n-k n − k ρ ∪ { x i = j } \rho\cup\{x_i=j\} ρ ∪ { x i = j } F \mathcal{F} F k = 0 k=0 k = 0
cube ( ρ ) ∖ B − 1 ( 1 ) = ⨆ j ∈ [ n ] ( cube ( ρ ∪ { x i = j } ) ∖ B − 1 ( 1 ) ) , (5) \operatorname{cube}(\rho) \setminus B^{-1}(1) = \bigsqcup_{j \in[n]} \left(\operatorname{cube}(\rho\cup\{x_i=j\}) \setminus B^{-1}(1)\right), \tag*{(5)} cube ( ρ ) ∖ B − 1 ( 1 ) = j ∈ [ n ] ⨆ ( cube ( ρ ∪ { x i = j }) ∖ B − 1 ( 1 ) ) , (5) so if the left-hand side is non-empty, then at least one of the terms on the right-hand is non-empty. Hence, ρ \rho ρ k = 1 k=1 k = 1
We resolve this by using the linear algebraic embedding of Razborov [Raz03] developed for the pseudowidth method. The high-level idea is to forget about which holes are occupied by pigeons under ρ \rho ρ i ∈ [ m ] i \in[m] i ∈ [ m ] V i = R n − k V_i = \mathbb{R}^{n-k} V i = R n − k v i , 1 , … , v i , n v_{i,1},\ldots,v_{i,n} v i , 1 , … , v i , n n − k n-k n − k V : = ⨂ i ∈ [ m ] V i V := \bigotimes_{i \in[m]} V_i V := ⨂ i ∈ [ m ] V i L : [ n ] m → V L : [n]^m \to V L : [ n ] m → V x ∈ Σ m x \in\Sigma^m x ∈ Σ m ⨂ i ∈ [ m ] v i , x i \bigotimes_{i \in[m]} v_{i,x_i} ⨂ i ∈ [ m ] v i , x i A ⊆ [ n ] m A \subseteq[n]^m A ⊆ [ n ] m L ( A ) : = span { L ( x ) ∣ x ∈ A } L(A) := \operatorname{span}\{L(x) \mid x \in A\} L ( A ) := span { L ( x ) ∣ x ∈ A } L ( ρ ) : = L ( cube ( ρ ) ) L(\rho) := L(\operatorname{cube}(\rho)) L ( ρ ) := L ( cube ( ρ ))
F ′ : = { ρ ∈ F ∣ L ( ρ ) ⊈ L ( B − 1 ( 1 ) ) } \mathcal{F}' := \{\rho\in\mathcal{F} \mid L(\rho) \not\subseteq L(B^{-1}(1))\} F ′ := { ρ ∈ F ∣ L ( ρ ) ⊆ L ( B − 1 ( 1 ))} is a width-w w w F ∨ B F \vee B F ∨ B ρ \rho ρ x i x_i x i n − k n-k n − k Σ \Sigma Σ x i x_i x i n − k n-k n − k ρ \rho ρ L ( ρ ) L(\rho) L ( ρ )
Lemma 32. For every M ∈ ( Σ n − k ) M \in\binom{\Sigma}{n-k} M ∈ ( n − k Σ ) i ∉ fix ( ρ ) i \notin\operatorname{fix}(\rho) i ∈ / fix ( ρ ) L ( ρ ) = ∑ j ∈ M L ( ρ ∪ { x i = j } ) L(\rho) = \sum_{j \in M} L(\rho\cup\{x_i=j\}) L ( ρ ) = ∑ j ∈ M L ( ρ ∪ { x i = j })
Proof. By definition we have:
L ( ρ ) = ⨂ t ∈ fix ( ρ ) span ( v t , ρ ( t ) ) ⊗ V i ⊗ ⨂ ℓ ∈ [ m ] ∖ ( fix ( ρ ) ∪ { i } ) V ℓ = ⨂ t ∈ fix ( ρ ) span ( v t , ρ ( t ) ) ⊗ span { v i , j ∣ j ∈ M } ⊗ ⨂ ℓ ∈ [ m ] ∖ ( fix ( ρ ) ∪ { i } ) V ℓ . (6) \begin{aligned}
L(\rho) &= \bigotimes_{t \in\operatorname{fix}(\rho)} \operatorname{span}(v_{t,\rho(t)}) \otimes V_i \otimes\bigotimes_{\ell\in[m]\setminus(\operatorname{fix}(\rho)\cup\{i\})} V_\ell\\
&= \bigotimes_{t \in\operatorname{fix}(\rho)} \operatorname{span}(v_{t,\rho(t)}) \otimes\operatorname{span}\{v_{i,j} \mid j \in M\} \otimes\bigotimes_{\ell\in[m]\setminus(\operatorname{fix}(\rho)\cup\{i\})} V_\ell. \tag*{(6)}
\end{aligned} L ( ρ ) = t ∈ fix ( ρ ) ⨂ span ( v t , ρ ( t ) ) ⊗ V i ⊗ ℓ ∈ [ m ] ∖ ( fix ( ρ ) ∪ { i }) ⨂ V ℓ = t ∈ fix ( ρ ) ⨂ span ( v t , ρ ( t ) ) ⊗ span { v i , j ∣ j ∈ M } ⊗ ℓ ∈ [ m ] ∖ ( fix ( ρ ) ∪ { i }) ⨂ V ℓ . (6) Then by the property of tensor products we can rewrite
L ( ρ ) = ∑ j ∈ M ⨂ t ∈ fix ( ρ ) span ( v t , ρ ( t ) ) ⊗ span ( v i , j ) ⊗ ⨂ ℓ ∈ [ m ] ∖ ( fix ( ρ ) ∪ { i } ) V ℓ = ∑ j ∈ M L ( ρ ∪ { x i = j } ) . L(\rho)=\sum_{j\in M}\bigotimes_{t\in\operatorname{fix}(\rho)}\operatorname{span}(v_{t,\rho(t)})\otimes\operatorname{span}(v_{i,j})\otimes\bigotimes_{\ell\in[m]\setminus(\operatorname{fix}(\rho)\cup\{i\})}V_\ell=\sum_{j\in M}L(\rho\cup\{x_i=j\}). L ( ρ ) = j ∈ M ∑ t ∈ fix ( ρ ) ⨂ span ( v t , ρ ( t ) ) ⊗ span ( v i , j ) ⊗ ℓ ∈ [ m ] ∖ ( fix ( ρ ) ∪ { i }) ⨂ V ℓ = j ∈ M ∑ L ( ρ ∪ { x i = j }) . It follows that F ′ \mathcal{F}' F ′ ρ ∈ F ′ \rho\in\mathcal{F}' ρ ∈ F ′ L ( ρ ) ⊈ L ( B − 1 ( 1 ) ) L(\rho)\not\subseteq L(B^{-1}(1)) L ( ρ ) ⊆ L ( B − 1 ( 1 )) i ∈ [ m ] ∖ fix ( ρ ) i\in[m]\setminus\operatorname{fix}(\rho) i ∈ [ m ] ∖ fix ( ρ ) ρ ∈ F \rho\in\mathcal{F} ρ ∈ F k k k F \mathcal{F} F M = { j ∈ [ n ] ∣ ρ ∪ { x i = j } ∈ F } M=\{j\in[n]\mid\rho\cup\{x_i=j\}\in\mathcal{F}\} M = { j ∈ [ n ] ∣ ρ ∪ { x i = j } ∈ F } n − k n-k n − k j ∈ M j\in M j ∈ M L ( ρ ∪ { x i = j } ) ⊆ L ( B − 1 ( 1 ) ) L(\rho\cup\{x_i=j\})\subseteq L(B^{-1}(1)) L ( ρ ∪ { x i = j }) ⊆ L ( B − 1 ( 1 )) ∑ j ∈ M L ( ρ ∪ { x i = j } ) = L ( ρ ) \sum_{j\in M}L(\rho\cup\{x_i=j\})=L(\rho) ∑ j ∈ M L ( ρ ∪ { x i = j }) = L ( ρ ) L ( B − 1 ( 1 ) ) L(B^{-1}(1)) L ( B − 1 ( 1 )) L ( ρ ) ⊆ L ( B − 1 ( 1 ) ) L(\rho)\subseteq L(B^{-1}(1)) L ( ρ ) ⊆ L ( B − 1 ( 1 ))
The remaining issue is the non-triviality of F ′ \mathcal{F}' F ′ ⋆ m ∈ F ′ \star^m\in\mathcal{F}' ⋆ m ∈ F ′ V = L ( ⋆ m ) ⊈ L ( B − 1 ( 1 ) ) V=L(\star^m)\not\subseteq L(B^{-1}(1)) V = L ( ⋆ m ) ⊆ L ( B − 1 ( 1 )) A A A dim ( L ( A ) ) \dim(L(A)) dim ( L ( A ))
Lemma 33. For every w w w B B B
dim ( L ( B − 1 ( 1 ) ) ) dim ( V ) ≤ ( 1 − k n ) − w ⋅ Pr u ∼ [ n ] m [ B ( u ) = 1 ] . \frac{\dim(L(B^{-1}(1)))}{\dim(V)}\leq\left(1-\frac{k}{n}\right)^{-w}\cdot\Pr_{u\sim[n]^m}[B(u)=1]. dim ( V ) dim ( L ( B − 1 ( 1 ))) ≤ ( 1 − n k ) − w ⋅ u ∼ [ n ] m Pr [ B ( u ) = 1 ] . Given Lemma 33 , we can conclude the proof of Lemma 31: Pr [ B ( u ) = 1 ] < ( 1 − k / n ) w \Pr[B(u)=1]<(1-k/n)^w Pr [ B ( u ) = 1 ] < ( 1 − k / n ) w dim ( L ( B − 1 ( 1 ) ) ) < dim ( V ) \dim(L(B^{-1}(1)))<\dim(V) dim ( L ( B − 1 ( 1 ))) < dim ( V ) F ′ ∋ ⋆ m \mathcal{F}'\ni\star^m F ′ ∋ ⋆ m
Proof of Lemma 33 . Let B 1 , … , B h B_1,\ldots,B_h B 1 , … , B h B B B B ≤ i = ⋁ j ≤ i B j B_{\leq i}=\bigvee_{j\leq i}B_j B ≤ i = ⋁ j ≤ i B j i i i B ≤ i − 1 B_{\leq i-1} B ≤ i − 1 B ≤ i B_{\leq i} B ≤ i Z i : = B i − 1 ( 1 ) Z_i:=B_i^{-1}(1) Z i := B i − 1 ( 1 ) Z ≤ i : = ⋃ j ≤ i Z j Z_{\leq i}:=\bigcup_{j\leq i}Z_j Z ≤ i := ⋃ j ≤ i Z j Z : = B − 1 ( 1 ) Z:=B^{-1}(1) Z := B − 1 ( 1 )
dim ( L ( Z ≤ i ) ) − dim ( L ( Z < i ) ) ≤ ( n − k n ) m − w ∣ Z i ∖ Z < i ∣ . (7) \dim(L(Z_{\leq i}))-\dim(L(Z_{<i}))\leq\left(\frac{n-k}{n}\right)^{m-w}\lvert Z_i\setminus Z_{<i}\rvert. \tag*{(7)} dim ( L ( Z ≤ i )) − dim ( L ( Z < i )) ≤ ( n n − k ) m − w ∣ Z i ∖ Z < i ∣ . (7) We postpone the proof of this inequality and first complete the proof of the lemma. Summing over all i i i
dim ( L ( Z ) ) ≤ ( n − k n ) m − w ( ∑ i ∣ Z i ∖ Z < i ∣ ) = ( n − k n ) m − w ∣ Z ∣ . \dim(L(Z))\leq\left(\frac{n-k}{n}\right)^{m-w}\left(\sum_i\lvert Z_i\setminus Z_{<i}\rvert\right)=\left(\frac{n-k}{n}\right)^{m-w}\lvert Z\rvert. dim ( L ( Z )) ≤ ( n n − k ) m − w ( i ∑ ∣ Z i ∖ Z < i ∣ ) = ( n n − k ) m − w ∣ Z ∣ . Hence,
dim ( L ( Z ) ) dim ( V ) ≤ ( ( n − k ) / n ) m − w ( n − k ) m ∣ Z ∣ = ( n − k n ) − w ∣ Z ∣ n − m = ( 1 − k n ) − w ⋅ Pr u ∼ [ n ] m [ B ( u ) = 1 ] . \frac{\dim(L(Z))}{\dim(V)}\leq\frac{((n-k)/n)^{m-w}}{(n-k)^m}\lvert Z\rvert=\left(\frac{n-k}{n}\right)^{-w}\lvert Z\rvert n^{-m}=\left(1-\frac{k}{n}\right)^{-w}\cdot\Pr_{u\sim[n]^m}[B(u)=1]. dim ( V ) dim ( L ( Z )) ≤ ( n − k ) m (( n − k ) / n ) m − w ∣ Z ∣ = ( n n − k ) − w ∣ Z ∣ n − m = ( 1 − n k ) − w ⋅ u ∼ [ n ] m Pr [ B ( u ) = 1 ] . To prove Equation (7) we will use the following claim which bounds the dimension of a set as a function of its size.
Claim 34. For any partial assignment ρ : [ m ] → [ n ] ∪ { ⋆ } \rho:[m]\to[n]\cup\{\star\} ρ : [ m ] → [ n ] ∪ { ⋆ } A ⊆ cube ( ρ ) A\subseteq\operatorname{cube}(\rho) A ⊆ cube ( ρ )
dim ( L ( A ) ) ≥ ( n − k n ) m − ∣ fix ( ρ ) ∣ ∣ A ∣ . \dim(L(A))\geq\left(\frac{n-k}{n}\right)^{m-\lvert\operatorname{fix}(\rho)\rvert}\lvert A\rvert. dim ( L ( A )) ≥ ( n n − k ) m − ∣ fix ( ρ )∣ ∣ A ∣ . In particular, dim ( L ( Z i ) ) ≥ ( ( n − k ) / n ) m − w \dim(L(Z_i))\geq((n-k)/n)^{m-w} dim ( L ( Z i )) ≥ (( n − k ) / n ) m − w
Proof. First, we prove that for any A ⊆ [ n ] m A\subseteq[n]^m A ⊆ [ n ] m dim ( L ( A ) ) ≥ ∣ A ∣ ( ( n − k ) / n ) m \dim(L(A))\geq\lvert A\rvert((n-k)/n)^m dim ( L ( A )) ≥ ∣ A ∣ (( n − k ) / n ) m i ∈ [ m ] i\in[m] i ∈ [ m ] B i ∼ ( [ n ] n − k ) B_i\sim\binom{[n]}{n-k} B i ∼ ( n − k [ n ] ) L ( B i ) L(B_i) L ( B i ) B = ∏ i ∈ [ m ] B i B=\prod_{i\in[m]}B_i B = ∏ i ∈ [ m ] B i
dim ( L ( A ∩ B ) ) = ∣ A ∩ B ∣ , \dim(L(A\cap B))=\lvert A\cap B\rvert, dim ( L ( A ∩ B )) = ∣ A ∩ B ∣ , by linear independence. That is, B i B_i B i i i i B i B_i B i
dim ( L ( A ) ) ≥ E [ dim ( L ( A ∩ B ) ) ] = E [ ∣ A ∩ B ∣ ] = ∣ A ∣ ( n − k n ) m , \dim(L(A))\geq\mathbb{E}[\dim(L(A\cap B))]=\mathbb{E}[\lvert A\cap B\rvert]=\lvert A\rvert\left(\frac{n-k}{n}\right)^m, dim ( L ( A )) ≥ E [ dim ( L ( A ∩ B ))] = E [∣ A ∩ B ∣] = ∣ A ∣ ( n n − k ) m , where the final equality is the probability that each element in B B B A A A ρ \rho ρ A ⊆ cube ( ρ ) A\subseteq\operatorname{cube}(\rho) A ⊆ cube ( ρ )
dim ( L ( A ) ) ≥ ( n − k n ) m − ∣ fix ( ρ ) ∣ ∣ A ∣ . \dim(L(A))\geq\left(\frac{n-k}{n}\right)^{m-\lvert\operatorname{fix}(\rho)\rvert}\lvert A\rvert. dim ( L ( A )) ≥ ( n n − k ) m − ∣ fix ( ρ )∣ ∣ A ∣ . We now prove Equation (7) . First note that without loss of generality we can assume every term in B B B w w w B i B_i B i t t t t + 1 t+1 t + 1 x j x_j x j B i B_i B i ⋁ a ∈ [ n ] B i ∧ [ [ x j = a ] ] \bigvee_{a\in[n]} B_i \land[[x_j=a]] ⋁ a ∈ [ n ] B i ∧ [[ x j = a ]]
( n − k n ) m − w ∣ Z i ∖ Z < i ∣ = ( n − k n ) m − w ( ∣ Z i ∣ − ∣ Z i ∩ Z < i ∣ ) = ( n − k n ) m − w ( n m − w − ∣ Z i ∩ Z < i ∣ ) ≥ ( n − k ) m − w − dim ( L ( Z i ∩ Z < i ) ) (Applying xref‘Claim 34‘) = dim ( L ( Z i ) ) − dim ( L ( Z i ∩ Z < i ) ) ≥ dim ( L ( Z ≤ i ) ) − dim ( L ( Z < i ) ) , \begin{aligned}
\left(\frac{n-k}{n}\right)^{m-w}|Z_i \setminus Z_{<i}| = \left(\frac{n-k}{n}\right)^{m-w}\left(|Z_i|-|Z_i\cap Z_{<i}|\right) \\
&= \left(\frac{n-k}{n}\right)^{m-w}\left(n^{m-w}-|Z_i\cap Z_{<i}|\right) \\
&\ge(n-k)^{m-w}-\dim(L(Z_i\cap Z_{<i})) \qquad\text{(Applying {xref}`Claim 34`)} \\
&= \dim(L(Z_i))-\dim(L(Z_i\cap Z_{<i})) \\
&\ge\dim(L(Z_{\le i}))-\dim(L(Z_{<i})),
\end{aligned} ( n n − k ) m − w ∣ Z i ∖ Z < i ∣ = ( n n − k ) m − w ( ∣ Z i ∣ − ∣ Z i ∩ Z < i ∣ ) = ( n n − k ) m − w ( n m − w − ∣ Z i ∩ Z < i ∣ ) ≥ ( n − k ) m − w − dim ( L ( Z i ∩ Z < i )) (Applying xref ‘Claim 34‘) = dim ( L ( Z i )) − dim ( L ( Z i ∩ Z < i )) ≥ dim ( L ( Z ≤ i )) − dim ( L ( Z < i )) , where the final inequality follows by applying the next Lemma 35 with B = Z i ∩ Z < i B=Z_i\cap Z_{<i} B = Z i ∩ Z < i A = Z i ∖ Z < i A=Z_i\setminus Z_{<i} A = Z i ∖ Z < i C = Z < i ∖ Z i C=Z_{<i}\setminus Z_i C = Z < i ∖ Z i
Lemma 35. For any disjoint sets A A A B B B C C C
dim ( L ( A ∪ B ) ) − dim ( L ( B ) ) ≥ dim ( L ( A ∪ B ∪ C ) ) − dim ( L ( B ∪ C ) ) . \dim(L(A\cup B))-\dim(L(B))\ge\dim(L(A\cup B\cup C))-\dim(L(B\cup C)). dim ( L ( A ∪ B )) − dim ( L ( B )) ≥ dim ( L ( A ∪ B ∪ C )) − dim ( L ( B ∪ C )) . Proof. Let A A A B B B C C C
dim ( L ( A ∪ B ) ) − dim ( L ( B ) ) = dim ( L ( A ) ) − dim ( L ( A ) ∩ L ( B ) ) ≥ dim ( L ( A ) ) − dim ( L ( A ) ∩ L ( B ∪ C ) ) = dim ( L ( A ∪ B ∪ C ) ) − dim ( L ( B ∪ C ) ) , \begin{aligned}
\dim(L(A\cup B))-\dim(L(B))=\dim(L(A))-\dim(L(A)\cap L(B)) \\
&\ge\dim(L(A))-\dim(L(A)\cap L(B\cup C)) \\
&=\dim(L(A\cup B\cup C))-\dim(L(B\cup C)),
\end{aligned} dim ( L ( A ∪ B )) − dim ( L ( B )) = dim ( L ( A )) − dim ( L ( A ) ∩ L ( B )) ≥ dim ( L ( A )) − dim ( L ( A ) ∩ L ( B ∪ C )) = dim ( L ( A ∪ B ∪ C )) − dim ( L ( B ∪ C )) , where the final line follows by adding B ∪ C B\cup C B ∪ C
PWPP is not in PLS
In this section we show that PWPP is not contained within PLS under public reductions.
Theorem 36. Let ( ω , f , g ) (\omega,f,g) ( ω , f , g ) ω ( u ) = u \omega(u)=u ω ( u ) = u w ≤ n 1 / 3 w\le n^{1/3} w ≤ n 1/3 [ n ] 2 n [n]^{2n} [ n ] 2 n err ( ω , f , g ) = 1 − n − Ω ( 1 ) \operatorname{err}(\omega,f,g)=1-n^{-\Omega(1)} err ( ω , f , g ) = 1 − n − Ω ( 1 )
Consider the problem Pigeon ⊆ [ n ] m × ( [ m ] 2 ) \subseteq[n]^m\times\binom{[m]}{2} ⊆ [ n ] m × ( 2 [ m ] ) m > n m>n m > n x i = x j x_i=x_j x i = x j x ∈ [ n ] m x\in[n]^m x ∈ [ n ] m m = 2 n m=2n m = 2 n ( ω , f , g ) (\omega,f,g) ( ω , f , g ) ω ( u ) = u \omega(u)=u ω ( u ) = u d d d w = d + log M w=d+\log M w = d + log M M ≥ 4 M\ge4 M ≥ 4 B B B 3 d + 2 ≤ 3 w 3d+2\le3w 3 d + 2 ≤ 3 w ∨ B \vee B ∨ B O ( w ) O(w) O ( w ) Pr u ∼ [ n ] m [ B ( u ) = 1 ] = err ( ω , f , g ) \Pr_{u\sim[n]^m}[B(u)=1]=\operatorname{err}(\omega,f,g) Pr u ∼ [ n ] m [ B ( u ) = 1 ] = err ( ω , f , g ) C C C W = ⌈ C w ⌉ W=\lceil Cw\rceil W = ⌈ C w ⌉
err ( ω , f , g ) ≥ ( 1 − W / n ) W ≥ 1 − W 2 / n = 1 − O ( w 2 / n ) , \operatorname{err}(\omega,f,g)\ge(1-W/n)^W\ge1-W^2/n=1-O(w^2/n), err ( ω , f , g ) ≥ ( 1 − W / n ) W ≥ 1 − W 2 / n = 1 − O ( w 2 / n ) , which proves Theorem 36 for w ≤ n 1 / 3 w\le n^{1/3} w ≤ n 1/3 n n n
Lemma 37. If B B B w w w Pr u ∼ [ n ] m [ B ( u ) = 1 ] < ( 1 − w / n ) w \Pr_{u\sim[n]^m}[B(u)=1]<(1-w/n)^w Pr u ∼ [ n ] m [ B ( u ) = 1 ] < ( 1 − w / n ) w w w w ∨ B \vee B ∨ B
Proof. By Lemma 31 it suffices to show that Pigeon has a w w w w w w F \mathcal{F} F w w w F \mathcal{F} F ρ ∈ F \rho\in\mathcal{F} ρ ∈ F i ∈ free ( ρ ) i\in\operatorname{free}(\rho) i ∈ free ( ρ ) j ∈ [ n ] ∖ range ( ρ ) j\in[n]\setminus\operatorname{range}(\rho) j ∈ [ n ] ∖ range ( ρ ) n − w n-w n − w ρ ∪ { p i = j } \rho\cup\{p_i=j\} ρ ∪ { p i = j } ∣ fix ( ρ ) ∣ < w |\operatorname{fix}(\rho)|<w ∣ fix ( ρ ) ∣ < w ρ ∪ { p i = j } ∈ F \rho\cup\{p_i=j\}\in\mathcal{F} ρ ∪ { p i = j } ∈ F
As a consequence, we can also obtain average-case resolution size lower bounds. In terms of Definition 1 the size is ∣ F ∣ |F| ∣ F ∣ ρ \rho ρ i ( ρ ) i(\rho) i ( ρ ) ρ \rho ρ F F F [61 Proposition 3.7] .
Corollary 38. For any DNF B B B Pr u ∼ [ n ] m [ B ( u ) = 1 ] < ( 1 − w / n ) w − 1 / n \Pr_{u\sim[n]^m}[B(u)=1] < (1-w/n)^{w}-1/n Pr u ∼ [ n ] m [ B ( u ) = 1 ] < ( 1 − w / n ) w − 1/ n Pigeon ∨ B \operatorname{Pigeon}\vee B Pigeon ∨ B n w n^w n w
Proof. Suppose F F F Pigeon ∨ B \operatorname{Pigeon}\vee B Pigeon ∨ B < n w < n^w < n w F F F > w >w > w F F F B ′ B' B ′ Pr [ B ′ ( u ) = 1 ] < n w ⋅ n − ( w + 1 ) = 1 / n \Pr[B'(u)=1] < n^w\cdot n^{-(w+1)}=1/n Pr [ B ′ ( u ) = 1 ] < n w ⋅ n − ( w + 1 ) = 1/ n ( w + 1 ) (w+1) ( w + 1 ) Pigeon ∨ B ∨ B ′ \operatorname{Pigeon}\vee B\vee B' Pigeon ∨ B ∨ B ′ Lemma 37 .
PPA is not in PLS
The preceding PPAD ∉ \notin ∈ / ∉ \notin ∈ /
The problem is again to find an edge in the hypergraph G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) Theorem 10 : given a labeling h : [ N ] → { 0 , 1 } r h:[N]\to\{0,1\}^r h : [ N ] → { 0 , 1 } r e ∈ E e\in E e ∈ E ⨁ v ∈ e h ( v ) = 0 r \bigoplus_{v\in e}h(v)=0^r ⨁ v ∈ e h ( v ) = 0 r e ∗ = [ ℓ ] e^*=[\ell] e ∗ = [ ℓ ] h ( 1 ) = ⋯ = h ( ℓ ) = 0 r h(1)=\cdots=h(\ell)=0^r h ( 1 ) = ⋯ = h ( ℓ ) = 0 r H \mathcal{H} H e ∗ e^* e ∗
ZeroEdge G : = { ( h , e ) ∈ H × ( E ∖ { e ∗ } ) : ⨁ v ∈ e h ( v ) = 0 r } . \operatorname{ZeroEdge}_G:=\{(h,e)\in\mathcal{H}\times(E\setminus\{e^*\}):\bigoplus_{v\in e}h(v)=0^r\}. ZeroEdge G := {( h , e ) ∈ H × ( E ∖ { e ∗ }) : v ∈ e ⨁ h ( v ) = 0 r } . The reason for this change is in order to make ZeroEdge G \operatorname{ZeroEdge}_G ZeroEdge G
Theorem 39. There exists G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) ZeroEdge G ∈ P P A \operatorname{ZeroEdge}_G\in\mathrm{PPA} ZeroEdge G ∈ PPA ZeroEdge G \operatorname{ZeroEdge}_G ZeroEdge G exp ( ( log N ) o ( 1 ) ) \exp((\log N)^{o(1)}) exp (( log N ) o ( 1 ) )
The theorem immediately follows from Lemmas 40 and 41 below:
Lemma 40. Suppose G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) E ⊆ ( [ N ] ℓ ) E\subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) ( ℓ , w + ℓ , b ) (\ell,w+\ell,b) ( ℓ , w + ℓ , b ) b b b w w w ZeroEdge G \operatorname{ZeroEdge}_G ZeroEdge G
Lemma 41. If G = ( [ N ] , E ) G=([N],E) G = ([ N ] , E ) E ⊆ ( [ N ] ℓ ) E\subseteq\binom{[N]}{\ell} E ⊆ ( ℓ [ N ] ) r r r ℓ = poly ( log N ) \ell=\operatorname{poly}(\log N) ℓ = poly ( log N ) ZeroEdge G ∈ P P A \operatorname{ZeroEdge}_G\in\mathrm{PPA} ZeroEdge G ∈ PPA
Proof of Theorem 39. The graph supplied by Theorem 10 satisfies the preconditions of Lemmas 40 and 41 simultaneously. Then by Lemma 31 and the robust strategy given by Lemma 40 we get that for every DNF B B B w = exp ( ( log N ) o ( 1 ) ) w=\exp((\log N)^{o(1)}) w = exp (( log N ) o ( 1 ) ) Pr [ B ( u ) = 1 ] ≤ 1 / 3 \Pr[B(u)=1]\le1/3 Pr [ B ( u ) = 1 ] ≤ 1/3 w w w ZeroEdge G ∨ B \operatorname{ZeroEdge}_G\vee B ZeroEdge G ∨ B ZeroEdge G \operatorname{ZeroEdge}_G ZeroEdge G
PLS hardness: proof of Lemma 40
Let L \mathcal{L} L ρ : [ N ] ∖ [ ℓ ] → { 0 , 1 } r ∪ { ⋆ } \rho:[N]\setminus[\ell]\to\{0,1\}^r\cup\{\star\} ρ : [ N ] ∖ [ ℓ ] → { 0 , 1 } r ∪ { ⋆ } ρ ∈ L \rho\in\mathcal{L} ρ ∈ L e ∈ E e\in E e ∈ E ρ ( v ) ≠ ⋆ \rho(v)\ne\star ρ ( v ) = ⋆ v ∈ e ∖ [ ℓ ] v\in e\setminus[\ell] v ∈ e ∖ [ ℓ ] ⨁ v ∈ e ∖ [ ℓ ] ρ ( v ) = 0 \bigoplus_{v\in e\setminus[\ell]}\rho(v)=0 ⨁ v ∈ e ∖ [ ℓ ] ρ ( v ) = 0
F : = { ρ ∈ L ∣ fix ( ρ ) ≤ w and ρ does not reveal any edge e ∈ E ∖ { e ∗ } } . \mathcal{F}:=\{\rho\in\mathcal{L}\mid\operatorname{fix}(\rho)\le w\text{ and }\rho\text{ does not reveal any edge }e\in E\setminus\{e^*\}\}. F := { ρ ∈ L ∣ fix ( ρ ) ≤ w and ρ does not reveal any edge e ∈ E ∖ { e ∗ }} . Take any ρ ∈ F \rho\in\mathcal{F} ρ ∈ F w w w v ∈ ( [ N ] ∖ [ ℓ ] ) ∖ fix ( ρ ) v\in([N]\setminus[\ell])\setminus\operatorname{fix}(\rho) v ∈ ([ N ] ∖ [ ℓ ]) ∖ fix ( ρ ) b b b F ⊆ E F\subseteq E F ⊆ E fix ( ρ ) ∪ [ ℓ ] ∪ { v } \operatorname{fix}(\rho)\cup[\ell]\cup\{v\} fix ( ρ ) ∪ [ ℓ ] ∪ { v } ℓ \ell ℓ ρ \rho ρ v v v e ∈ F e\in F e ∈ F v ∈ e v\in e v ∈ e f e : = ⨁ z ∈ e ∖ { v } ρ ( z ) f_e:=\bigoplus_{z\in e\setminus\{v\}}\rho(z) f e := ⨁ z ∈ e ∖ { v } ρ ( z ) h ( v ) h(v) h ( v ) e e e ZeroEdge G \operatorname{ZeroEdge}_G ZeroEdge G α ∈ { 0 , 1 } r ∖ { f e ∣ e ∈ F ; v ∈ e } \alpha\in\{0,1\}^r\setminus\{f_e\mid e\in F;v\in e\} α ∈ { 0 , 1 } r ∖ { f e ∣ e ∈ F ; v ∈ e } ρ ∪ { h ( v ) = α } ∈ F \rho\cup\{h(v)=\alpha\}\in\mathcal{F} ρ ∪ { h ( v ) = α } ∈ F ∣ F ∣ ≤ b |F|\le b ∣ F ∣ ≤ b b b b
PPA containment: proof of Lemma 41
We follow exactly the same strategy as in the PPAD case: encode ZeroEdge as a system of polynomials which is unsatisfiable over the Boolean cube and show that it has a short F 2 \mathbb{F}_{2} F 2 [30 ] . For every a ∈ [ N ] ∖ [ ℓ ] a \in[N] \setminus[\ell] a ∈ [ N ] ∖ [ ℓ ] j ∈ [ r ] j \in[r] j ∈ [ r ] h a , j h_{a,j} h a , j
h ( a ) = ( h a , 1 , … , h a , r ) ∈ { 0 , 1 } r . h(a) = (h_{a,1}, \ldots, h_{a,r}) \in\{0,1\}^{r}. h ( a ) = ( h a , 1 , … , h a , r ) ∈ { 0 , 1 } r . Set h a , j : = 0 h_{a,j} := 0 h a , j := 0 a ∈ [ ℓ ] a \in[\ell] a ∈ [ ℓ ] j ∈ [ r ] j \in[r] j ∈ [ r ] h ( 1 ) = ⋯ = h ( ℓ ) = 0 r h(1) = \cdots= h(\ell) = 0^{r} h ( 1 ) = ⋯ = h ( ℓ ) = 0 r h = { h a , j ∣ a ∈ [ N ] ∖ [ ℓ ] , j ∈ [ r ] } h = \{h_{a,j} \mid a \in[N] \setminus[\ell], j \in[r]\} h = { h a , j ∣ a ∈ [ N ] ∖ [ ℓ ] , j ∈ [ r ]} h h h n : = ( N − ℓ ) r n := (N-\ell)r n := ( N − ℓ ) r
For an edge e ∈ E e \in E e ∈ E
F e ( h ) = ∑ v ∈ e h ( v ) ∈ F 2 r , F e ( h ) j = ∑ v ∈ e h v , j . F_e(h) = \sum_{v \in e} h(v) \in\mathbb{F}_2^r,\qquad F_e(h)_j = \sum_{v \in e} h_{v,j}. F e ( h ) = v ∈ e ∑ h ( v ) ∈ F 2 r , F e ( h ) j = v ∈ e ∑ h v , j . where the first sum is coordinate-wise XOR and the second sum is over F 2 \mathbb{F}_2 F 2
P G = { p e ( h ) ∣ e ∈ E ∖ { e ∗ } } , p e ( h ) = ∏ j = 1 r ( 1 + ∑ v ∈ e h v , j ) . (8) \mathcal{P}_G = \{p_e(h) \mid e \in E \setminus\{e^*\}\},\qquad p_e(h) = \prod_{j=1}^{r}\left(1+\sum_{v \in e} h_{v,j}\right). \tag*{(8)} P G = { p e ( h ) ∣ e ∈ E ∖ { e ∗ }} , p e ( h ) = j = 1 ∏ r ( 1 + v ∈ e ∑ h v , j ) . (8) Every polynomial is over F 2 \mathbb{F}_2 F 2 P G \mathcal{P}_G P G
p e ( h ) = 1 ⟺ F e ( h ) = 0 r . p_e(h)=1 \quad\Longleftrightarrow\quad F_e(h)=0^r. p e ( h ) = 1 ⟺ F e ( h ) = 0 r . The next lemma shows that if E E E r r r ( P G ) (\mathcal{P}_G) ( P G ) G _G G 2 _2 2 P G \mathcal{P}_G P G [30 ] implies a black-box containment ZeroEdgeG ∈ P P A d t _G \in\mathrm{PPA}^{\mathrm{dt}} G ∈ PPA dt
Lemma 42 (NS2 _2 2 P G \mathcal{P}_G P G The system P G \mathcal{P}_G P G 2 _2 2
1 = ∑ e ∈ E ∖ { e ∗ } p e ( h ) ( m o d 2 ) . 1 = \sum_{e \in E \setminus\{e^*\}} p_e(h) \pmod2. 1 = e ∈ E ∖ { e ∗ } ∑ p e ( h ) ( mod 2 ) . Furthermore, the NS2 _2 2 ∑ e ∈ E ∖ { e ∗ } p e \sum_{e \in E \setminus\{e^*\}} p_e ∑ e ∈ E ∖ { e ∗ } p e r r r ∣ E ∣ ( ℓ + 1 ) r |E|(\ell+1)^r ∣ E ∣ ( ℓ + 1 ) r
Proof. Let p e ∗ ( h ) p_{e^*}(h) p e ∗ ( h ) P G \mathcal{P}_G P G p e ∗ ( h ) = ∏ j ∈ [ r ] ( 1 + F e ∗ ( h ) j ) p_{e^*}(h) = \prod_{j \in[r]}(1+F_{e^*}(h)_j) p e ∗ ( h ) = ∏ j ∈ [ r ] ( 1 + F e ∗ ( h ) j ) E E E ∑ e ∈ E p e ( h ) = 0 \sum_{e \in E} p_e(h) = 0 ∑ e ∈ E p e ( h ) = 0 F 2 \mathbb{F}_2 F 2 p e ( h ) p_e(h) p e ( h )
h a 1 , j 1 h a 2 , j 2 ⋯ h a s , j s , h_{a_1,j_1}h_{a_2,j_2}\cdots h_{a_s,j_s}, h a 1 , j 1 h a 2 , j 2 ⋯ h a s , j s , where s ≤ r s \le r s ≤ r j k j_k j k a 1 , … , a s ∈ e a_1,\ldots,a_s \in e a 1 , … , a s ∈ e e e e p e ( h ) p_e(h) p e ( h ) ∑ e ∈ E p e ( h ) \sum_{e \in E}p_e(h) ∑ e ∈ E p e ( h ) p e ( h ) p_e(h) p e ( h ) e e e r r r r r r
On the other hand, since h ( 1 ) = ⋯ = h ( ℓ ) = 0 h(1)=\cdots=h(\ell)=0 h ( 1 ) = ⋯ = h ( ℓ ) = 0 p e ∗ ( h ) = p [ ℓ ] ( h ) p_{e^*}(h)=p_{[\ell]}(h) p e ∗ ( h ) = p [ ℓ ] ( h )
p e ∗ ( h ) = ∏ j ∈ [ r ] ( 1 + F e ∗ ( h ) j ) = ∏ j ∈ [ r ] ( 1 + ∑ i ∈ [ ℓ ] h ( i ) j ) = ∏ j ∈ [ r ] ( 1 + 0 ) = 1. p_{e^*}(h)=\prod_{j\in[r]}(1+F_{e^*}(h)_j)=\prod_{j\in[r]}\left(1+\sum_{i\in[\ell]}h(i)_j\right)=\prod_{j\in[r]}(1+0)=1. p e ∗ ( h ) = j ∈ [ r ] ∏ ( 1 + F e ∗ ( h ) j ) = j ∈ [ r ] ∏ 1 + i ∈ [ ℓ ] ∑ h ( i ) j = j ∈ [ r ] ∏ ( 1 + 0 ) = 1. Therefore since p e ∗ ( h ) = 1 p_{e^*}(h)=1 p e ∗ ( h ) = 1 ∑ e ∈ E p e ( h ) = 0 \sum_{e\in E}p_e(h)=0 ∑ e ∈ E p e ( h ) = 0 ∑ e ∈ E ∖ { e ∗ } p e ( h ) = 1 \sum_{e\in E\setminus\{e^*\}}p_e(h)=1 ∑ e ∈ E ∖ { e ∗ } p e ( h ) = 1 F 2 \mathbb{F}_2 F 2
We have shown not only that P G \mathcal{P}_G P G 2 _2 2 ∑ e p e q e = 1 \sum_e p_eq_e=1 ∑ e p e q e = 1 q e q_e q e P G \mathcal{P}_G P G p e p_e p e r r r ( ℓ + 1 ) r (\ell+1)^r ( ℓ + 1 ) r p e p_e p e ∣ E ∣ ( ℓ + 1 ) r = 2 poly ( ℓ ) |E|(\ell+1)^r = 2^{\operatorname{poly}(\ell)} ∣ E ∣ ( ℓ + 1 ) r = 2 poly ( ℓ )
Figure 5. This picture illustrates the translation with r = 1 r = 1 r = 1 G G G e ∗ = { 1 , 2 } e^* = \{1,2\} e ∗ = { 1 , 2 } h ∈ { 0 , 1 } 8 h \in\{0,1\}^{8} h ∈ { 0 , 1 } 8 h ( 1 ) = h ( 2 ) = 0 h(1) = h(2) = 0 h ( 1 ) = h ( 2 ) = 0 G G G 2 _2 2 ∑ u v ∈ E ( 1 + h u + h v ) = 0 \sum_{uv\in E}(1+h_u+h_v)=0 ∑ uv ∈ E ( 1 + h u + h v ) = 0 ≤ 1 \leq1 ≤ 1 ( e , u ) (e,u) ( e , u ) u ∈ { ⊥ } ∪ e u \in\{\bot\}\cup e u ∈ { ⊥ } ∪ e
Translating from NS2 _2 2 To finish the proof of PPA inclusion, we instantiate the conversion of a F 2 \mathbb{F}_2 F 2 [30 Lemma 13] . Their generic proof does not necessarily imply an efficient instance. We use the fact that G G G efficiently r r r S ⊆ [ N ] S \subseteq[N] S ⊆ [ N ] ≤ r \leq r ≤ r e ⊇ S e \supseteq S e ⊇ S
First recall the canonical PPA-complete problem.
Definition 5. Lonely problem is defined on a single array Mate ∈ ( [ 2 N + 1 ] ) 2 N + 1 \in([2N+1])^{2N+1} ∈ ([ 2 N + 1 ] ) 2 N + 1
i ∈ [ 2 N + 1 ] i \in[2N+1] i ∈ [ 2 N + 1 ] M a t e M a t e i ≠ i \mathrm{Mate}_{\mathrm{Mate}_i} \ne i Mate Mate i = i
i ∈ [ 2 N + 1 ] i \in[2N+1] i ∈ [ 2 N + 1 ] M a t e i = i \mathrm{Mate}_i = i Mate i = i
Every monomial occurrence in the refutation ∑ e ∈ E ∖ { e ∗ } p e ( h ) + 1 = 0 \sum_{e\in E\setminus\{e^*\}}p_e(h)+1=0 ∑ e ∈ E ∖ { e ∗ } p e ( h ) + 1 = 0 ( e , u ) (e,u) ( e , u ) e ∈ E e \in E e ∈ E u ∈ ( e ∪ { ⊥ } ) r u \in(e\cup\{\bot\})^r u ∈ ( e ∪ { ⊥ } ) r V V V ( e ∗ , ⊥ r ) (e^*,\bot^r) ( e ∗ , ⊥ r ) ∣ V ∣ = ∣ E ∣ ( ℓ + 1 ) r − 1 |V|=|E|(\ell+1)^r-1 ∣ V ∣ = ∣ E ∣ ( ℓ + 1 ) r − 1 ( e , u ) (e,u) ( e , u ) m u : = ∏ i ∈ [ r ] : u i ≠ ⊥ h u i , i m_u:=\prod_{i\in[r]:u_i\ne\bot}h_{u_i,i} m u := ∏ i ∈ [ r ] : u i = ⊥ h u i , i u i ∈ e ∗ u_i\in e^* u i ∈ e ∗ h u i , i h_{u_i,i} h u i , i H → V V \mathcal{H}\to V^V H → V V ( e , u ) (e,u) ( e , u ) m u ( h ) = 0 m_u(h)=0 m u ( h ) = 0 syntactic properties of NS2 _2 2 S ⊆ e S\subseteq e S ⊆ e ⊥ \bot ⊥ u u u r r r σ S : E S → E S \sigma_S:E_S\to E_S σ S : E S → E S e e e S S S M a t e e , u ( h ) = ( σ S ( e ) , u ) \mathrm{Mate}_{e,u}(h)=(\sigma_S(e),u) Mate e , u ( h ) = ( σ S ( e ) , u ) e ∈ E ∖ { e ∗ } e\in E\setminus\{e^*\} e ∈ E ∖ { e ∗ } p e ( h ) = 1 p_e(h)=1 p e ( h ) = 1 M a t e e , ⊥ r ( h ) = ( e , ⊥ r ) \mathrm{Mate}_{e,\bot^r}(h)=(e,\bot^r) Mate e , ⊥ r ( h ) = ( e , ⊥ r ) h h h ( h , e ) ∈ (h,e)\in ( h , e ) ∈ p e ( h ) = 0 p_e(h)=0 p e ( h ) = 0 p e p_e p e u ∈ ( e ∪ { ⊥ } ) r u\in(e\cup\{\bot\})^r u ∈ ( e ∪ { ⊥ } ) r m u ( h ) = 1 m_u(h)=1 m u ( h ) = 1 ∏ i ∈ [ r ] ( { ⊥ } ∪ { v ∈ e ∣ h v , i = 1 } ) \prod_{i\in[r]}\bigl(\{\bot\}\cup\{v\in e\mid h_{v,i}=1\}\bigr) ∏ i ∈ [ r ] ( { ⊥ } ∪ { v ∈ e ∣ h v , i = 1 } ) ⊥ r \bot^r ⊥ r p e ( h ) = 1 p_e(h)=1 p e ( h ) = 1
Acknowledgements
Ziyi Guan is funded by the Swiss National Science Foundation (SNSF) through a Postdoc.Mobility fellowship. Oliver Korten is supported by the National Science Foundation under Grant No. DMS-2424441. Artur Riazanov is supported by the Simons Foundation as a Junior Fellow in the Simons Society of Fellows (20599). Noah Fleming is supported by the Swedish Research Council under grant number 2025-06762. Mika Göös and Weiqiang Yuan are supported by the Swiss State Secretariat for Education, Research, and Innovation (SERI) under contract number MB22.00026.
The authors thank Nir Bitansky, Tal Malkin, Yaroslav Alekseev, Gilbert Maystre, Eylon Yogev, and Yiding Zhang for discussions related to this project.
AI disclosure
The separation from P W P P ⊈ P L S \mathrm{PWPP} \not\subseteq\mathrm{PLS} PWPP ⊆ PLS U E o P L \mathrm{UEoPL} UEoPL [3 ] . The separations P P A ⊈ P L S \mathrm{PPA} \not\subseteq\mathrm{PLS} PPA ⊆ PLS P P A D ⊈ F P \mathrm{PPAD} \not\subseteq\mathrm{FP} PPAD ⊆ FP
References
TFNP glossary
In this section, we give formal definitions of all TFNP classes we use. With the exception of the entire class TFNP and the smallest subclass (total) FP that contains efficiently solvable total relations, all subclasses are defined by canonical complete problems. Then if F F F C \mathcal{C} C F ′ ∈ C F' \in\mathcal{C} F ′ ∈ C § 6 ) from F ′ F' F ′ F F F
PPP (Pigeon). We are given Pigeon ∈ [ N ] N + 1 \operatorname{Pigeon} \in[N]^{N+1} Pigeon ∈ [ N ] N + 1
PWPP (WeakPigeon). We are given Pigeon ∈ [ N ] 2 N \operatorname{Pigeon} \in[N]^{2N} Pigeon ∈ [ N ] 2 N
PPA (Lonely). We are given Mate ∈ [ 2 N + 1 ] 2 N + 1 \operatorname{Mate} \in[2N+1]^{2N+1} Mate ∈ [ 2 N + 1 ] 2 N + 1
i ∈ [ 2 N + 1 ] i \in[2N+1] i ∈ [ 2 N + 1 ] Mate i = i \operatorname{Mate}_{i} = i Mate i = i
i ∈ [ 2 N + 1 ] i \in[2N+1] i ∈ [ 2 N + 1 ] Mate Mate i ≠ i \operatorname{Mate}_{\operatorname{Mate}_{i}} \ne i Mate Mate i = i
PPAD (End of Line). We are given Succ , Pred ∈ [ N ] N \operatorname{Succ},\operatorname{Pred} \in[N]^N Succ , Pred ∈ [ N ] N
1 1 1 Pred 1 ≠ 1 \operatorname{Pred}_{1} \ne1 Pred 1 = 1 Succ 1 = 1 \operatorname{Succ}_{1} = 1 Succ 1 = 1 Pred Succ 1 ≠ 1 \operatorname{Pred}_{\operatorname{Succ}_{1}} \ne1 Pred Succ 1 = 1
i ∈ [ N ] ∖ { 1 } i \in[N] \setminus\{1\} i ∈ [ N ] ∖ { 1 } Succ Pred i ≠ i \operatorname{Succ}_{\operatorname{Pred}_{i}} \ne i Succ Pred i = i
i ∈ [ N ] i \in[N] i ∈ [ N ] Pred Succ i ≠ i \operatorname{Pred}_{\operatorname{Succ}_{i}} \ne i Pred Succ i = i
A common grid formulation. For PLS, EoPL, and UEoPL, use the N × N N \times N N × N N ≥ 2 N \ge2 N ≥ 2 S u c c i j ∈ [ N ] ∪ { ⊥ } \mathrm{Succ}_{ij} \in[N] \cup\{\bot\} Succ ij ∈ [ N ] ∪ { ⊥ } i < N i < N i < N ⊥ \bot ⊥ k k k ( i + 1 , k ) (i+1,k) ( i + 1 , k ) active if S u c c i j ≠ ⊥ \mathrm{Succ}_{ij} \ne\bot Succ ij = ⊥ proper sink is an inactive node reached from an active node.
PLS (Sink of Dag). Solutions are
( 1 , 1 ) (1,1) ( 1 , 1 )
( N , j ) (N,j) ( N , j )
( i , j ) (i,j) ( i , j ) i < N i < N i < N ( i + 1 , S u c c i j ) (i+1,\mathrm{Succ}_{ij}) ( i + 1 , Succ ij )
In the third case we output the active predecessor, which witnesses an incoming edge to the inactive sink. This makes the solution locally checkable even though PLS has no predecessor pointers, as in [29 Section 3.2] .
EoPL (End of Potential Line). Add pointers P r e d i j ∈ [ N ] ∪ { ⊥ } \mathrm{Pred}_{ij} \in[N] \cup\{\bot\} Pred ij ∈ [ N ] ∪ { ⊥ } 2 , … , N 2,\ldots,N 2 , … , N i < N i < N i < N ( i , j ) (i,j) ( i , j ) S u c c i j = k ≠ ⊥ \mathrm{Succ}_{ij}=k \ne\bot Succ ij = k = ⊥ P r e d i + 1 , k = j \mathrm{Pred}_{i+1,k}=j Pred i + 1 , k = j N N N S u c c N j ≠ ⊥ \mathrm{Succ}_{Nj} \ne\bot Succ N j = ⊥
( i , j ) (i,j) ( i , j )
( i , j ) ≠ ( 1 , 1 ) (i,j) \ne(1,1) ( i , j ) = ( 1 , 1 ) i < N i < N i < N
In particular, every active node in row 1 except ( 1 , 1 ) (1,1) ( 1 , 1 )
UEoPL (Unique End of Potential Line). Use the same instance, activity, and four solution types as EoPL, and add just one further type:
( i , j ) (i,j) ( i , j ) ( i , j ′ ) (i,j') ( i , j ′ ) j ≠ j ′ j \ne j' j = j ′
TFNP separations in the ROM
In this section, we will give a formal definition of TFNP problems and reductions under the random oracle model. Let Γ a ( n ) , b ( n ) \Gamma_{a(n),b(n)} Γ a ( n ) , b ( n ) γ : { 0 , 1 } a ( n ) → { 0 , 1 } b ( n ) \gamma:\{0,1\}^{a(n)} \to\{0,1\}^{b(n)} γ : { 0 , 1 } a ( n ) → { 0 , 1 } b ( n )
Definition 6 (Search problem in an oracle model). A search problem in the oracle-model of Γ a ( n ) , b ( n ) \Gamma_{a(n),b(n)} Γ a ( n ) , b ( n ) R = { R n } n ≥ 1 \mathcal{R}=\{R_n\}_{n\ge1} R = { R n } n ≥ 1 R n ⊆ { 0 , 1 } n × Γ a ( n ) , b ( n ) × { 0 , 1 } s ( n ) R_n \subseteq\{0,1\}^n \times\Gamma_{a(n),b(n)} \times\{0,1\}^{s(n)} R n ⊆ { 0 , 1 } n × Γ a ( n ) , b ( n ) × { 0 , 1 } s ( n ) R \mathcal{R} R n n n x ∈ { 0 , 1 } n x \in\{0,1\}^n x ∈ { 0 , 1 } n γ n ∈ Γ a ( n ) , b ( n ) \gamma_n \in\Gamma_{a(n),b(n)} γ n ∈ Γ a ( n ) , b ( n ) y y y ( x , γ n , y ) ∈ R n (x,\gamma_n,y) \in R_n ( x , γ n , y ) ∈ R n
We say that an algorithm A A A R ( ⋅ ) \mathcal{R}^{(\cdot)} R ( ⋅ ) n n n γ n \gamma_n γ n a ( n ) a(n) a ( n ) b ( n ) b(n) b ( n )
Pr x ∼ { 0 , 1 } n , γ n ∼ Γ a ( n ) , b ( n ) [ A γ n ( x ) outputs y such that ( x , γ n , y ) ∈ R n ] ≥ 2 3 . \Pr_{\substack{x \sim\{0,1\}^n,\ \gamma_n \sim\Gamma_{a(n),b(n)}}}\left[A^{\gamma_n}(x)\text{ outputs }y\text{ such that }(x,\gamma_n,y)\in R_n\right] \ge\frac{2}{3}. x ∼ { 0 , 1 } n , γ n ∼ Γ a ( n ) , b ( n ) Pr [ A γ n ( x ) outputs y such that ( x , γ n , y ) ∈ R n ] ≥ 3 2 . We say that an oracle TFNP search problem R ( ⋅ ) \mathcal{R}^{(\cdot)} R ( ⋅ ) efficiently reducible to S ( ⋅ ) \mathcal{S}^{(\cdot)} S ( ⋅ ) f ( ⋅ ) , g ( ⋅ ) f^{(\cdot)},g^{(\cdot)} f ( ⋅ ) , g ( ⋅ ) poly ( n ) \operatorname{poly}(n) poly ( n )
Pr x ∼ { 0 , 1 } n , γ n ∼ Γ a ( n ) , b ( n ) [ ∀ y , ( f γ n ( 1 n , x ) , γ n , y ) ∈ S ( ⋅ ) ⟹ ( x , γ n , g γ n ( 1 n , x , y ) ) ∈ R ( ⋅ ) ] ≥ 2 3 . \Pr_{\substack{x \sim\{0,1\}^n,\ \gamma_n \sim\Gamma_{a(n),b(n)}}}\left[\forall y,\ (f^{\gamma_n}(1^n,x),\gamma_n,y)\in S^{(\cdot)} \Longrightarrow(x,\gamma_n,g^{\gamma_n}(1^n,x,y))\in R^{(\cdot)}\right] \ge\frac{2}{3}. x ∼ { 0 , 1 } n , γ n ∼ Γ a ( n ) , b ( n ) Pr [ ∀ y , ( f γ n ( 1 n , x ) , γ n , y ) ∈ S ( ⋅ ) ⟹ ( x , γ n , g γ n ( 1 n , x , y )) ∈ R ( ⋅ ) ] ≥ 3 2 . One may assume that a ( n ) a(n) a ( n ) b ( n ) b(n) b ( n ) s ( n ) s(n) s ( n ) circuit TFNP problems we mentioned in this paper, i.e., TFNP problems, where the input is the description of a circuit whose truth table encodes an object of exponential length, it is natural to define the corresponding oracle TFNP problem by letting the input be descriptions of oracle circuits . For example, the oracle search problem P W P P ( ⋅ ) \mathrm{PWPP}^{(\cdot)} PWPP ( ⋅ ) x x x C γ : { 0 , 1 } m → { 0 , 1 } m − 1 C^{\gamma}\colon\{0,1\}^{m} \to\{0,1\}^{m-1} C γ : { 0 , 1 } m → { 0 , 1 } m − 1 ( x , γ n , ( y 1 , y 2 ) ) ∈ PWPP ( ⋅ ) (x,\gamma_n,(y_1,y_2)) \in\operatorname{PWPP}^{(\cdot)} ( x , γ n , ( y 1 , y 2 )) ∈ PWPP ( ⋅ ) C γ n ( y 1 ) = C γ n ( y 2 ) C^{\gamma_n}(y_1) = C^{\gamma_n}(y_2) C γ n ( y 1 ) = C γ n ( y 2 ) y 1 ≠ y 2 y_1 \ne y_2 y 1 = y 2
Note that any of the circuit TFNP problems we considered in this paper is equivalent to another problem where the input oracle circuit is promised to be the canonical circuit C γ ( x ) : = γ ( x ) C^{\gamma}(x) := \gamma(x) C γ ( x ) := γ ( x ) uniform versions of average-case reductions between the corresponding black-box problems, where each node of the decision trees can be locally printed by a uniform algorithm in polylog ( N ) \operatorname{polylog}(N) polylog ( N )
