TFNP intersections through the lens of feasible disjunction

0582265 - MÚ 2025 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Hubáček, Pavel - Khaniki, Erfan - Thapen, Neil
TFNP intersections through the lens of feasible disjunction.
15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2024 - (Guruswami, V.), č. článku 63. Leibniz International Proceedings in Informatics (LIPIcs), 287. ISBN 978-3-95977-309-6.
[15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Berkeley (US), 30.01.2024-02.02.2024]
Grant CEP: GA ČR(CZ) GX19-27871X; GA ČR(CZ) GA23-04825S
Institucionální podpora: RVO:67985840
Klíčová slova: TFNP * feasible disjunction * proof complexity * TFNP intersection classes
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

The complexity class CLS was introduced by Daskalakis and Papadimitriou (SODA 2010) to capture the computational complexity of important TFNP problems solvable by local search over continuous domains and, thus, lying in both PLS and PPAD. It was later shown that, e.g., the problem of computing fixed points guaranteed by Banach’s fixed point theorem is CLS-complete by Daskalakis et al. (STOC 2018). Recently, Fearnley et al. (J. ACM 2023) disproved the plausible conjecture of Daskalakis and Papadimitriou that CLS is a proper subclass of PLS∩PPAD by proving that CLS = PLS∩PPAD. To study the possibility of other collapses in TFNP, we connect classes formed as the intersection of existing subclasses of TFNP with the phenomenon of feasible disjunction in propositional proof complexity, where a proof system has the feasible disjunction property if, whenever a disjunction F ∨ G has a small proof, and F and G have no variables in common, then either F or G has a small proof. Based on some known and some new results about feasible disjunction, we separate the classes formed by intersecting the classical subclasses PLS, PPA, PPAD, PPADS, PPP and CLS. We also give the first examples of proof systems which have the feasible interpolation property, but not the feasible disjunction property.
Trvalý link: https://hdl.handle.net/11104/0350365