Complexity Class of the Week: \(L_2^P\)

Back in the 90s when I was a young professor at the University of Chicago, we would have a Complexity Class of the Week where I would take some interesting complexity class, write down on a white board everything we knew about it with some open problems and students and faculty would muse over it. When I started the blog in 2002, I took the concept online. 

My first Complexity Class of the Week post covered the class \(S_2^P\). Recently Rahul Santhanam said to me "\(L_2^P\) is the new \(S_2^P\)". So for one week only, I'm bringing back the complexity class of the week to talk about \(L_2^P\), the set of problems reducible to the linear ordering principle. 

Recall the \(S_2^P\) courtroom: a polynomial-time judge, two lawyers submitting written arguments, one arguing the string is in the language, the other arguing it's out, and neither seeing the other's brief. For \(L_2^P\) we add one rule: the judge's rulings must be transitive. Each lawyer submits an argument that the judge can compare in polynomial time, where the judge in his mind ranks all the arguments in a linear order. The best argument wins.

The linear ordering principle states that any total linear order of a finite set has a unique minimum element. Oliver Korten and Toni Pitassi define the Linear Ordering Principle (LOP)  as a total search problem: given a circuit \(C(x,y)\) purporting to compute a linear ordering on \(\{0,1\}^n\), find either the minimum element or a witness that one of the order axioms fails (a violation of antisymmetry or transitivity). \(L_2^P\) is the class of languages polynomial-time Turing reducible to LOP. Korten and Pitassi show polynomial-time many-one, Turing and even \(\mathrm{P^{NP}}\) reductions to LOP all give the same class. Equivalently, \(L\in L_2^P\) if there is a polynomial-time relation \(R\) such that for every \(x\), \(R(x,\cdot,\cdot)\) defines a linear order on polynomially-long strings, and the minimum element begins with a 1 exactly when \(x\in L\). That last formulation makes clear that \(L_2^P\) is just \(S_2^P\) with a transitive referee, so \(L_2^P\subseteq S_2^P\).

Korten and Pitassi show \(\mathrm{P^{NP}}\subseteq L_2^P\subseteq S_2^P\) and \(\mathrm{MA}\subseteq L_2^P\). Edward Hirsch and Ilya Volkovich show  \(\mathrm{P^{prMA}}\subseteq L_2^P\), answering a 2011 question of Venkatesan Chakaravarthy and Sambuddha Roy on whether \(\mathrm{P^{prMA}}\subseteq S_2^P\). MA is the class of two-round interactive proofs where the prover goes first. Promise-MA (prMA) means you need to give the correct answer when the promise holds but can give an arbitrary response when it doesn't.

Since Jin-Yi Cai showed \(S_2^P\subseteq \mathrm{ZPP^{NP}}\), and under standard derandomization assumptions \(\mathrm{P^{NP}}=\mathrm{ZPP^{NP}}\), in the world most of us believe in, \(\mathrm{P^{NP}}= \mathrm{P^{prMA}}=L_2^P=S_2^P=\mathrm{ZPP^{NP}}.\)

Why define the class at all? It came out of the recent breakthroughs on circuit lower bounds. Lijie Chen, Shuichi Hirahara, Zeyong Li and Hanlin Ren showed that \(S_2^E\) requires circuits of near-maximum size \(2^n/n\), by giving a clever algorithm for the Range Avoidance problem: given a circuit mapping \(n\) bits to \(n+1\) bits, find a string outside its range. Korten and Pitassi sharpened their algorithm into the reduction from Range Avoidance to LOP and thus to \(L_2^P\). The payoff: \(L_2^E\) requires \(2^n/n\)-size circuits, and for every fixed \(k\) there is a language in \(L_2^P\) without \(n^k\)-size circuits. In my 2002 post I wrote that "\(S_2^P\) is the smallest class known to have these properties." That's where the quote from Rahul came from.

Karp–Lipton collapses have moved too. Korten and Pitassi asked whether NP in P/poly collapses PH to \(L_2^P\); Hirsch and Volkovich answered yes via \(\mathrm{PH}=\mathrm{P^{prMA}}\subseteq L_2^P\). 

Some of my old work on \(S_2^P\) now moves to \(L_2^P\). With Aduri Pavan and Samik Sengupta, we showed that if \(\mathrm{P}^{\mathrm{NP}[1]} = \mathrm{P}^{\mathrm{NP}[2]}\) then the polynomial-time hierarchy collapses to \(S_2^P\). Vyas Ram Selvam extended that collapse to \(\mathrm{P}_{||}^{\mathrm{NP}[1],\mathrm{MA}[1]}\subseteq \mathrm{P^{prMA}}\subseteq L_2^P\) under the same assumption.

Thirty years ago Yamakami and I constructed a language \(L(G)\in\Sigma_2^{P,G}\cap\Pi_2^{P,G}\) and used it to show generic oracles separate \(\Sigma_2^P\cap\Pi_2^P\) from \(\mathrm{P^{NP}}\). I later pushed \(L(G)\) into \(S_2^{P,G}\) and with a little effort can now show \(L(G)\in L_2^{P,G},\) showing that \(\mathrm{P^{NP}}\subsetneq L_2^P\) relative to generic oracles.

One thing that doesn't carry over: last fall I showed that the search version of \(S_2^P\) is equivalent to  \(\mathrm{TF}\Sigma_2\), a probably larger class, where the search version of \(L_2^P\) is just LOP, computationally equivalent to \(L_2^P\).

Whether  \(L_2^P=S_2^P\) or even \(L_2^P=\mathrm{ZPP^{NP}} \) remains open even in relativized worlds.

For more, read the well-written papers by Korten and Pitassi and Hirsch and Volkovich.