On the complexity of some restricted variants of \textsc{Quotient Pigeon} and a weak variant of \textsc{Kőnig}

DOI10.1016/J.IPL.2025.106574MaRDI QIDQ6970524zbMATH OpenFDO

Authors Takashi Ishizuka

Publication date 17 June 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2025.106574

zbMATH Keywords

Kőnig's lemmapigeonhole principlePPPTFNP

Mathematics Subject Classification ID

Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Cites work

• Consensus halving is PPA-complete
• Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP
• Further collapses in TFNP
• How easy is local search?
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Integer factoring and modular square roots
• On Search Complexity of Discrete Logarithm
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• PPP-completeness with connections to cryptography
• Settling the complexity of computing two-player Nash equilibria
• TFNP intersections through the Lens of feasible disjunction
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The complexity of the parity argument with potential
• The frontier of intractability for EFX with two agents

Cited in

(1)

• The \(\mathtt{PPP}\)-completeness of Ward-Szabó

This page was built for publication: On the complexity of some restricted variants of \textsc{Quotient Pigeon} and a weak variant of \textsc{Kőnig}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970524)