The PCP-for-PPAD conjecture: a quasilinear reduction
There are fixed rational constants and , a fixed positive integer , a fixed nonnegative integer , a fixed polynomial with nonnegative integer coefficients, and deterministic polynomial-time algorithms such that: (i) every generalized circuit has an acceptable rational assignment of encoding length at most ; (ii) for every End-of-Line instance of length , is a generalized circuit of complete encoding length ; (iii) runs in time polynomial in ; and (iv) for every acceptable assignment of , returns a solution of in time polynomial in plus the encoding length of .
The proof is complete and acyclically orders all parameter choices (Sections 6.6 and 6.8), establishes totality via Brouwer's fixed-point theorem on a fixed rational mesh (Lemma 6.13), and proves soundness for arbitrary real assignments meeting the gate-failure budget.
“Theorem 1.3 (Quasilinear PCP for PPAD). There are fixed rational constants 0 < ε < 1/10 , 0 < δ < 1, a fixed positive integer A, a fixed nonnegative integer b, a fixed polynomial p with nonnegative integer coefficients, and deterministic algorithms R, D with the following properties.” · Show in paper