PPP (complexity)¶
The class of total polynomially verifiable search problems reducible by efficient witness-preserving maps to the zero-preimage-or-collision PIGEONHOLE CIRCUIT problem.
Core Idea¶
PPP is a class of total search problems, not a single problem or a counting theorem. A member has short, efficiently checkable answers for every input and reduces efficiently to PIGEONHOLE CIRCUIT: an instance becomes a circuit, and every permitted circuit answer can be decoded into a valid answer to the original problem. That witness-preserving reduction establishes membership; a reduction in the reverse direction is additionally needed to call a member PPP-complete.[ref-65bdeb0fbe0e][ref-0f8f65b2a84b]
Scope of Application¶
PPP belongs to computational complexity theory. Its reference task receives an \(n\)-input, \(n\)-output Boolean circuit. It asks for an input mapped to zero or two distinct inputs with the same output. If zero is absent, \(2^n\) inputs have only \(2^n-1\) nonzero outputs available, so a collision must occur. A member need not itself receive a circuit: the constrained cSIS problem receives modular matrices and a target vector, then reduces to the circuit task.[ref-65bdeb0fbe0e][ref-0f8f65b2a84b]
The cSIS result uses the authors' stated parameter bounds, binary-invertible matrix and specified vector-or-pair answers. It does not extend to unconstrained SIS or every lattice task. The published FOCS article states the completeness theorem and sketches its proof; the authors' full version gives the detailed reductions.[^ref-0f8f65b2a84b]
Clarity¶
Keep three levels apart: PPP is the class, PIGEONHOLE CIRCUIT is its defining complete member, and the finite pigeonhole principle explains one branch of that member's totality proof. A counting-flavored existence argument alone does not prove class membership. One must supply a polynomial-time circuit construction and a decoder that handles either permitted circuit answer.[^ref-65bdeb0fbe0e]
Papadimitriou listed Equal Sums as a PPP member while leaving its completeness open in 1994. That sentence is historical; it does not establish today's classification or any lower bound.[^ref-65bdeb0fbe0e]
Manages Complexity¶
Different search tasks can have unlike inputs and witnesses. PPP compares them through one fixed target and the same two-direction test. The member-to-circuit reduction establishes membership. A circuit-to-member reduction additionally establishes hardness; both directions together establish completeness. These distinctions let the cSIS theorem say more than mere membership without treating every PPP member as complete.[ref-65bdeb0fbe0e][ref-0f8f65b2a84b]
Abstract Reasoning¶
For a candidate search relation \(R(x,y)\), ask whether every valid input has a short checkable witness. Then seek polynomial-time maps \(f\) and \(g\): \(f(x)\) is a canonical circuit, and for every allowed circuit answer \(z\), \(R(x,g(x,z))\) holds. A map that decodes only convenient zero preimages, but fails on collisions, is insufficient.[^ref-0f8f65b2a84b]
For the identity circuit \(C(x)=x\), zero has a preimage and no collision occurs. Its equal-size domain and codomain never instantiate the live Pigeonhole Principle's larger-to-smaller mapping signature. That principle is therefore a conditional proof neighbor, not an asserted strict DAG parent.
Knowledge Transfer¶
The reduction contract transfers within total-search complexity from explicit circuits to the unlike arithmetic representation of cSIS. It does not transfer a claim that cSIS's matrices are themselves circuits, that PPP membership supplies an efficient solver, or that a similar class-by-reference-task pattern is already a substrate-independent Prime.[^ref-0f8f65b2a84b]
The current entry is a subclass of live FNP (complexity): each PPP member has polynomially bounded, polynomial-time verifiable witnesses, while PPP additionally requires totality and the fixed-target search reduction. Live Complexity Class has a different decision-acceptance and bounded-solver-resource signature. The canonical circuit, not the class, is an individual Search Problem.
Example¶
Canonical PIGEONHOLE CIRCUIT. Its four roles are: (1) total checkable search relation = zero preimage or distinct collision for every circuit; (2) fixed target = this very task; (3) target totality = zero is reached or the nonzero outputs force a collision; (4) reduction = identity instance map and witness decoder. Completeness follows from its position as the defining target.[^ref-65bdeb0fbe0e]
Constrained Short Integer Solution. Its four roles are: (1) total checkable relation = the paper's constrained binary-vector or distinct-pair answer under its formal modular parameters; (2) fixed target = PIGEONHOLE CIRCUIT, although the cSIS input is arithmetic data; (3) target totality = the zero-or-collision guarantee carried back through the reduction; (4) reduction = the full paper's efficient circuit construction and decoder. A separate reverse reduction proves this constrained task PPP-complete.[^ref-0f8f65b2a84b]
Relationships to Other Abstractions¶
Current abstraction PPP (complexity) Domain-specific
Parents (1) — more general patterns this builds on
-
PPP (complexity) is a kind of FNP (complexity) Domain-specific
PPP is the total reduction-defined subclass of FNP whose members reduce to PIGEONHOLE CIRCUIT.
Hierarchy path (1) — routes to 1 parentless root
- PPP (complexity) → FNP (complexity) → Verification → Evaluation → Comparison → Self Checking
Neighborhood in Abstraction Space¶
PPP (complexity) sits in a sparse region of the domain-specific corpus (84th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Computational Complexity & Hardness (17 abstractions)
Nearest neighbors
- QMA — 0.82
- Equicontinuity — 0.81
- Bloom Filter — 0.81
- P versus NP Problem — 0.81
- Maharam Algebra — 0.81
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Pigeonhole Principle: a conditional counting step in the canonical proof, not the computational class.[^ref-65bdeb0fbe0e]
- PPP-complete: requires reverse hardness as well as membership.[^ref-0f8f65b2a84b]
- PWPP or PPAD: related classes; the cited sources support non-strict containments, not separations.[ref-65bdeb0fbe0e][ref-0f8f65b2a84b]
- Equal Sums' present status: the cited completeness-open statement describes 1994 only.[^ref-65bdeb0fbe0e]
References¶
[^ref-65bdeb0fbe0e]: Christos H. Papadimitriou, “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence”, Journal of Computer and System Sciences 48, 498–532 (1994), especially §2, printed pp. 504–506/PDF pp. 6–8 and §5, printed pp. 528–530/PDF pp. 30–32. Full original-paper reprint inspected; the Equal Sums and algorithm remarks are time-indexed.
[^ref-0f8f65b2a84b]: Katerina Sotiraki, Manolis Zampetakis and Giorgos Zirdelis, “PPP-Completeness with Connections to Cryptography”, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, pp. 148–158, doi:10.1109/FOCS.2018.00023, especially printed pp. 151–153, §II and Theorem II.6. Full official proceedings article inspected; it states the result and gives proof overviews. The authors' full original preprint v1, §§2.1 and 4, supplies the detailed Karp reductions and Lemmas 4.4–4.5 under the paper's cSIS parameter conditions.