On the complexity of some restricted variants of Quotient Pigeon and a weak variant of Kőnig
Takashi Ishizuka · Information Processing Letters · 2025
One of the most famous TFNP subclasses is PPP , which is the set of all search problems whose totality is guaranteed by the pigeonhole principle. The author's recent preprint [1] has introduced a TFNP problem related to the pigeonhole principle over a quotient set, called Quotient Pigeon , and shown that the problem Quotient Pigeon is not only PPP -hard but also PLS -hard. In this paper, we formulate other computational problems related to the pigeonhole principle over a quotient set via an explicit representation of the equivalence classes. Our new formulation introduces a non-trivial PPP ∩ PPA k -complete problem for every k ≥ 2 . Furthermore, we consider the computational complexity of a computational problem related to Kőnig's lemma, which is a weaker variant of the problem formulated by Pasarkar et al. [2] . We show that our weaker variant is PPAD -hard and is in PPP ∩ PPA . • We have investigated the computational aspects of the pi- geonhole principle over a quotient set. • We have introduced the first PPP ∩ PPA k -complete problem for a positive integer k ≥ 2 . • Consider the computational complexity of a weak variant of a problem related to Kőnig lemma.