pith. sign in

arxiv: 2507.23345 · v2 · submitted 2025-07-31 · 💻 cs.CC · cs.DM

The PPP-completeness of the Ward-Szabo theorem

Takashi Ishizuka This is my paper

Pith reviewed 2026-05-19 02:58 UTC · model grok-4.3

classification 💻 cs.CC cs.DM
keywords PPPWard-Szabóbichromatic triangleTFNPtotal search problemspigeonhole principlegraph edge coloringcomputational complexity
0
0 comments X

The pith

The Ward-Szabó search problem of finding a bichromatic triangle is complete for the complexity class PPP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the total search problem Ward-Szabó is PPP-complete. Ward-Szabó takes as input an edge coloring of the complete graph on N squared vertices that uses at most N colors and at least two colors, and requires outputting a triangle whose two edges receive different colors. The result improves the prior classification of the problem as PWPP-hard and inside TFNP by showing both membership in PPP via the pigeonhole principle and hardness for PPP via reduction. This pins down the precise location of the problem among total search problems whose existence guarantees come from the pigeonhole principle.

Core claim

Ward and Szabó proved that any edge coloring of the complete graph on N squared vertices using N colors and at least two colors must contain a bichromatic triangle. The associated search problem of locating one such triangle is therefore total. The paper proves that this search problem is complete for PPP, the TFNP subclass of total search problems whose totality is guaranteed by the pigeonhole principle.

What carries the argument

Polynomial-time reduction from a canonical PPP-complete problem to Ward-Szabó that preserves totality and efficient verifiability of solutions.

If this is right

  • Any problem in PPP reduces in polynomial time to Ward-Szabó.
  • Ward-Szabó can serve as a canonical hard problem for proving PPP-hardness of other total search problems.
  • The bichromatic triangle search problem inherits the same totality guarantee from the pigeonhole principle that defines PPP.
  • If a polynomial-time algorithm existed for Ward-Szabó then every problem in PPP would be solvable in polynomial time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar combinatorial statements resting on the pigeonhole principle may yield additional PPP-complete search problems when turned into total search tasks.
  • Resolving whether PPP equals PPA or other TFNP subclasses would immediately classify the computational status of finding bichromatic triangles.
  • Heuristic methods developed for Ward-Szabó instances could be tested for transfer to other PPP problems such as collision finding.

Load-bearing premise

A polynomial-time reduction from a known PPP-complete problem to Ward-Szabó exists while preserving the guarantee that a solution must exist.

What would settle it

An explicit coloring of the complete graph on N squared vertices using at most N colors and at least two colors that contains no bichromatic triangle, which would violate both the original combinatorial statement and membership of the search problem in PPP.

read the original abstract

Ward and Szab\'o [WS94] have shown that a complete graph with $N^2$ nodes whose edges are colored by $N$ colors and that has at least two colors contains a bichromatic triangle. This fact leads us to a total search problem: Given an edge-coloring on a complete graph with $N^2$ nodes using at least two colors and at most $N$ colors, find a bichromatic triangle. Bourneuf, Folwarczn\'y, Hub\'acek, Rosen, and Schwartzbach [Bou+23] have proven that such a total search problem, called Ward-Szab\'o, is PWPP-hard and belongs to the class TFNP, a class for total search problems in which the correctness of every candidate solution is efficiently verifiable. However, it is open which TFNP subclass contains Ward-Szab\'o. This paper will improve the computational complexity of Ward-Szab\'o. We prove that Ward-Szab\'o is a complete problem for the complexity class PPP, a TFNP subclass of problems in which the existence of solutions is guaranteed by the pigeonhole principle.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript claims to prove that the Ward-Szabó total search problem is PPP-complete. The problem takes as input an edge-coloring of the complete graph on N² vertices using at most N colors and at least two colors, and requires outputting a bichromatic triangle; the authors establish both membership in PPP (via a pigeonhole argument) and PPP-hardness, improving on the prior PWPP-hardness and TFNP membership shown in [Bou+23].

Significance. If the central claim holds, the result supplies a natural, combinatorially motivated complete problem for PPP, which may aid in classifying other TFNP problems and clarifying relationships among TFNP subclasses. The explicit connection to the pigeonhole principle is a strength, as is the improvement from PWPP-hardness to full PPP-completeness.

major comments (1)
  1. [§3] §3 (Membership in PPP): the argument places Ward-Szabó in PPP by invoking the existential pigeonhole principle on the N² vertices and N colors to guarantee a bichromatic triangle, but does not exhibit an explicit polynomial-time reduction from the Ward-Szabó search problem to a canonical PPP-complete problem such as COLLISION. Without a constructive reduction that maps solutions back in polynomial time, the argument establishes totality (hence TFNP membership) but does not establish membership in the subclass PPP.
minor comments (1)
  1. [Abstract] The abstract and introduction could more clearly distinguish the new PPP-completeness result from the prior PWPP-hardness of [Bou+23] to highlight the precise technical advance.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on our manuscript. We address the major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (Membership in PPP): the argument places Ward-Szabó in PPP by invoking the existential pigeonhole principle on the N² vertices and N colors to guarantee a bichromatic triangle, but does not exhibit an explicit polynomial-time reduction from the Ward-Szabó search problem to a canonical PPP-complete problem such as COLLISION. Without a constructive reduction that maps solutions back in polynomial time, the argument establishes totality (hence TFNP membership) but does not establish membership in the subclass PPP.

    Authors: We agree with the referee that an explicit reduction is required to rigorously establish membership in PPP rather than merely TFNP. In the revised manuscript we will add a detailed polynomial-time reduction from the Ward-Szabó search problem to COLLISION. The reduction will map a valid edge-coloring instance to a function whose domain and range sizes are polynomial in the input size, and will show how any collision can be converted back into a bichromatic triangle in polynomial time, thereby placing Ward-Szabó in PPP. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained against external benchmarks

full rationale

The paper establishes PPP-completeness by citing the Ward-Szabó existence theorem from WS94 for totality and the PWPP-hardness result from Bou+23 for the hardness direction. Membership in PPP is grounded in the standard pigeonhole principle applied directly to the input parameters (N² vertices, N colors, at least two colors used), which matches the class definition without requiring a fitted parameter or self-referential construction. No equations or steps reduce by construction to prior outputs of the same paper; the cited results are from distinct prior works and the pigeonhole argument is externally falsifiable via the class definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of PPP via the pigeonhole principle and the totality of the search problem; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Pigeonhole principle guarantees a solution exists for problems in PPP
    Invoked to place Ward-Szabó in PPP and to define the class itself.

pith-pipeline@v0.9.0 · 5728 in / 1137 out tokens · 38651 ms · 2026-05-19T02:58:58.302953+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    PPP-Completeness and Extremal Combinatorics

    LIPIcs. 2025, 14:1–14:22.doi: 10.4230/LIPICS.ITCS.2025.14. [Bou+23] Romain Bourneuf, Lukávs Folwarczný, Pavel Hubácek, Alon Rosen, and Nikolaj I. Schwartzbach. “PPP-Completeness and Extremal Combinatorics.” In:14th Inno- vations in Theoretical Computer Science Conference. Vol

    work page doi:10.4230/lipics.itcs.2025.14 2025

  2. [2]

    Black-Box PPP Is Not Turing-Closed

    LIPIcs. 2023, 22:1– 22:20. doi: 10.4230/LIPICS.ITCS.2023.22. [Fle+24] Noah Fleming, Stefan Grosser, Toniann Pitassi, and Robert Robere. “Black-Box PPP Is Not Turing-Closed.” In:Proceedings of the 56th Annual ACM Symposium on Theory of Computing. ACM, 2024, pp. 1405–1414.doi: 10 . 1145 / 3618260 . 3649769. [Ghe25] Surendra Ghentiyala. Private Communication

    work page doi:10.4230/lipics.itcs.2023.22 2023

  3. [3]

    The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard

    [HG18] Alexandros Hollender and Paul W. Goldberg. “The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard.” In: Electronic Colloquium on Computational ComplexityTR18-120 (2018). url: https://eccc.weizmann.ac.il/report/2018/120. [HV21] Pavel Hubácek and Jan Václavek. “On Search Complexity of Discrete Logari...

    work page 2018

  4. [4]

    On the complexity of some restricted variants of Quotient Pi- geon and a weak variant of Kőnig

    LIPIcs. 2021, 60:1–60:16.doi: 10.4230/LIPICS.MFCS.2021.60. [Ish25] Takashi Ishizuka. “On the complexity of some restricted variants of Quotient Pi- geon and a weak variant of Kőnig.” In:Information Processing Letters190 (2025), p. 106574. doi: https://doi.org/10.1016/j.ipl.2025.106574. [Jai+24] Siddhartha Jain, Jiawei Li, Robert Robere, and Zhiyang Xun. “...

    work page doi:10.4230/lipics.mfcs.2021.60 2021

  5. [5]

    Total NP Search Problems with Abundant Solutions

    doi: https://doi.org/10.1007/978-3-642-17364-6. [Li24] Jiawei Li. “Total NP Search Problems with Abundant Solutions.” In:15th Inno- vations in Theoretical Computer Science Conference. Vol

    work page doi:10.1007/978-3-642-17364-6

  6. [6]

    On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

    LIPIcs. 2024, 75:1– 75:23. doi: 10.4230/LIPICS.ITCS.2024.75. [Pap94] Christos H. Papadimitriou. “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence.” In:Journal of Computer and System Sciences48.3 (1994), pp. 498–532.doi: 10.1016/S0022-0000(05)80063-7. 16 [PPY23] Amol Pasarkar, Christos H. Papadimitriou, and Mihalis Yannaka...

    work page doi:10.4230/lipics.itcs.2024.75 2024

  7. [7]

    PPP-Completeness with Connections to Cryptography

    LIPIcs. 2023, 88:1–88:20.doi: 10.4230/LIPICS.ITCS.2023.88. [SZZ18] Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. “PPP-Completeness with Connections to Cryptography.” In:59th IEEE Annual Symposium on Foun- dations of Computer Science. IEEE Computer Society, 2018, pp. 148–158.doi: 10.1109/FOCS.2018.00023. [WS94] C Ward and S Szabó. “On swell ...

    work page doi:10.4230/lipics.itcs.2023.88 2023