Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2602.16810 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917525857501184 |
|---|---|
| author | Fleming, Noah Gal, Anna Imrek, Deniz Marciot, Christophe |
| author_facet | Fleming, Noah Gal, Anna Imrek, Deniz Marciot, Christophe |
| contents | 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. [KKMP21] observed that many of the natural problems considered so far in the second level of the total function polynomial hierarchy (TF$Σ_2$) 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$Σ_2$ 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 [FIM25]. 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 $Σ_2$-variant of the Sherali-Adams proof system. To do so, we extend the classical pseudo-expectation method to the $Σ_2$ setting, showing that the existence of a $Σ_2$ pseudo-expectation precludes a $Σ_2$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16810 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Separations above TFNP from Sherali-Adams Lower Bounds Fleming, Noah Gal, Anna Imrek, Deniz Marciot, Christophe Computational Complexity 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. [KKMP21] observed that many of the natural problems considered so far in the second level of the total function polynomial hierarchy (TF$Σ_2$) 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$Σ_2$ 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 [FIM25]. 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 $Σ_2$-variant of the Sherali-Adams proof system. To do so, we extend the classical pseudo-expectation method to the $Σ_2$ setting, showing that the existence of a $Σ_2$ pseudo-expectation precludes a $Σ_2$ 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. |
| title | Separations above TFNP from Sherali-Adams Lower Bounds |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2602.16810 |