Upper and Lower Bounds for the Linear Ordering Principle

An important notion in this context is that of symmetric alternation. Namely, one of the best collapses was based on the following idea ([12], attributed to Sengupta): if polynomial-size circuits for SAT exist, two provers (defending the answers “yes” and “no”, respectively) send such circuits to a polynomial-time bounded verifier who can, in turn, use them to verify membership in any language in $\mathrm{𝐏𝐇}$. The corresponding class ${𝐒}_{\mathrm{𝟐}}^{𝐏}$ [13, 43] was thus shown to have fixed-polynomial circuit lower bounds. (In Section 2 we provide formal definitions for all less known classes we use.)

Indeed, since $\mathrm{𝐍𝐏}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}$, if SAT requires superpolynomial circuits, we are done. Otherwise, the Polynomial Hierarchy, which is known to contain “hard” languages (that is, for every $k\in \mathbb{N}$, $\mathrm{𝐏𝐇}⊈\mathrm{𝖲𝗂𝗓𝖾}[n^k]$) by Kannan’s theorem [31], collapses to ${𝐒}_{\mathrm{𝟐}}^{𝐏}$ and so do these hard languages. This technique has been known as a win-win argument in the literature [31, 8, 34, 50, 12, 44, 15, 51, 26]. Chen et al. [17] prove that there is a bidirectional relationship between fixed-polynomial lower bounds and Karp–Lipton–style theorems. In the linear-exponential regime, while the win-win argument can be extended to obtain superpolynomial lower bounds for ${𝐒}_{\mathrm{𝟐}}^{𝐄}$ (the linear-exponential version of ${𝐒}_{\mathrm{𝟐}}^{𝐏}$), it falls short of achieving truly exponential lower bounds, as it encounters the so-called “half-exponential” barrier (see [40]).

Upon further inspection, one can observe that the presumed polynomial-size circuits for SAT do not actually depend on the input itself, but rather on its length. Based on this observation, the collapse was deepened to the input-oblivious version of ${𝐒}_{\mathrm{𝟐}}^{𝐏}$, called ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ [14]. Yet, since ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ is not known and, in fact, not believed to contain $\mathrm{𝐍𝐏}$, the fixed-polynomial lower bounds do not (immediately) carry over to ${𝐎}_{\mathrm{𝟐}}^{𝐏}$.

This state of affairs remained unchanged for about fifteen years until a significant progress was made when Kleinberg et al. [33] initiated the study of total functions beyond $\mathrm{𝐓𝐅𝐍𝐏}$. While Karp–Lipton’s theorem has not been improved, lower bounds against $\mathrm{𝖲𝗂𝗓𝖾}[n^k]$ were pushed down to ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ [22] and ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ [36], a new${}^{\text{<a href="\#footnote1" title="footnote 1 ‣ Upper and Lower Bounds for the Linear Ordering Principle" class="ltx\_ref" style="font-size:70\%;"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}}$ important class which we describe in more detail below. At the same time, truly exponential lower bounds were established for ${𝐒}_{\mathrm{𝟐}}^{𝐄}$ [38] (as it turns out, ${𝐒}_{\mathrm{𝟐}}^{𝐄}={𝐎}_{\mathrm{𝟐}}^{𝐄}$ [22]) and ${𝐋}_{\mathrm{𝟐}}^{𝐄}$ [36].

An important feature of these new results was that they were based on reducing finding a hard function to a total search problem. Namely, the works of Korten [35] and Li [38] reduced the question to the so-called Range Avoidance problem: given a function $f:{\{0,1\}}^n\to {\{0,1\}}^m$ with $m>n$, represented by a Boolean circuit, find a point outside its image (this problem is known under the name dWPHP in the bounded arithmetic community and has implications in proof complexity, see [42, 28] and [37] for survey). In [16, 38], Range Avoidance has been reduced to symmetric alternation. Subsequently, Korten and Pitassi [36] reduced Range Avoidance to the Linear Ordering Principle: given an implicitly described ordering relation, either find the smallest element or report a breach of the linear order axioms (for the case of a linear order it is known as MIN in the bounded arithmetic community [18]). A polynomial-time Turing closure of this principle gave rise to a new class ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}$: a version of ${𝐒}_{\mathrm{𝟐}}^{𝐏}$ where the two provers provide points of a polynomial-time verifiable linear order on binary strings of a certain length (each point starting with the corresponding answer $0$ or $1$), and the prover that provides the smaller element wins.

In a parallel line of research, the same questions were considered for classes based on Merlin–Arthur proofs: Santhanam [44] has shown fixed-polynomial lower bounds for promise problems possessing such proofs (i.e. the class $\mathrm{𝐩𝐫𝐌𝐀}$). In [15], Chakaravarthy and Roy have shown a Karp–Lipton–style collapse and thus fixed-polynomial size lower bounds for the class ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$. In particular, they presented a new upper bound for ${𝐒}_{\mathrm{𝟐}}^{𝐏}$ by showing that ${𝐒}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐀𝐌}}$. Nonetheless, the relationship between ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ and the classes of symmetric alternation (including ${𝐒}_{\mathrm{𝟐}}^{𝐏}$, ${𝐎}_{\mathrm{𝟐}}^{𝐏}$, and then-unknown ${𝐋}_{\mathrm{𝟐}}^{𝐏}$) remained open.

Combining their upper bound for ${𝐒}_{\mathrm{𝟐}}^{𝐏}$ with a result of [3], that $\mathrm{𝐍𝐏}\subseteq 𝐏/\mathrm{𝐩𝐨𝐥𝐲}$ implies an “internal collapse” $\mathrm{𝐌𝐀}=\mathrm{𝐀𝐌}$ (which goes through for the promise versions of the classes as well), [15] concluded that the Polynomial Hierarchy collapses all the way to ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$. Subsequently, by applying the win-win argument, they obtained fixed-polynomial bounds for ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$, which (unlike $\mathrm{𝐩𝐫𝐌𝐀}$) is a class of languages. It is to be noted though that since $\mathrm{𝐩𝐫𝐌𝐀}$ is not a class of languages – while ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ is, there is no immediate way to carry any lower bound against $\mathrm{𝐩𝐫𝐌𝐀}$ over to ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$: it is not clear how to leverage (even) Turing reductions to construct a specific language consistent with a given promise problem.

Babai, Fortnow, and Lund [5] prove that if $\mathrm{𝐄𝐗𝐏}\subseteq 𝐏/\mathrm{𝐩𝐨𝐥𝐲}$, then $\mathrm{𝐄𝐗𝐏}=\mathrm{𝐌𝐀}$. Although this is a much larger class, the proof has the advantage that it does not relativize. More collapses in the exponential regime have been proved since then [27, 11], and the win-win argument yields superpolynomial lower bounds for some of them: $\mathrm{𝐌𝐀𝐄𝐗𝐏}⊈𝐏/\mathrm{𝐩𝐨𝐥𝐲}$ [10].

Two open questions regarding symmetric alternation have been stated explicitly:

• $\mathrm{■}$

  whether ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ is contained in ${𝐒}_{\mathrm{𝟐}}^{𝐏}$ [15] (note that for these two classes Karp–Lipton style theorems have been proved by [15] and by Samik Sengupta [unpublished], respectively),

• $\mathrm{■}$

  whether a Karp–Lipton–style theorem holds for ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ [36].

In this paper we resolve both these questions affirmatively by showing the following containment. (Recall that ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}$.)

Combining this theorem with a result of Chakaravarthy and Roy [15] that $\mathrm{𝐍𝐏}\subseteq 𝐏/\mathrm{𝐩𝐨𝐥𝐲}$ implies the collapse $\mathrm{𝐏𝐇}={𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$, we obtain a Karp–Lipton–style collapse theorem for ${𝐋}_{\mathrm{𝟐}}^{𝐏}$, thus resolving an open question posed in [36].

Together with the result of [12], it lines up all known non-input-oblivious classes for which a Karp–Lipton–style collapse has been shown: ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}\subseteq {\mathrm{𝐙𝐏𝐏}}^{\mathrm{𝐍𝐏}}\subseteq {𝚺}_{\mathrm{𝟐}}^{𝐏}.$

Another important result of this work is a new upper bound on ${𝐋}_{\mathrm{𝟐}}^{𝐏}$: we prove that ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$. The best known upper bound prior to our result followed from [36, 15]: ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐀𝐌}}$.

Our two new inclusions (Th. 31 and 22) yield the non-input-oblivious part of Fig. 1.

Th. 31 shows that ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ is currently the smallest non-input-oblivious class for which a Karp–Lipton–style collapse is known. On the other hand, such a collapse was also shown for ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ [14], which is input-oblivious. However, since the precise relationship between ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ and ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ remains unknown, one may ask: what is the strongest Karp–Lipton–style collapse? Our next result assists in navigating this question.

We note that the “non-promise” version of this inclusion, i.e. ${𝐏}^{{𝐎}_{\mathrm{𝟐}}^{𝐏}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}$, was already established in [14]. However, this result does not carry over to the promise case. A similar phenomenon arises in the non-input-oblivious analogue of this question: while we know that ${𝐏}^{{𝐒}_{\mathrm{𝟐}}^{𝐏}}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}$ [14], it still remains open whether ${𝐏}^{{\mathrm{𝐩𝐫𝐒}}_{\mathrm{𝟐}}^{𝐏}}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}$.

With this tool in hand, we can identify and show the strongest Karp–Lipton–style collapse that currently known. Namely, the collapse can be extended to ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$, where $\mathrm{𝐩𝐫𝐎𝐌𝐀}$ is the input-oblivious version of $\mathrm{𝐩𝐫𝐌𝐀}$ and therefore is contained in $\mathrm{𝐩𝐫𝐌𝐀}$. At the same time, Th. 25 allows us to show that ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ is also contained in ${𝐎}_{\mathrm{𝟐}}^{𝐏}$, thus making ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ smaller than both ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ and ${𝐎}_{\mathrm{𝟐}}^{𝐏}$!

Th. 25 also helps us to tighten the chain of containments between ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ and ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ using a newly defined ${\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏}$ class, an input-oblivious analogue of ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ (see Fig. 1).

Computing the number of accepting paths of a given non-deterministic Turing machine is a fundamental problem captured by the “counting” class $\mathrm{\#}𝐏$. Yet, this class appears to be too powerful since, by Toda’s Theorem [49], even a single query to it suffices to decide any language in the polynomial hierarchy, $\mathrm{𝐏𝐇}\subseteq {𝐏}^{\mathrm{\#}𝐏[\mathrm{𝟏}]}$! Given that, it is natural to explore approximations. To this end, one can consider the problem of Approximate Counting (ApproxCount for short) which refers to the task of approximating the number of accepting paths (within a constant factor). Equivalently, this problem can be framed as approximating the size of a set $S$ represented as the set of satisfying assignments of a Boolean circuit $C$. Previously, it was shown that this task could be carried out by a randomized algorithm using an $\mathrm{𝐍𝐏}$ oracle (${\mathrm{𝐅𝐁𝐏𝐏}}^{\mathrm{𝐍𝐏}}$) [48, 30] and by a deterministic algorithm using a $\mathrm{𝐩𝐫𝐀𝐌}$ oracle (${\mathrm{𝐅𝐏}}^{\mathrm{𝐩𝐫𝐀𝐌}}$) [47, 23]. Shaltiel and Umans [46] show how to accomplish this task in ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$, yet under a derandomization assumption. We note that all of these algorithms can be implemented using parallel (i.e. non-adaptive) oracle queries. That is, in ${\mathrm{𝐅𝐁𝐏𝐏}}_{\parallel }^{\mathrm{𝐍𝐏}},{\mathrm{𝐅𝐏}}_{\parallel }^{\mathrm{𝐩𝐫𝐀𝐌}}$ and ${\mathrm{𝐅𝐏}}_{\parallel }^{\mathrm{𝐍𝐏}}$, respectively. Jeřábek studies approximate counting in the context of bounded arithmetic and reduces to it many problems associated with complexity classes [29]. Approximate counting has also recently attracted considerable attention in the quantum literature [41, 1, 2, 39].

The decision version of the problem is to distinguish between two constant-factor estimates of the set size. For concreteness, consider the following problem called set-size estimation (or SSE for short): Given a set $S$ (via a Boolean circuit $C$) and an integer $m$ with the promise that either $\left|S\right|\ge m$ or $\left|S\right|\le m/2$, our goal is to decide which case holds. Interestingly, this problem is complete for the class $\mathrm{𝐒𝐁𝐏}$ (strictly speaking for the corresponding class of promise problems $\mathrm{𝐩𝐫𝐒𝐁𝐏}$) introduced in [7] by Böhler et al. as a relaxation of the class $\mathrm{𝐁𝐏𝐏}$ to the case when the acceptance probability is not required to be bounded away from $0$. This relaxation, as was shown in [7], yields additional power: $\mathrm{𝐌𝐀}\subseteq \mathrm{𝐒𝐁𝐏}\subseteq \mathrm{𝐀𝐌}$. The class $\mathrm{𝐒𝐁𝐏}$, which stands for small bounded-error polynomial-time, thus sits strictly between the two fundamental classes based on Arthur–Merlin protocols, yet its definition is very different. Moreover, $\mathrm{𝐒𝐁𝐏}$ remains the only known natural class that lies between $\mathrm{𝐌𝐀}$ and $\mathrm{𝐀𝐌}$.

In terms of upper bounds, in a seminal paper [23], Goldwasser and Sipser have exhibited an Arthur–Merlin protocol not only for this problem, but also for the case when the set $S$ is represented by a non-deterministic circuit! (A non-deterministic circuit $C(x,w)$ accepts $x$ if there exists a witness $w$ for which $C(x,w)=1$.) This more general version of the problem (WSSE, where the set $S$ is given via a non-deterministic circuit), is complete for the class $\mathrm{𝐩𝐫𝐀𝐌}$. (See Definition 12 for the formal definition of the problems; in fact, the factor-of-two gap in the estimates is arbitrary and can be replaced by any positive constant.) In fact, Goldwasser–Sipser’s protocol proves the containment both for languages ($\mathrm{𝐒𝐁𝐏}\subseteq \mathrm{𝐀𝐌}$) and for promise problems ($\mathrm{𝐩𝐫𝐒𝐁𝐏}\subseteq \mathrm{𝐩𝐫𝐀𝐌}$). At the same time, it is important to highlight the distinction between the two versions of the problem – i.e. for the “standard” (SSE) vs non-deterministic (WSSE) Boolean circuits – which appears to be (at the very least) non-trivial. Notably, the work of [7] established an oracle separation between $\mathrm{𝐒𝐁𝐏}$ and $\mathrm{𝐀𝐌}$.

On a similar note, by combining some of the previous techniques, we observe that ApproxCount can be carried out in ${\mathrm{𝐅𝐏}}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ rather than ${\mathrm{𝐅𝐏}}^{\mathrm{𝐩𝐫𝐀𝐌}}$, and, in fact, even in ${\mathrm{𝐅𝐏}}_{\parallel }^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$. We describe the main idea in more details in Section 1.4.2. We defer the formal proof of this fact to the full version of the paper. Given this observation, it is natural to study the computational power of ${𝐏}^{\text{ApproxCount}}$, that is, deterministic algorithms with oracle access to ApproxCount. Indeed, an immediate corollary of the above is that ${𝐏}^{\text{ApproxCount}}={𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ and ${𝐏}_{\parallel }^{\text{ApproxCount}}={𝐏}_{\parallel }^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$. At the same, O’Donnell and Say [41] previously showed that ${𝐏}_{\parallel }^{\text{ApproxCount}}={\mathrm{𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}$, a complexity class defined earlier by Han et al. [25]. One can think of ${\mathrm{𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}$ as a version of $\mathrm{𝐁𝐏𝐏}$ in which different computational paths (of the same probability) may have different lengths. Incidentally, it was established in [7] that ${\mathrm{𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}$ can be obtained from $\mathrm{𝐁𝐏𝐏}$ via the so-called “postselection” and that $\mathrm{𝐒𝐁𝐏}\subseteq {\mathrm{𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}$ (and resp. $\mathrm{𝐩𝐫𝐒𝐁𝐏}\subseteq {\mathrm{𝐩𝐫𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}$). Putting all together, one arrives at the following three clusters of complexity classes associated with approximate counting:

where both inclusions are believed to be strict.

The upper bound ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ is obtained by developing a process that, given an arbitrary element in a linearly ordered set, rapidly converges to the set’s minimum.

In [36], Korten and Pitassi show that $\mathrm{𝐌𝐀}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$. The inclusion ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$ essentially follows their argument with the additional observation that since ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ is a syntactic class, not only it contains $\mathrm{𝐌𝐀}$ but it is also consistent with $\mathrm{𝐩𝐫𝐌𝐀}$. Thus one can first construct a pseudorandom generator using an ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ oracle [35, 36] and then leverage it to derandomize the $\mathrm{𝐩𝐫𝐌𝐀}$ oracle not just in $\mathrm{𝐩𝐫𝐍𝐏}$, but actually in $\mathrm{𝐍𝐏}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$! Therefore, ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐏}^{{𝐋}_{\mathrm{𝟐}}^{𝐏}}={𝐋}_{\mathrm{𝟐}}^{𝐏}$.

We also observe that since the pseudorandom generator depends only on the input length (and not the input itself), derandomization also helps settling the relations between input-oblivious classes to a certain extent. The main difference is that unlike their non-oblivious counterparts, they do not posses all the desired properties w.r.t. Turing closure and natural containments. However, Th. 25 (its technique is described below) eventually helps us building the chain from ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ to ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ in two different ways: both directly and through derandomization and intermediate classes using ${\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏}$.

A Karp–Lipton–style collapse to ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ follows from [15] by combining several previously known techniques. However, is this collapse stronger than the known collapse to ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ [14]? The inclusion $\mathrm{𝐩𝐫𝐎𝐌𝐀}\subseteq {\mathrm{𝐩𝐫𝐎}}_{\mathrm{𝟐}}^{𝐏}$ can be transferred from a somewhat similar statement that was proven in [14]; however, in order to prove ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}$ we need also the inclusion ${𝐏}^{{\mathrm{𝐩𝐫𝐎}}_{\mathrm{𝟐}}^{𝐏}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}$, which seems novel. The main idea is that the two provers corresponding to the oracle give their input-oblivious certificates prior to the whole computation, and the verification algorithm performs a cross-check not only between the certificates of different provers but also between the certificates of the same prover, which allows us to simulate all oracle queries to ${\mathrm{𝐩𝐫𝐎}}_{\mathrm{𝟐}}^{𝐏}$ in a single ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ algorithm. Indeed, our approach is made possible by the input-oblivious nature of the computational model: while the oracle queries may be adaptive and not known in advance (due to potential queries outside of the promise set), the certificates are universal for the whole computation and nothing else is required.

Starting from Karp–Lipton’s paper [32], Kannan’s fixed-polynomial circuit complexity lower bounds [31] have been improving accordingly to new collapses: if a new collapse $\mathrm{𝐍𝐏}\subseteq 𝐏/\mathrm{𝐩𝐨𝐥𝐲}⟹\mathrm{𝐏𝐇}=𝒞$ is shown for a class $𝒞$ containing $\mathrm{𝐍𝐏}$, it immediately implies lower bounds for this class, because if $\mathrm{𝐍𝐏}⊈𝐏/\mathrm{𝐩𝐨𝐥𝐲}$, we are already done.

However, a collapse to ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ [14] did not imply lower bounds for ${𝐎}_{\mathrm{𝟐}}^{𝐏}$, because $\mathrm{𝐍𝐏}$ is unlikely to be contained in it (after all, ${𝐎}_{\mathrm{𝟐}}^{𝐏}\subseteq 𝐏/\mathrm{𝐩𝐨𝐥𝐲}$). It was not until nearly two decades later that lower bounds for ${𝐎}_{\mathrm{𝟐}}^{𝐏}$ have been shown by Gajulapalli, Li, and Volkovich [22] building on recent progress for the range avoidance problem [35, 38], thus matching the progress on the two questions again.

Korten and Pitassi [36] have shown fixed-polynomial lower bounds for their new class ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ without showing a collapse result, thereby introducing a misalignment once again, yet this time in the opposite direction. Our paper’s inclusion ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$ restores the balance.

However, the observation that in the input-oblivious world the currently best collapse ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ reopens this question. Does this class possess fixed-polynomial circuit lower bounds? One can observe that Santhanam’s proof [44] of $\mathrm{𝖲𝗂𝗓𝖾}[n^k]$ lower bounds for promise problems in $\mathrm{𝐩𝐫𝐌𝐀}$ is input-oblivious. Indeed, the presented hard promise problems are actually in $\mathrm{𝐩𝐫𝐎𝐌𝐀}$! However, these promise problems do not yield a language in ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}$ that is hard for $\mathrm{𝖲𝗂𝗓𝖾}[n^k]$, and we leave this question for further research.

The best class for which fixed-polynomial circuit lower bounds can be proved (trivially) is ${𝐏}^{\epsilon \text{-}\text{Hard-tt}}$ (for any particular fixed $\epsilon >0$), where $\epsilon$-Hard-tt, asks given $1^{2^n}$, to output a truth table of a function ${\{0,1\}}^n\to \{0,1\}$ of circuit complexity at least $2^{\epsilon n}$ (Korten [35] defines a smoother version of it where the input length is not necessarily a power of two.) Can one prove a collapse to this class? Note that for the purpose of fixed-polynomial lower bounds even a limited version of $\epsilon$-Hard-tt suffices where the truth table is non-empty for a number of entries greater than any polynomial and its complexity is only superpolynomial.

Switching to the linear-exponential regime, in [36], Korten and Pitassi have shown that ${𝐋}_{\mathrm{𝟐}}^{𝐄}$ – the exponential version of ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ – contains a language of circuit complexity $2^n/n$. By translation, our upper bound scales as ${𝐋}_{\mathrm{𝟐}}^{𝐄}\subseteq {𝐄}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}={𝐄}^{{\mathrm{𝐩𝐫𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}}$. As a corollary we obtain a new circuit lower bound for ${𝐄}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ (and hence for ${𝐄}^{{\mathrm{𝐩𝐫𝐁𝐏𝐏}}_{\mathrm{𝐩𝐚𝐭𝐡}}})$. To the best of our knowledge, the strongest previously established bound for this class was “half-exponential” that followed from the bound on $\mathrm{𝐌𝐀𝐄𝐗𝐏}$ [40].

It is to be noted that this corollary could be viewed as an unconditional version of a result of Aydinliog̃lu et al. [4] as it recovers and strengthens their conclusion. In particular, [4] have shown the following (stated using slightly different terminology): if ${𝐏}^{\mathrm{𝐍𝐏}}$ is consistent with $\mathrm{𝐩𝐫𝐀𝐌}$ or even $\mathrm{𝐩𝐫𝐒𝐁𝐏}$, then ${𝐄}^{\mathrm{𝐍𝐏}}$ contains a language of circuit complexity $2^n/n$. Indeed, given the premises we obtain that ${𝐄}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}\subseteq {𝐄}^{{𝐏}^{\mathrm{𝐍𝐏}}}={𝐄}^{\mathrm{𝐍𝐏}}$ from which the claim follows directly by the corollary.

Similarly to ${𝐋}_{\mathrm{𝟐}}^{𝐏}$, one could define a class of languages reducible to Avoid. A similar class of search problems, $\mathrm{𝐀𝐏𝐄𝐏𝐏}$, has been defined by [33, 35] (and Korten [35] proved that constructing a hard truth table is a problem that is complete for this class under ${𝐏}^{\mathrm{𝐍𝐏}}$-reductions); however, we are asking about a class of languages. Korten and Pitassi have shown that ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ can be equivalently defined using many-one, Turing, or ${𝐏}^{\mathrm{𝐍𝐏}}$-reductions, thus there are several options. One can observe that the containment ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$ (Th. 31) is essentially proved via the intermediate class ${𝐏}^{\text{Avoid},\mathrm{𝐍𝐏}}$ that uses both an oracle for Range Avoidance (a single-valued or an essentially unique [36] version) and an oracle for SAT. Can one prove that one of the containments in ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐏}^{\text{Avoid},\mathrm{𝐍𝐏}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$ is in fact an equality?

One can define an input-oblivious version ${\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏}$ of ${𝐋}_{\mathrm{𝟐}}^{𝐏}$, however, contrary to $\mathrm{𝐍𝐏}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$, it is not obvious whether $\mathrm{𝐎𝐍𝐏}\subseteq {\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏}$ or even $\mathrm{𝐎𝐍𝐏}\subseteq {𝐏}^{{\mathrm{𝐩𝐫𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏}}$. Still ${𝐏}^{{\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}\cap {𝐋}_{\mathrm{𝟐}}^{𝐏}$. Nevertheless, one can extend the proof of ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$ to show ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}\subseteq {𝐏}^{{\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏},\mathrm{𝐍𝐏}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$ and ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}\subseteq {𝐏}^{{\mathrm{𝐎𝐋}}_{\mathrm{𝟐}}^{𝐏},\mathrm{𝐩𝐫𝐎𝐍𝐏}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}\cap {𝐋}_{\mathrm{𝟐}}^{𝐏}$. (These containments are included in Fig. 1, they give also an alternative proof of ${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}$ that still uses Th. 25.)

1. 1.

   Can one strengthen our inclusion ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ to ${𝐒}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$? One can try combining our techniques with the proof of ${𝐒}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐀𝐌}}$ by Chakaravarthy and Roy [15].

   Note that in the other direction it is open even whether $\mathrm{𝐒𝐁𝐏}\subseteq {𝐒}_{\mathrm{𝟐}}^{𝐏}$.

2. 2.

   Chakaravarthy and Roy [15] asked whether ${𝐏}^{\mathrm{𝐩𝐫𝐌𝐀}}$ and ${𝐏}^{{\mathrm{𝐩𝐫𝐒}}_{\mathrm{𝟐}}^{𝐏}}$ are contained in ${𝐒}_{\mathrm{𝟐}}^{𝐏}$. While we resolved the first question, the second one remains open. We note that, although in the input-oblivious world both inclusions hold (${𝐏}^{\mathrm{𝐩𝐫𝐎𝐌𝐀}}\subseteq {𝐏}^{{\mathrm{𝐩𝐫𝐎}}_{\mathrm{𝟐}}^{𝐏}}\subseteq {𝐎}_{\mathrm{𝟐}}^{𝐏}$, Cor. 26), the proof of the latter inclusion (Th. 25) is essentially input-oblivious (one needs to give all the certificates for the oracle non-adaptively, and queries cannot be predicted because oracle answers cannot be predicted for promise problems).

3. 3.

   As was mentioned, the ${\mathrm{𝐅𝐏}}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ procedure for approximate counting can be implemented in ${\mathrm{𝐅𝐏}}_{\parallel }^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$ – that is, using parallel (i.e. non-adaptive) oracle queries. On the other hand the containment ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$, which uses approximate counting as a black-box subroutine, seems to require sequential, adaptive queries. Could one implement the latter containment using parallel queries (i.e. show that ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq {𝐏}_{\parallel }^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$)? In particular, as $\mathrm{𝐏𝐏}$ is consistent with $\mathrm{𝐩𝐫𝐒𝐁𝐏}$ [7] and is closed under non-adaptive Turing reductions [20], this would imply that ${𝐋}_{\mathrm{𝟐}}^{𝐏}\subseteq \mathrm{𝐏𝐏}$. Note that it is unknown even whether ${𝐏}^{\mathrm{𝐍𝐏}}\subseteq \mathrm{𝐏𝐏}$, while ${𝐏}^{\mathrm{𝐍𝐏}}\subseteq {𝐋}_{\mathrm{𝟐}}^{𝐏}$. Moreover, there is an oracle separating the former two classes [6].

4. 4.

   A recent work of Gajulapalli et al. [21] places ${𝐋}_{\mathrm{𝟐}}^{𝐏}$ in the class ${\mathrm{𝐔𝐄𝐎𝐏𝐋}}^{\mathrm{𝐍𝐏}}$ (where $\mathrm{𝐔𝐄𝐎𝐏𝐋}$ consists of problems that are many-one polynomial-time reducible to Unique-End-of-Potential-Line, see [19, 21]), which appears to be incomparable to our result (Th. 22). Can one determine the relative status of ${\mathrm{𝐔𝐄𝐎𝐏𝐋}}^{\mathrm{𝐍𝐏}}$ and ${𝐏}^{\mathrm{𝐩𝐫𝐒𝐁𝐏}}$?