Upper and Lower Bounds for the Linear Ordering Principle

Korten and Pitassi (FOCS, 2024) defined a new¹ complexity class L^P₂ as the polynomial-time Turing closure of the Linear Ordering Principle (a total function extending finding the minimum of an order [18] to the case where the order is not linear). They put it between MA (Merlin-Arthur protocols) and S^P₂ (the second symmetric level of the polynomial hierarchy). In this paper we sandwich L^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^prOP2 ⊆ O^P₂ (where O^P₂ is the input-oblivious version of S^P₂). These containment results altogether have several byproducts: We give an affirmative answer to an open question posed by Chakaravarthy and Roy (Computational Complexity, 2011) whether P^prMA ⊆ S^P₂, thereby settling the relative standing of the existing (non-oblivious) Karp-Lipton-style collapse results of [15] and [12], We give an affirmative answer to an open question of Korten and Pitassi whether a Karp-Lipton-style collapse can be proven for L^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^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.