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 L2P as the polynomial-time Turing closure of LOP. They also showed that L2P  lies between MA (Merlin–Arthur protocols) and S2P (the second symmetric level of the polynomial hierarchy).

In this work, we establish tighter upper and lower bounds for L2P by sandwiching it between PprMA and PprSBP. Here, the oracles are promise problems, and SBP is the only currently known natural complexity class that lies between MA and AM. The containment L2P⊆PprSBP 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:

We answer affirmatively an open question posed by Chakaravarthy and Roy (Computational Complexity, 2011) on whether PprMA⊆S2P, thereby settling the relative standing of previously existing Karp–Lipton–style collapse results.

We resolve an open question of Korten and Pitassi whether a Karp–Lipton–style collapse can be established for L2P.