Strong vs. Weak Range Avoidance and the Linear Ordering Principle

In a pair of recent breakthroughs [1], [2] it was shown that the classes <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{S}_{2}^{\mathrm{E}}, \mathsf{ZPE}^{\mathsf{NP}}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{2}^{\mathrm{E}}$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C:\{0,1\}^{n}\rightarrow\{0,1\}^{n+1}$</tex>, find an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n+1$</tex> -bit strina outside its range. Range Avoidance is a member of the class Tf <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{2}^{\dot{\mathrm{F}}}$</tex> of total search problems in the second level of the polynomial hierarchy, analogous to its better-known counterpart TFNP in the first level. TF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{2}^{\overline{\mathrm{F}}}$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\prec:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$</tex> purportedly defining a total order on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{0,1\}^{n}$</tex>, find either a witness that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\prec$</tex> 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 ” <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{L}_{2}^{\mathrm{P}}$</tex> “ of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{s}_{2}^{\mathrm{p}}$</tex> which nonetheless maintains most of the interesting properties of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathsf{S}_{2}^{\mathrm{P}}$</tex> ; in particular we show that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{L}_{2}^{\mathrm{P}}$</tex> contains MA and that its exponential analogue <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{L}_{2}^{\mathrm{E}}$</tex> requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{n}/n$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C$</tex>: <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{0,1\}^{n}\backslash \{0^{n}\}\rightarrow\{0,1\}^{n}$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{2}^{\mathrm{P}}\Vert$</tex>, 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].