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.

Version

v1 · 2026-10-07 · History

Domain-specific #

13985

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Computational Complexity Theory, Total Search Problems → Computer Science & Software Engineering

Aliases

Polynomial Pigeonhole Principle class

Core Idea

PPP, the Polynomial Pigeonhole Principle class, groups total search problems by a precise computational criterion: a problem belongs when every instance can be transformed in polynomial time into an instance of PIGEONHOLE CIRCUIT, and any permitted answer to that circuit can be transformed in polynomial time back into a valid answer to the original problem. The member problem has polynomially bounded, efficiently checkable witnesses for every input. Membership is about this witness-preserving reduction, not simply about having a counting argument for existence.^[1][2]

The canonical circuit task takes a Boolean circuit \(C:\{0,1\}^{n}\to\{0,1\}^{n}\) and accepts either an input \(x\) with \(C(x)=0^{n}\) or distinct inputs \(x,y\) with \(C(x)=C(y)\). One of these must exist: if zero is absent from the image, all \(2^{n}\) inputs map into only \(2^{n}-1\) nonzero outputs, so two collide. Papadimitriou introduced this defining complete problem; Sotiraki and colleagues use the equivalent modern Karp-reduction formulation and prove that constrained Short Integer Solution (cSIS), a structured arithmetic task without a circuit in its input, is also PPP-complete.^[1][2]

Structural Signature

Sig role-phrases:

• Total polynomial search relation. Each member has a polynomially bounded, polynomial-time checkable answer for every valid input. A partial witness task is not a PPP member under this definition.
• Fixed canonical target. PIGEONHOLE CIRCUIT specifies equal-length Boolean input and output strings and permits either a zero preimage or a distinct equal-output pair.
• Canonical totality. For each circuit, zero is reached or the nonzero outputs are fewer than the inputs, forcing a collision. This is a guarantee about the target task, not a claim that every circuit itself exhibits a collision.
• Polynomial-time search reduction. An efficient instance map produces a canonical circuit, and an efficient decoder converts every valid zero-preimage or collision response to an answer for the member problem.^[1][2]

A reverse reduction from PIGEONHOLE CIRCUIT into a member is an additional condition for PPP-completeness. It is not required for mere membership. The canonical task is complete by definition; the cSIS paper proves both membership and reverse hardness under its stated input restrictions.^[2]

What It Is Not

PPP is not the finite pigeonhole principle itself. That counting theorem is used in the no-zero branch of the canonical totality proof, while PPP is a class of computational search relations and reductions. PPP is also not just PIGEONHOLE CIRCUIT: that task is one complete member and common target, and cSIS has unlike arithmetic input. A problem with an informal pigeonhole-flavored existence proof is not thereby shown to belong; the polynomial-time instance map and decoder must be given.^[1][2]

Nor does PPP membership establish that a member is complete, that a polynomial-time finder exists, or that no such finder could exist. Papadimitriou's 1994 Equal Sums example was placed in PPP while its completeness was left open at that time. It is a historical illustration of the membership/completeness distinction, not an assertion about its present classification.^[1]

Scope of Application

The literal scope is theoretical computer science: total search tasks whose proposed answers are efficiently checkable, represented so that search reductions can be computed and decoded. Papadimitriou's canonical circuit has an explicit succinct Boolean representation. Sotiraki and colleagues' constrained lattice-congruence problem takes matrices and a target vector; its membership proof constructs a circuit reduction from that representation. The shared role is the reduction, not a requirement that every member arrive as a circuit.^[1][2]

The cSIS result applies to the authors' constrained modular parameter regime and specified one-vector-or-pair output relation. The published FOCS 2018 paper states Theorem II.6 and sketches both directions; its authors' full version gives the detailed membership and hardness lemmas. This does not make unconstrained SIS or every lattice search task PPP-complete.^[2]

Clarity

The class, its defining task, and its proof principle occupy different levels. Class: all eligible total search problems reducible to the target. Defining task: zero-preimage or collision for a length-preserving circuit. Proof principle: if the zero output is unavailable, the remaining codomain is one smaller than the domain. Confusing these levels converts a theorem into a class label or treats a single complete problem as the whole class.^[1]

Reduction direction matters. Reducing cSIS to PIGEONHOLE CIRCUIT proves cSIS is in PPP, because a canonical answer can be decoded into a cSIS answer. Reducing PIGEONHOLE CIRCUIT to cSIS proves cSIS is PPP-hard. The two directions together establish completeness. A one-way reduction alone does not support both claims.^[2]

Manages Complexity

Many total search tasks have different-looking witnesses. Rather than seek a separate existence algorithm or hardness theory for each, PPP supplies one reference problem and one transport rule. An author proves that an arbitrary answer to the reference circuit can be translated back to the original task; the class then records a bounded relationship among those tasks. This compresses varied search descriptions into a common reduction language without erasing the member's own input and witness types.^[1][2]

The cSIS result illustrates the gain. Its modular matrices do not look like the explicit Boolean circuit in the canonical task. The published theorem and full proof nevertheless establish both the forward search reduction and reverse hardness reduction. That comparison conveys a precise completeness result while keeping the algebraic constraints and output forms in cSIS itself.^[2]

Abstract Reasoning

Let \(R(x,y)\) be an efficiently checkable total search relation. To test PPP membership, construct a polynomial-time map \(f\) from each input \(x\) to a length-preserving circuit. Then construct a polynomial-time decoder \(g\) such that for every valid canonical output \(z\) of \(f(x)\), \(R(x,g(x,z))\) holds. The universal word “every” prevents a reduction from choosing only a convenient zero-preimage while failing to decode a collision, or vice versa.^[1][2]

A counterfactual separates class identity from a proof branch. For the identity circuit \(C(x)=x\), zero has a preimage and no two distinct inputs collide. The canonical disjunction is still total, but this particular circuit does not map more inputs into fewer available output slots. Only if zero is absent does the nonzero-output restriction trigger the live finite Pigeonhole Principle's excess-to-fewer-slots signature. Thus the principle is a useful conditional proof neighbor, not an all-instance typed parent of the class.

Knowledge Transfer

The reduction test transfers between unlike computational representations. For an explicit Boolean circuit, the membership map and decoder can be identities. For cSIS, the input is algebraic data and the reduction builds a circuit whose allowed outputs decode into a constrained vector or vector pair. What transfers is the complete search-reduction contract, not the surface notation of bits versus modular matrices.^[1][2]

The phrase “class defined by a reference problem and structure-preserving transformations” could suggest a broader formal pattern. These sources demonstrate it in computational search complexity only. A claim that a similar mechanism is a substrate-independent Prime would require independent noncomputational cases with the same full role structure; the current PPP entry remains domain-specific.

Examples

Canonical PIGEONHOLE CIRCUIT

Papadimitriou's task receives a Boolean circuit with \(n\) input bits and \(n\) output bits. It accepts a zero preimage or a distinct collision pair. Candidate answers are short and checkable. The zero-or-collision proof guarantees an answer for every circuit, and the identity map of the task to itself satisfies the reduction criterion. As the defining task, it is complete by construction.^[1]

Mapped back: total relation = checkable zero-preimage-or-collision witnesses for every circuit; canonical target = this same circuit task; totality = zero appears or nonzero codomain forces collision; reduction = identity instance map and witness decoder. Completeness is a further label about reverse reduction, automatic for this reference problem.

Constrained Short Integer Solution

Sotiraki and colleagues define cSIS using modular matrix \(A\), binary-invertible matrix \(G\), target \(b\), and parameter bounds. A permitted answer is either a binary vector satisfying specified congruences or a distinct binary-vector pair satisfying their pair conditions. The full paper proves membership by mapping cSIS into PIGEONHOLE CIRCUIT and decoding either kind of returned witness; it separately proves canonical-to-cSIS hardness. The official FOCS paper states the resulting PPP-completeness theorem.^[2]

Mapped back: total relation = the paper's admissible vector-or-pair search with its parameters; canonical target = zero-preimage-or-collision circuit problem; totality = the canonical guarantee carried through the reduction; reduction = the full paper's efficient instance map and decoder. Its arithmetic input makes this unlike the explicit-circuit case. The reverse map proves completeness only for the defined constrained task.^[2]

Structural Tensions

The inspected sources do not show an all-instance opposition that a PPP member must balance. Totality versus difficulty is a distinction between guaranteed existence and an algorithmic question, not a universal tradeoff inside each instance. Membership versus completeness is a difference in reduction direction, not two pressures to be optimized. Cryptographic interpretations of some members are additional contexts, not an intrinsic conflict that defines the class.^[1][2]

Diagnostic: When a claim about PPP sounds stronger than the evidence, ask which direction of reduction was proved, whether every canonical answer decodes, and whether a historic open-status sentence is being mistaken for a present lower bound.

Structural–Framed Character

Vocabulary travel: “pigeonhole” recalls a general finite counting principle, while the PPP label selects a specific total-search reduction class. Institutional origin: no conference or software package confers membership; it follows from the formal relation and reduction. Human-practice dependence: researchers choose representations and exhibit reductions, but the validity of a specified reduction is mathematically checkable.^[1][2]

Evaluative weight: calling a task cryptographically useful or practically difficult is separate from its class membership. Import versus recognition: a proved reduction recognizes membership; merely importing the name because a solution “must exist by pigeonhole” does not. Its character: near the structural end of the structural–framed spectrum within theoretical computer science, because fixed witness and reduction conditions decide membership, while its literal formulation depends on computation models, polynomial time and a chosen canonical task. This is domain-specific formal structure, not a free-standing counting Prime.

Structural Core vs. Domain Accent

The core is a total, polynomially checkable search relation transported by efficient instance and witness maps to the fixed zero-preimage-or-collision circuit task. The bit-level circuit encoding is explicit in the defining member; modular matrices and congruences are accents of cSIS. Reverse hardness, one-way permutations and collision-resistant hashing are additional claims or uses rather than membership requirements.^[1][2]

A more generic class-by-reference-task-and-witness-preserving-transformations skeleton is a future-Prime question, not an approved parent. It would require unlike noncomputational positive cases and full live-signature tests. Subtracting polynomial verification, Boolean-circuit reference and Karp reductions from PPP leaves either the live finite Pigeonhole Principle or a thin classification metaphor, neither of which defines this named class.

Instantiates / Related Primes

This entry is a kind of FNP (complexity).

The proposed all-instance class-to-class DAG edge is PPP → FNP (complexity), with subsumption: every PPP member is a polynomially balanced, polynomial-time verifiable search relation, while FNP also permits partial relations and does not require PPP’s fixed circuit target or reduction. The independent current-catalog recheck must confirm this exact placement.^[1][2]

The live Pigeonhole Principle requires a larger finite set mapped into fewer slots, forcing a collision. Its exact structure appears only after assuming zero is not in a canonical circuit's image; the identity circuit \(C(x)=x\) is an admitted canonical case with a zero preimage and no collision. That all-instance counterexample defeats a strict child-to-parent presupposition or kind-of edge, even though the principle explains one proof branch.^[1]

Live Complexity Class is the closest name, but its current full signature requires a bounded solving resource and yes/no decision acceptance. PPP bounds verification and reduction work for total witness-production tasks; it does not grant an efficient solver or a yes/no acceptance test for each member. Search Problem and Computational Problem describe individual instance/solution relations, whereas PPP is a set of such relations. Classification names an assignment process, whereas the formal class exists independently of any particular act of assigning a new problem. These are topical neighbors, not additional full all-instance typed parents.

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 (84^th 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

• Finite pigeonhole theorem. It is a conditional totality-proof tool for the canonical problem, not this reduction-closed computational class.^[1]
• PIGEONHOLE CIRCUIT alone. It is one complete member and reference task; cSIS is a differently represented member.^[2]
• PPP-complete versus in PPP. Completeness additionally requires the canonical-to-member reduction.^[2]
• PWPP's shrinking-output COLLISION task. That task has a different output condition; the sources give a non-strict subclass relationship, not a separation theorem.^[2]
• PPAD. Papadimitriou proves PPAD is contained in PPP, without proving the inclusion strict.^[1]
• Equal Sums' current complexity status. The 1994 article is evidence for its historical PPP membership and then-open completeness question only.^[1]

References

[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s

[2] Katerina Sotiraki, Manolis Zampetakis and Giorgos Zirdelis, “PPP-Completeness with Connections to Cryptography”, 2018 IEEE 59^th 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u