Upper and Lower Bounds for the Linear Ordering Principle

The Linear Ordering Principle (LOP) is a total search problem that generalizes the task of finding the minimum element of a given order to settings in which the order need not be total. Building on this, Korten and Pitassi (FOCS 2024) introduced the complexity class $\L_2P$ as the polynomial-time Turing closure of LOP. They also showed that $\L_2P$ lies between $\MA$ (Merlin–Arthur protocols) and $\S_2P$ (the second symmetric level of the polynomial hierarchy).

In this work, we establish tighter upper and lower bounds for $\L_2P$ by sandwiching it between $\P^{\prMA}$ and $\P^{\prSBP}$. Here, the oracles are promise problems, and $\SBP$ is the only currently known natural complexity class that lies between $\MA$ and $\AM$. The containment $\L_2P \subseteq \P^{\prSBP}$ is obtained via an iterative procedure that uses a $\prSBP$ oracle to estimate the average order rank of a subset and to identify the minimum element of a linear order. This technique may be of independent interest.

These containment results yield several consequences: 

1) We answer affirmatively an open question posed by Chakaravarthy and Roy (Computational Complexity, 2011) on whether $\P^{\prMA} \subseteq \S_2P$, thereby settling the relative standing of previously existing Karp–Lipton–style collapse results. 

2) We resolve an open question of Korten and Pitassi whether a Karp–Lipton–style collapse can be established for $\L_2P$.

Based on a joint work with Edward Hirsch.