Upper and Lower Bounds for the Linear Ordering Principle
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914430533500928 |
|---|---|
| author | Hirsch, Edward A. Volkovich, Ilya |
| author_facet | Hirsch, Edward A. Volkovich, Ilya |
| contents | Korten and Pitassi (FOCS, 2024) defined a new complexity class $L_2^P$ as the polynomial-time Turing closure of the Linear Ordering Principle. They put it between $MA$ (Merlin--Arthur protocols) and $S_2^P$ (the second symmetric level of the polynomial hierarchy).
In this paper we sandwich $L_2^P$ between $P^{prMA}$ and $P^{prSBP}$. (The oracles here are promise problems, and $SBP$ is the only known class between $MA$ and $AM$.) The containment in $P^{prSBP}$ is proved via an iterative process that uses a $prSBP$ oracle to estimate the average order rank of a subset and find the minimum of a linear order.
Another containment result of this paper is $P^{prO_2^P} \subseteq O_2^P$ (where $O_2^P$ is the input-oblivious version of $S_2^P$). These containment results altogether have several byproducts:
We give an affirmative answer to an open question posed by of Chakaravarthy and Roy (Computational Complexity, 2011) whether $P^{prMA} \subseteq S_2^P$, thereby settling the relative standing of the existing (non-oblivious) Karp-Lipton-style collapse results of Chakaravarthy and Roy (2011) and Cai (2007),
We give an affirmative answer to an open question of Korten and Pitassi whether a Karp-Lipton-style collapse can be proven for $L_2^P$,
We show that the Karp-Lipton-style collapse to $P^{prOMA}$ is actually better than both known collapses to $P^{prMA}$ due to Chakaravarthy and Roy (Computational Complexity, 2011) and to $O_2^P$ also due to Chakaravarthy and Roy (STACS, 2006). Thus we resolve the controversy between previously incomparable Karp-Lipton collapses stemming from these two lines of research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19188 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Upper and Lower Bounds for the Linear Ordering Principle Hirsch, Edward A. Volkovich, Ilya Computational Complexity 68Q15 F.1.3 Korten and Pitassi (FOCS, 2024) defined a new complexity class $L_2^P$ as the polynomial-time Turing closure of the Linear Ordering Principle. They put it between $MA$ (Merlin--Arthur protocols) and $S_2^P$ (the second symmetric level of the polynomial hierarchy). In this paper we sandwich $L_2^P$ between $P^{prMA}$ and $P^{prSBP}$. (The oracles here are promise problems, and $SBP$ is the only known class between $MA$ and $AM$.) The containment in $P^{prSBP}$ is proved via an iterative process that uses a $prSBP$ oracle to estimate the average order rank of a subset and find the minimum of a linear order. Another containment result of this paper is $P^{prO_2^P} \subseteq O_2^P$ (where $O_2^P$ is the input-oblivious version of $S_2^P$). These containment results altogether have several byproducts: We give an affirmative answer to an open question posed by of Chakaravarthy and Roy (Computational Complexity, 2011) whether $P^{prMA} \subseteq S_2^P$, thereby settling the relative standing of the existing (non-oblivious) Karp-Lipton-style collapse results of Chakaravarthy and Roy (2011) and Cai (2007), We give an affirmative answer to an open question of Korten and Pitassi whether a Karp-Lipton-style collapse can be proven for $L_2^P$, We show that the Karp-Lipton-style collapse to $P^{prOMA}$ is actually better than both known collapses to $P^{prMA}$ due to Chakaravarthy and Roy (Computational Complexity, 2011) and to $O_2^P$ also due to Chakaravarthy and Roy (STACS, 2006). Thus we resolve the controversy between previously incomparable Karp-Lipton collapses stemming from these two lines of research. |
| title | Upper and Lower Bounds for the Linear Ordering Principle |
| topic | Computational Complexity 68Q15 F.1.3 |
| url | https://arxiv.org/abs/2503.19188 |