Korten and Pitassi (FOCS, 2024) defined a new complexity class $L_2P$ as the polynomial-time Turing closure of the Linear Ordering Principle. They put it between $MA$ (Merlin--Arthur protocols) and $S_2P$ (the second symmetric level of the polynomial hierarchy).

In this paper we sandwich $L_2P$ between $P^{prMA}$ and $P^{prSBP}$. (The oracles ... more >>>