Search Results

Documents authored by Davis, Ben

Colourful TFNP and Propositional Proofs

Authors: Ben Davis and Robert Robere

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Recent work has shown that many of the standard TFNP classes - such as PLS, PPADS, PPAD, SOPL, and EOPL - have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem can be efficiently proved by the corresponding proof system. We build on this line of work by studying coloured variants of these TFNP classes: C-PLS, C-PPADS, C-PPAD, C-SOPL, and C-EOPL. While C-PLS has been studied in the literature before, the coloured variants of the other classes are introduced here for the first time. We give a family of results showing that these coloured TFNP classes are natural objects of study, and that the correspondence between TFNP and natural propositional proof systems is not an exceptional phenomenon isolated to weak TFNP classes. Namely, we show that: - Each of the classes C-PLS, C-PPADS, and C-SOPL have corresponding proof systems characterizing them. Specifically, the proof systems for these classes are obtained by adding depth to the formulas in the corresponding proof system for the uncoloured class. For instance, while it was previously known that PLS is characterized by bounded-width Resolution (i.e. depth 0.5 Frege), we prove that C-PLS is characterized by depth-1.5 Frege (Res(polylog(n)). - The classes C-PPAD and C-EOPL coincide exactly with the uncoloured classes PPADS and SOPL, respectively. Thus, both of these classes also have corresponding proof systems: unary Sherali-Adams and Reversible Resolution, respectively. - Finally, we prove a coloured intersection theorem for the coloured sink classes, showing C-PLS ∩ C-PPADS = C-SOPL, generalizing the intersection theorem PLS ∩ PPADS = SOPL. However, while it is known in the uncoloured world that PLS ∩ PPAD = EOPL = CLS, we prove that this equality fails in the coloured world in the black-box setting. More precisely, we show that there is an oracle O such that C-PLS^O ∩ C-PPAD^O ⊋ C-EOPL^O. To prove our results, we introduce an abstract multivalued proof system - the Blockwise Calculus - which may be of independent interest.

Cite as

Ben Davis and Robert Robere. Colourful TFNP and Propositional Proofs. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

  author =	{Davis, Ben and Robere, Robert},
  title =	{{Colourful TFNP and Propositional Proofs}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{36:1--36:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-183066},
  doi =		{10.4230/LIPIcs.CCC.2023.36},
  annote =	{Keywords: oracle separations, TFNP, proof complexity, Res(k), lower bounds}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail