Computer Science/Discrete Mathematics Seminar I

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.