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 M. Chiari and J. Krajíček, 1998 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ᵖrMA and PᵖrSBP. (The oracles here are promise problems, and SBP is the only known class between MA and AM. ) The containment in PᵖrSBP 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ᵖrO₂P ⊆ 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ᵖrMA ⊆ S₂P, thereby settling the relative standing of the existing (non-oblivious) Karp–Lipton–style collapse results of V. T. Chakaravarthy and S. Roy, 2011 and J. -Y. Cai, 2007, - 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ᵖrOMA is actually better than both known collapses to PᵖrMA 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.
Hirsch et al. (Thu,) studied this question.