2026-07-23T17:39:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27079 2026-07-23T11:36:19Z ddc:004 open_access

Separations Above TFNP from Sherali-Adams Lower Bounds Fleming, Noah Gál, Anna Imrek, Deniz Marciot, Christophe TFNP Range Avoidance Linear Ordering Principle Separation Sherali-Adams Pseudo-Expectation Unlike in TFNP, for which there is an abundance of problems capturing natural existence principles which are incomparable (in the black-box setting), Kleinberg et al. [Robert Kleinberg et al., 2021] observed that many of the natural problems considered so far in the second level of the total function polynomial hierarchy (TFΣ₂) reduce to the Strong Avoid problem. In this work, we prove that the Linear Ordering Principle does not reduce to Strong Avoid in the black-box setting, exhibiting the first TFΣ₂ problem that lies outside of the class of problems reducible to Strong Avoid. The proof of our separation exploits a connection between total search problems in the polynomial hierarchy and proof complexity, recently developed by Fleming, Imrek, and Marciot [Fleming et al., 2025]. In particular, this implies that to show our separation, it suffices to show that there is no small proof of the Linear Ordering Principle in a Σ₂-variant of the Sherali-Adams proof system. To do so, we extend the classical pseudo-expectation method to the Σ₂ setting, showing that the existence of a Σ₂ pseudo-expectation precludes a Σ₂ Sherali-Adams proof. The main technical challenge is in proving the existence of such a pseudo-expectation, we manage to do so by solving a combinatorial covering problem about permutations. We also show that the extended pseudo-expectation bound implies that the Linear Ordering Principle cannot be reduced to any problem admitting a low-degree Sherali-Adams refutation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah Fleming and Anna Gál and Deniz Imrek and Christophe Marciot 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.37 urn:nbn:de:0030-drops-270797 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.37 eng https://creativecommons.org/licenses/by/4.0/legalcode