Strong vs. Weak Range Avoidance and the Linear Ordering Principle

In a pair of recent breakthroughs [1], [2] it was shown that the classes$\mathrm{S}_{2}^{\mathrm{E}}, \mathsf{ZPE}^{\mathsf{NP}}$and$\Sigma_{2}^{\mathrm{E}}$require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan [3]. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given a circuit$C:\{0,1\}^{n}\rightarrow\{0,1\}^{n+1}$, find an$n+1$-bit strina outside its range. Range Avoidance is a member of the class Tf$\Sigma_{2}^{\dot{\mathrm{F}}}$of total search problems in the second level of the polynomial hierarchy, analogous to its better-known counterpart TFNP in the first level. TF$\Sigma_{2}^{\overline{\mathrm{F}}}$was only recently introduced in [4] and its structure is not well understood. We investigate here the extent to which algorithms of the kind in [1], [2] can be applied to other search problems in this class, and prove a variety of results both positive and negative. On the positive side we show that Li's Range Avoidance algorithm [2] can be improved to give a reduction from Range Avoidance to a natural total search problem we call the Linear Ordering Principle or “LOP”: given a circuit$\prec:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$purportedly defining a total order on$\{0,1\}^{n}$, find either a witness that$\prec$is not a total order or else a minimal element in the ordering. The problem LOP is quite interesting in its own right, as it defines a natural syntactic subclass ”$\mathrm{L}_{2}^{\mathrm{P}}$“ of$\mathrm{s}_{2}^{\mathrm{p}}$which nonetheless maintains most of the interesting properties of$\mathsf{S}_{2}^{\mathrm{P}}$; in particular we show that$\mathrm{L}_{2}^{\mathrm{P}}$contains MA and that its exponential analogue$\mathrm{L}_{2}^{\mathrm{E}}$requires$2^{n}/n$size circuits. Both of these are consequences of our reduction from Range Avoidance to LOP. On the negative side we prove that the algorithms developed in [1], [2] cannot be extended to Strong Range Avoidance, a problem considered in the same paper which first introduced Range Avoidance [4]. In this problem we are given a circuit$C$:$\{0,1\}^{n}\backslash \{0^{n}\}\rightarrow\{0,1\}^{n}$, and once again seek a point outside its range. We give a separation in the decision tree (oracle) model showing that this problem cannot be solved in FP$\Sigma_{2}^{\mathrm{P}}\Vert$, which in particular rules out all of the new kinds of algorithms considered in [1], [2]. This black box separation is derived from a novel depth 3 AC°circuit lower bound for a total search problem, which we believe is of independent interest from the perspective of circuit complexity: we show that unlike previous depth 3 lower bounds, ours cannot be proven by reduction from a decision problem, and thus requires new techniques specifically tailored to total search problems. Proving lower bounds of this kind was recently proposed by Vyas and Williams in the context of the original (Weak) Avoid problem [5].