EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The PPP-completeness of Ward-Szabó

Takashi Ishizuka

Theoretical Computer Science · 2026-06 · 1076 · 115990

DOI: 10.1016/j.tcs.2026.115990 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-06. Verfasst von Takashi Ishizuka. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Society for the Promotion of Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Japan Society for the Promotion of Science

Zitieren

APA

Ishizuka, T. (2026). The PPP-completeness of Ward-Szabó. Theoretical Computer Science, 1076, 115990. https://doi.org/10.1016/j.tcs.2026.115990

Vancouver

Ishizuka T. The PPP-completeness of Ward-Szabó. Theoretical Computer Science. 2026;1076:115990. doi:10.1016/j.tcs.2026.115990

BibTeX
@article{Ishizuka2026,
  author = {Ishizuka, Takashi},
  title = {The PPP-completeness of Ward-Szabó},
  journal = {Theoretical Computer Science},
  year = {2026},
  volume = {1076},
  pages = {115990},
  doi = {10.1016/j.tcs.2026.115990}
}
Kostenlos starten →