betaFeedback

WorksComputer Science

Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time

Abstract

We show that every multitape nondeterministic Turing machine can be simulated deterministically in subexponential time. Specifically, we show that the recent algorithms for 33-SAT\mathsf{SAT} presented by OpenAI and Anthropic imply NTIME[t]⊆DTIME[2O(tlog⁡log⁡t/log⁡t)]\mathsf{NTIME}[t]\subseteq\mathsf{DTIME}[2^{O(t \log \log t/\sqrt{\log t})}], and that a stronger consequence of their proof yields NTIME[t]⊆DTIME[2O(t/log⁡t)].\mathsf{NTIME}[t] \subseteq\mathsf{DTIME}[2^{O(t /\sqrt{\log t})}]. More generally, we show that any subexponential time algorithm for solving circuit-CSPs transfers to a deterministic simulation of NTIME\mathsf{NTIME} with the same savings. Our results follow from new generalizations of Cook–Levin, which may be of independent interest.

Introduction

The exponential time hypothesis (ETH) of Impagliazzo and Paturi [11] has been recently refuted:

Fact 1.1 [16 Cla26]. 3-SAT over nn variables and O(n)O(n) clauses can be solved in time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}.

It’s natural to ask whether this result implies a more general speed-up for other problems that can be solved efficiently with nondeterminism. However, the most direct attempt to show NTIME[t]⊆DTIME[2o(t)]\mathrm{NTIME}[t] \subseteq\mathrm{DTIME}\left[2^{o(t)}\right] based on Lemma 1.1 fails: the most efficient known version of Cook–Levin reduces acceptance of a nondeterministic Turing machine running in time tt to the satisfiability of a 3-CNF formula over O(tlog⁡t)O(t\log t) variables and clauses [6]. Plugging this into Lemma 1.1 yields NTIME[t]⊆DTIME[2O(tlog⁡t)]\mathrm{NTIME}[t] \subseteq\mathrm{DTIME}\left[2^{O(t\sqrt{\log t})}\right], which is worse than the trivial upper bound of DTIME[2O(t)]\mathrm{DTIME}[2^{O(t)}]. So this proof strategy would require improving upon the parameters of quasilinear Cook–Levin, which is a long-standing open problem.

In this work, we show that the recent ETH refutation does indeed apply to the general simulations of nondeterministic computation—even with the same savings:

Theorem 1 (Subexponential Simulation of NTMs). For every growth function t:N→Nt:\mathbb{N} \to\mathbb{N} such that t(n)≥nt(n) \ge n, we have

NTIME[t]⊆DTIME[2O(t/log⁡t)].\mathrm{NTIME}[t] \subseteq\mathrm{DTIME}\left[2^{O(t/\sqrt{\log t})}\right].

We obtain Theorem 1 as a corollary of a more general “transfer” theorem showing how further improvements in algorithms for SAT yield further improvements in the NTIME vs. DTIME setting. To state this transfer theorem, we first define constraint-satisfaction problems (CSPs) where each constraint is represented by a circuit (see Figure 1).

A circuit-CSP over $n=8$ variables and $m=4$ constraints of arity 5 and density $14/8$

Figure 1. A circuit-CSP over n=8n = 8 variables and m=4m = 4 constraints of arity 5 and density 14/814/8.

Definition 1.2 (Circuit-CSP). A circuit-CSP Φ\Phi consists of Boolean variables x:=x1,…,xn\boldsymbol{x} := x_1,\ldots,x_n together with constraints (S1,C1),…,(Sm,Cm)(S_1,C_1),\ldots,(S_m,C_m), where each SjS_j is a tuple of distinct variables from x\boldsymbol{x} and each CjC_j is a Boolean circuit on ∣Sj∣\lvert S_j\rvert inputs. An assignment to x\boldsymbol{x} satisfies Φ\Phi if Cj(Sj)=1C_j(S_j)=1 for all jj. The arity of Φ\Phi is max⁡j∣Sj∣\max_j \lvert S_j\rvert, and its density is 1n∑j∣Sj∣\frac{1}{n}\sum_j \lvert S_j\rvert.

For instance, if all CjC_j are disjunctions of kk literals (variables or negations thereof), then this definition corresponds to a kk-CNF. Generally, larger arity and density make it more difficult to decide if a circuit-CSP is satisfiable.

Stated in terms of circuit-CSPs, our transfer theorem is as follows:

Theorem 2 (Circuit-CSP solvers imply NTM simulators). Let t(n)t(n), k(n)k(n), and s(n)s(n) be growth functions such that t(n)≥nt(n)\ge n and 2≤s(n)≤n/log⁡n2\le s(n)\le n/\log n. Suppose that circuit-CSP over nn variables with arity at most k(n)k(n) and density at most 22 can be solved in time 2O(n/s(n))poly⁡(∣Φ∣)2^{O(n/s(n))}\operatorname{poly}(\lvert\Phi\rvert), then

NTIME⁡[t]⊆DTIME⁡[2O(t/k(t))⋅2O(t/s(t))].\operatorname{NTIME}[t]\subseteq\operatorname{DTIME}\left[2^{O(t/k(t))}\cdot2^{O(t/s(t))}\right].

Notice that as long as k(n)≥Ω(s(n))k(n)\ge\Omega(s(n)), the above theorem losslessly transfers any improvements in a circuit-CSP solver to an improved upper bound for NTIME. In order to recover Theorem 1 from Theorem 2, we need a circuit-CSP version of Lemma 1.1. We show that [16 Theorem D.1] and the analogous [Cla26, Lemma 8 and Theorem A] imply the following:

Fact 1.3 ([16 Cla26]). Circuit-CSP over nn variables with arity at most n9/10n^{9/10} and constant density can be solved in time 2O(n/log⁡n)poly⁡(∣Φ∣)2^{O(n/\sqrt{\log n})}\operatorname{poly}(\lvert\Phi\rvert).

Combining this fact with Theorem 2 directly recovers Theorem 1.

It is worth noting that Lemma 1.3 is stronger than Lemma 1.1. Naturally, one would hope for an improvement to the state of NTIME vs. DTIME even if we are only able to improve the algorithm for 3-SAT and not circuit-CSP. We therefore provide a variant of Theorem 2 that exchanges an easier-to-satisfy assumption for weaker parameters:

Theorem 3 (3-SAT solvers imply NTM simulators). Let t(n)≥nt(n)\ge n and 2≤s(n)≤n/log⁡n2\le s(n)\le n/\log n be growth functions. Suppose that 3-SAT over nn variables and O(n)O(n) clauses can be solved in time 2O(n/s(n))2^{O(n/s(n))}, then

NTIME⁡[t]⊆DTIME⁡[2O(tlog⁡s(t)/s(t))].\operatorname{NTIME}[t]\subseteq\operatorname{DTIME}\left[2^{O(t\log s(t)/s(t))}\right].

This conclusion is weaker than Theorem 2 since it has an extra factor of log⁡s(t)\log s(t) in the exponent. Setting s(n)=log⁡(n)s(n)=\sqrt{\log(n)} and applying Lemma 1.1 gives the following corollary, which is a weaker version of Theorem 1: NTIME[t]⊆DTIME[2O(tlog⁡log⁡t/log⁡t)]\mathrm{NTIME}[t]\subseteq\mathrm{DTIME}\left[2^{O\left(t\log\log t/\sqrt{\log t}\right)}\right].

Remark 1.4. [16]’s Theorem D.1 is stronger than Lemma 1.1 or even Lemma 1.3, as it solves the more difficult problem of Boolean tensor contraction (see Lemma 6.1). Our goal when formulating Theorem 2 in terms of circuit-CSP was to choose a “minimal” problem for which algorithmic improvements would translate losslessly to NTIME.

Relatedly, [16 Cla26] further prove that their algorithms count the number of satisfying assignments (e.g., they solve #circuit-CSP). With this strengthened assumption and some additional care in the argument, all of our deterministic algorithms can also produce a count of the number of accepting paths.

Background and context

Prior to this work, very little was known about the relationship between NTIME and DTIME. Paul, Pippenger, Szemerédi, and Trotter [18] showed the modest separation NTIME[n]≠DTIME[n]\mathrm{NTIME}[n]\ne\mathrm{DTIME}[n], which was then improved to NTIME[nlg⁡∗(n)]≠DTIME[nlg⁡∗(n)]\mathrm{NTIME}[n\sqrt{\lg^*(n)}]\ne\mathrm{DTIME}[n\sqrt{\lg^*(n)}] by Santhanam [19]. For upper bounds, the question we study here, even less was known. Lipton conjectured that for any ε>0\varepsilon>0,

NTIME[t]⊆DTIME[2εt],\mathrm{NTIME}[t]\subseteq\mathrm{DTIME}[2^{\varepsilon t}],

which has remained an open question and has been asked multiple times in the literature [14, 15, 13, 7]. Some progress was made by [13], who proved a DTIME[2ct]\mathrm{DTIME}[2^{ct}] upper bound with an improvement in the constant cc. Theorem 1 settles Lipton’s conjecture in the affirmative by a large margin.

It’s worth noting that there exists an oracle relative to which Lipton’s conjecture is false [2, 15, 7]. Therefore, our proof, by necessity, does not relativize. Furthermore, Bennett and Gill’s proof that P≠NP\mathrm{P}\ne\mathrm{NP} relative to a random oracle [1] can be straightforwardly extended to show that Lipton’s conjecture is false even relative to a random oracle. Therefore, our result is an example of a natural statement whose truth differs in the random-oracle and unrelativized worlds (cf. [3]).

Single-tape Turing machines. For single-tape Turing machines, the situation is much simpler, and we have the following chain of inclusions:

NTIME1[t]⊆NSPACE1[O(t)]⊆DTIME[2O(t)]⊆DTIME1[2O(t)].\mathrm{NTIME}_{1}[t]\subseteq\mathrm{NSPACE}_{1}[O(\sqrt{t})]\subseteq\mathrm{DTIME}[2^{O(\sqrt{t})}]\subseteq\mathrm{DTIME}_{1}[2^{O(\sqrt{t})}].

where the subscript 1 indicates single-tape machines. The first inclusion was proven by Hopcroft and Ullman [10] (and strictly speaking requires t(n)≥n2t(n)\ge n^2), the second uses the standard configuration graph technique [5, 20], and the last one uses the quadratic blow-up for multitape simulations [9]. Unfortunately, we don’t know how to extend time vs. space results that hold under robust models of computation (e.g., multitape or RAM) to the nondeterministic setting, and thus they do not imply anything about NTIME vs. DTIME [HPV77, Wil25].

Technical Overview

Our main technical lemma is a generalized version of Cook–Levin that, instead of mapping a nondeterministic Turing machine to a single 3-CNF, maps it to a collection of circuit-CSPs:

Lemma 2.1 (Generalized Cook–Levin for CSPs). Let MM be a nondeterministic multitape Turing machine that runs in time t(n)t(n), and let b:N→Nb:\mathbb{N}\to\mathbb{N} be such that b(n)≤t(n)b(n)\le t(n). Then, there is a deterministic algorithm that takes an input xx to MM of length nn and returns circuit-CSPs Φ1,…,Φm\Phi_1,\ldots,\Phi_m for m=2O(t(n)/b(n))m=2^{O(t(n)/b(n))} in time m⋅poly⁡(t(n))m\cdot\operatorname{poly}(t(n)), such that

  1. MM accepts input xx if and only if some Φℓ\Phi_\ell is satisfiable, and

  1. each Φℓ\Phi_\ell has O(t(n))O(t(n)) variables, arity O(b(n))O(b(n)), density at most 2, and O(t(n)/b(n))O(t(n)/b(n)) constraint circuits each of size O(b(n)log⁡b(n))O(b(n)\log b(n)).

We then obtain the following corollary, which looks more like the original Cook–Levin because it maps a nondeterministic Turing machine to a collection of 3-CNFs. We need this corollary to prove Theorem 3 since it only assumes an improvement for 3-SAT solvers, not the more general circuit-CSP solvers.

Corollary 2.2 (Generalized Cook–Levin). Let MM be a nondeterministic multitape Turing machine that runs in time t(n)t(n), let xx be a length nn input to MM, and let b(n)≤t(n)b(n) \le t(n). There is a deterministic algorithm that maps xx to 3-CNF formulas φ1,…,φm\varphi_1,\ldots,\varphi_m that runs in time m⋅poly⁡(t(n))m \cdot\operatorname{poly}(t(n)) for m=2O(t(n)/b(n))m = 2^{O(t(n)/b(n))} such that

  1. MM accepts input xx if and only if some φℓ\varphi_\ell is satisfiable, and

  1. each φℓ\varphi_\ell has O(t(n)log⁡b(n))O(t(n)\log b(n)) variables and clauses.

If we set b=tb=t in the above, an inspection of the proof shows that this results in a single 3-CNF formula φ\varphi over O(tlog⁡t)O(t\log t) variables. Additionally, the poly⁡(t)\operatorname{poly}(t) runtime can be made t⋅poly⁡(log⁡t)t \cdot\operatorname{poly}(\log t) with some additional care in the argument. We do not take this care since, for the parameter regime that we care about, it does not impact the result. Therefore, this corollary recovers the classical quasilinear Cook–Levin and so is indeed a generalization. See Table 1 for a detailed comparison between our results and quasilinear Cook–Levin.

ReductionOutputCountVariablesConstraintsRuntime
Classical Cook–Levin [6]3-CNF1O(tlog⁡t)O(t \log t)O(tlog⁡t)O(t \log t) clauses of width 3tpoly⁡(log⁡t)t \operatorname{poly}(\log t)
Generalized Cook–Levin CSP form (Lemma 2.1)circuit-CSPs Φℓ\Phi_\ell2O(t/b)2^{O(t/b)}O(t)O(t)O(t/b)O(t/b) circuits of arity O(b)O(b), size O(blog⁡b)O(b \log b), and density ≤2\le22O(t/b)poly⁡(t)2^{O(t/b)}\operatorname{poly}(t)
Generalized Cook–Levin 3-CNF form (Lemma 2.2)3-CNFs φℓ\varphi_\ell2O(t/b)2^{O(t/b)}O(tlog⁡b)O(t \log b)O(tlog⁡b)O(t \log b) clauses of width 32O(t/b)poly⁡(t)2^{O(t/b)}\operatorname{poly}(t)

Table 1. Three encodings of a nondeterministic time-tt Turing machine. The machine accepts iff some output is satisfiable. Variable and constraint bounds are per output. At b=tb=t, the last row recovers the first.

Remark 2.3. These generalizations of Cook–Levin have a similar flavor to the sparsification lemma of Impagliazzo, Paturi, and Zane [12]. In fact, in the language of [12], Lemma 2.2 with b(n):=Θ(1/ε)b(n) := \Theta(1/\varepsilon) is a sub-exponential reduction family (SERF) from the language L(M)L(M), parameterized by runtime, to 3-CNF parameterized by the number of clauses.

Theorem 2 and Theorem 3 are immediate from Lemma 2.1 and Lemma 2.2. We prove them in Section 4.

Proof overview of lem:cl-for-CSP and cor:cl

The typical proof of classical quasilinear Cook–Levin can be described in 2 steps:

  1. Use a result of [17] to convert the nondeterministic TM into a size O(tlog⁡t)O(t \log t) circuit CC, and then,

  1. use a result of [21] to convert this circuit CC into a 3-CNF φ\varphi over O(tlog⁡t)O(t \log t) variables.

The tlog⁡tt \log t bound on the number of variables results from encoding the entire Turing machine as a single large circuit CC. Suppose that instead, we were somehow able to break the Turing machine up into size bb segments and encode each segment individually. This would result in O(t/b)O(t/b) circuits each of size O(blog⁡b)O(b \log b). Then, when we reach step 2, we would have a 3-CNF over O(t/b)⋅O(blog⁡b)=O(tlog⁡b)O(t/b) \cdot O(b \log b) = O(t \log b) different variables. This is the entire idea of the proof. It turns out that when we break the Turing machine up into size bb segments, there are 2O(t/b)2^{O(t/b)} ways to do so. This is why we end up with 2O(t/b)2^{O(t/b)} different 3-CNFs in the statement of Lemma 2.2, and also why we cannot afford to make bb arbitrarily small.

How to segment an NTM. Our technique is similar to that of [13 Section 5]. We split the runtime of a tt-time Turing machine MM into t/bt/b epochs, each of length bb. Additionally, we split each of the Turing machine’s dd tapes into contiguous blocks, each consisting of bb cells. Then, a result of [HPV77] (restated in Lemma 3.1) allows us to assume without loss of generality that MM is block-respecting, meaning that it only moves its tape heads from one block to another at the end of an epoch. In other words, for a fixed epoch i∈[t/b]i \in[t/b] and a fixed tape j∈[d]j \in[d], that tape head will stay within a single block (see Figure 2). We let π∈{L,S,R}(t/b−1)×d\pi\in\{L, S, R\}^{(t/b-1)\times d} be the pattern that MM’s heads take (see Figure 3). Specifically,

A 3-tape Turing machine split into blocks

Figure 2. A 3-tape Turing machine split into t/bt/b blocks of bb cells each. The Turing machine is block-respecting if each of its heads stays within a single block during each length-bb epoch.

The same 3-tape Turing machine at the start of epochs $i$ and $i+1$

Figure 3. The same 3-tape Turing machine at the start of epochs ii and i+1i+1; the block that each head stays in during that epoch is shaded. In this example, the pattern for epoch ii is πi=(R,L,S)\pi_i=(R,L,S): the head on tape 1 moves right one block, the head on tape 2 moves left one block, and the head on tape 3 remains in the same block.

πi,j={L,if M’s jth head moves a block to the left after epoch iS,if M’s jth head remains in the same block after epoch iR,if M’s jth head moves a block to the right after epoch i\pi_{i,j} = \begin{cases} L, & \text{if } M\text{’s }j\text{th head moves a block to the left after epoch }i \\ S, & \text{if } M\text{’s }j\text{th head remains in the same block after epoch }i \\ R, & \text{if } M\text{’s }j\text{th head moves a block to the right after epoch }i \end{cases}

A pattern determines the data flow of the computation: for every epoch, it tells us which earlier epoch last worked on the block that the current epoch reads. There are 3d(t/b−1)=2O(t/b)3^{d(t/b-1)} = 2^{O(t/b)} patterns, and we do not know a priori which one the computation follows, so we try all of them, constructing one circuit-CSP (or 3-CNF) per pattern.1

How to construct a circuit-CSP from a segmented NTM. Let’s suppose we have fixed a guess for the pattern π\pi. Using a result of [17] (restated in Lemma 3.3), we construct, for each epoch ii, a constraint circuit CiC_i of size O(blog⁡b)O(b \log b) that ensures the validity of the computation of MM within that epoch. The final circuit-CSP comes from taking the AND of all the CiC_i’s.

The variables of circuit CiC_i fall into three groups:

  • x(i)x^{(i)} describes the block configuration at the start of epoch ii (the block contents, head positions, and state),

  • y(i)y^{(i)} describes the block configuration at the end of epoch ii, and

  • w(i)w^{(i)} are the bb nondeterministic choices made by MM during epoch ii.

Then, CiC_i checks whether y(i)y^{(i)} is an honest description of the configuration after running MM for bb steps from configuration x(i)x^{(i)} with nondeterministic choices w(i)w^{(i)}. If it’s the last epoch, we of course additionally check whether MM accepts.

The variables x(i)x^{(i)} and y(i)y^{(i)} are shared among circuits. Each block’s content in x(i)x^{(i)} is the corresponding part of y(i′)y^{(i')} for the last epoch i′i' that worked on that block, as determined by π\pi, and the state and head positions come from y(i−1)y^{(i-1)}. For example, in Figure 4a, since epochs 1 and 4 work on block 0, and epochs 2 and 3 work on block 1, the output variables corresponding to block 0 in y(1)y^{(1)} are identified with the inputs for block 0 in x(4)x^{(4)}, and similarly, the output variables corresponding to block 1 in y(2)y^{(2)} are identified with the inputs for block 1 in x(3)x^{(3)}.

Computation graph and Circuit-CSP for a single-tape Turing machine with four epochs

Figure 4. (a) Computation graph. Each node represents an epoch, color coded according to the block that contains the tape head during said epoch. Green arrows carry the state and head position to the next epoch. Pink arrows carry a block’s contents from its last visit to its next visit. (b) Circuit-CSP Φπ\Phi_\pi. The variables below CiC_i encode epoch ii’s nondeterministic choices (gray), final block contents (blue or orange), and final state and head position (black). The green and pink wires supply inputs from earlier epochs as specified by the computation graph. A single-tape Turing machine with head pattern π=(R,S,L)\pi=(R,S,L) and four epochs.

Sharing variables in this way allows us to enforce consistency between epochs. Notice also that each variable is shared among at most 2 circuits. This means the density of our circuit-CSP is at most 2. See Figure 4 for an illustration.

How to construct a 3-CNF formula from a circuit-CSP. We can convert each constraint circuit CiC_i in the previous step into a 3-CNF formula over O(blog⁡b)O(b\log b) variables using a result of [21] (Lemma 3.4). There are O(t/b)O(t/b) different constraint circuits, so taking the AND of all of them results in a 3-CNF over O(tlog⁡b)O(t\log b) variables.

Summary. You can view our argument as consisting of the same two steps as Cook–Levin just applied to segments of the Turing machine execution instead of the whole thing. We summarize the argument here:

  1. Divide the Turing machine’s runtime into epochs, applying [HPV77] to show it can be made block-respecting. Each pattern π\pi for how the heads move between blocks at the boundaries of each epoch will give rise to a different circuit-CSP.

  2. For a fixed pattern π\pi, use [17] to convert each epoch into a constraint circuit. Taking the AND of all these circuits results in a circuit-CSP.

  3. Use [21] to convert each circuit-CSP into a 3-CNF.

Lemma 2.1 follows from just steps 1 and 2. Step 3 is only needed for obtaining Lemma 2.2.

Preliminaries

Notation. We write [n]={1,…,n}[n]=\{1,\ldots,n\} and [0,n]={0,…,n}[0,n]=\{0,\ldots,n\}. All functions f:N→Nf:\mathbb{N}\to\mathbb{N} are assumed to be growth functions (i.e. time-constructible and non-decreasing) unless stated otherwise. All log’s are base 2.

Block-respecting Turing machines. The proof of Theorem 2 uses the notion of block-respecting Turing machines from Hopcroft, Paul, and Valiant [HPV77]. Roughly speaking, a bb-block-respecting Turing machine has each tape divided into blocks of size bb, and tape heads are only allowed to cross from one block to another at time steps that are integer multiples of bb (so at most one block crossing every bb steps). Intuitively, assuming a block-respecting Turing machine helps our proof since we can then think of its computation on a given block as a constraint of arity O(b)O(b) over variables representing the content of the bb tape-cells of the block. Concretely, we use the following slight modification of [HPV77]:

Lemma 3.1 (NTMs can be made block-respecting [HPV77]). Let MM be a dd-tape nondeterministic Turing machine running in time t(n)t(n). Then, for every function b:N→Nb:\mathbb{N}\to\mathbb{N} with b(n)≤t(n)b(n)\le t(n), there exists a nondeterministic Turing machine M′M' that accepts the same language as MM. Furthermore, M′M' uses O(d)O(d) tapes, runs in time O(t(n))O(t(n)), and is b(n)b(n)-block-respecting when receiving an input of length nn.

Converting Turing machines into circuits. We will also use a form of Pippenger–Fischer’s result on compiling deterministic Turing machines into circuits [17]. To state it we will need some notation. Given a dd-tape deterministic Turing machine MM over an alphabet Γ\Gamma, and set of states QQ, we define its set of block configurations as CM,b:=(Γb)d×Q×[0,b+1]dC_{M,b}:=(\Gamma^b)^d\times Q\times[0,b+1]^d for b≥1b\ge1, representing the content of a size-bb block on each of the dd tapes, together with a state, and an offset describing the starting position of each head within the block (the positions 0 and b+1b+1 indicate that the head is just to the left or just to the right of the block, respectively). Then, a block computation is a function

BM,b:CM,b→CM,b∪{⊥}\mathcal{B}_{M,b}: \mathcal{C}_{M,b} \to\mathcal{C}_{M,b} \cup\{\perp\}

which maps a block configuration to the one resulting after bb steps of computation by MM if all heads stayed within their block in the first b−1b-1 steps of computation, and to ⊥\perp if some head exited its block in the first b−1b-1 steps or began in position 0 or b+1b+1. Informally, the result of Pippenger–Fischer says BM,b\mathcal{B}_{M,b}, interpreted as a boolean function, can be computed by a circuit with O(blog⁡b)O(b\log b) gates. More formally, let LM,b:=db⌈log⁡∣Γ∣⌉+⌈log⁡∣Q∣⌉+d⌈log⁡(b+2)⌉L_{M,b} := db\lceil\log|\Gamma|\rceil+ \lceil\log|Q|\rceil+ d\lceil\log(b+2)\rceil be the number of bits required to describe a block configuration, and let enc⁡M,b:CM,b→{0,1}LM,b\operatorname{enc}_{M,b}: \mathcal{C}_{M,b} \to\{0,1\}^{L_{M,b}} be a function that encodes block configurations in binary in the natural way. Then, we can state Pippenger–Fischer’s result as follows.

Lemma 3.2 (Converting TMs into Circuits [17]). Let MM be a dd-tape deterministic Turing machine, and let b≥1b \ge1 be an integer. Let fM,b:{0,1}2LM,b→{0,1}f_{M,b}: \{0,1\}^{2L_{M,b}} \to\{0,1\} be such that fM,b(x,y)=1f_{M,b}(x,y)=1 for x,y∈{0,1}LM,bx,y \in\{0,1\}^{L_{M,b}} if and only if xx and yy are encodings of block configurations β1\beta_1 and β2\beta_2, respectively, and BM,b(β1)=β2\mathcal{B}_{M,b}(\beta_1)=\beta_2. Then a circuit for fM,bf_{M,b} with O(blog⁡b)O(b\log b) gates can be computed deterministically in time poly⁡(b)\operatorname{poly}(b).

There is a natural analogue of the above for nondeterministic Turing machines. We assume that a nondeterministic machine MM makes one binary choice per step, or equivalently, it can read the iith bit of a witness ww during the iith step. For a block configuration β∈CM,b\beta\in\mathcal{C}_{M,b} and a witness w∈{0,1}bw \in\{0,1\}^{b}, let BM,b(β,w)∈CM,b∪{⊥}\mathcal{B}_{M,b}(\beta,w) \in\mathcal{C}_{M,b} \cup\{\perp\} be defined exactly as BM,b(β)\mathcal{B}_{M,b}(\beta) in the deterministic case except now it additionally takes in ww as input. This gives a nondeterministic block computation

BM,b:CM,b×{0,1}b→CM,b∪{⊥}.\mathcal{B}_{M,b}: \mathcal{C}_{M,b} \times\{0,1\}^{b} \to\mathcal{C}_{M,b} \cup\{\perp\}.

Lemma 3.3 (Converting NTMs into circuits [17]). Let MM be a dd-tape nondeterministic Turing machine, and let b≥1b \ge1 be an integer. Let gM,b:{0,1}2LM,b+b→{0,1}g_{M,b}: \{0,1\}^{2L_{M,b}+b} \to\{0,1\} be such that gM,b(x,w,y)=1g_{M,b}(x,w,y)=1 for x,y∈{0,1}LM,bx,y \in\{0,1\}^{L_{M,b}} and w∈{0,1}bw \in\{0,1\}^{b} if and only if xx and yy are encodings of block configurations β1\beta_1 and β2\beta_2, respectively, and BM,b(β1,w)=β2\mathcal{B}_{M,b}(\beta_1,w)=\beta_2. Then a circuit for gM,bg_{M,b} with O(blog⁡b)O(b\log b) gates can be computed deterministically in time poly⁡(b)\operatorname{poly}(b).

Converting circuits into 3-CNFs. We will also need a way of converting circuits into 3-CNF formulas. This result was first discovered by [21], although it’s been rediscovered in different forms many times since.

Lemma 3.4 (Converting circuits into CNFs [21]). Let C(x)C(x) be a circuit over nn variables with gg gates of fan-in at most 2. There is a 3-CNF formula φ(x,y)\varphi(x,y) over n+gn+g variables and O(g)O(g) clauses such that for every assignment to the variables xx we have C(x)=1C(x)=1 if and only if ∃y φ(x,y)=1\exists y\ \varphi(x,y)=1. Furthermore φ\varphi can be computed in time poly⁡(n+g)\operatorname{poly}(n+g).

Proofs of thm:lossless-general and thm:lossy-general

Proof of Theorem 2 assuming Lemma 2.1. Let MM be a nondeterministic Turing machine with running time t(n)t(n), and k(n)k(n) be the arity function in the hypothesis. Given an input xx of length nn, we will deterministically decide whether MM accepts xx as follows. First, we use the algorithm from Lemma 2.1 on MM, xx, and b(n):=⌊c⋅k(t(n))⌋b(n):=\lfloor c\cdot k(t(n))\rfloor for some sufficiently small 0<c<10<c<1, thus obtaining a collection of circuit-CSPs Φ1…Φm\Phi_1\ldots\Phi_m, each with NN variables, where t(n)≤N≤Ct(n)t(n)\le N\le Ct(n) for some fixed C>1C>1. This step takes time m⋅poly⁡(t(n))m\cdot\operatorname{poly}(t(n)).2 The assumption of Theorem 2 tells us that each of these circuit-CSPs Φℓ\Phi_\ell with O(t(n))O(t(n)) variables, arity O(b(n))≤k(t(n))≤k(N)O(b(n)) \leq k(t(n)) \leq k(N), and density at most 2 can be solved in time 2O(t(n)/s(t(n)))⋅poly⁡(∣Φℓ∣)=2O(t(n)/s(t(n)))2^{O(t(n)/s(t(n)))} \cdot\operatorname{poly}(|\Phi_\ell|) = 2^{O(t(n)/s(t(n)))}. There are mm such Circuit-CSPs, so solving all of them takes time m⋅2O(t(n)/s(t(n)))m \cdot2^{O(t(n)/s(t(n)))}. We output that MM accepts xx iff any Φℓ\Phi_\ell is satisfiable. Condition 1 of Lemma 2.1 ensures the correctness of this algorithm. Plugging in m=2O(t(n)/b(n))m = 2^{O(t(n)/b(n))}, the total runtime is

2O(t(n)/b(n))(poly⁡(t(n))+2O(t(n)/s(t(n))))=2O(t(n)/b(n))⋅2O(t(n)/s(t(n)))2^{O(t(n)/b(n))}\left(\operatorname{poly}(t(n)) + 2^{O(t(n)/s(t(n)))}\right) = 2^{O(t(n)/b(n))} \cdot2^{O(t(n)/s(t(n)))}

since s(t(n))≤t(n)/log⁡t(n)s(t(n)) \leq t(n) / \log t(n) by hypothesis.

Proof of Theorem 3 assuming Lemma 2.2. The proof is nearly identical to that of Theorem 2. Given a nondeterministic TM MM running in time t:=t(n)t := t(n) and an input xx of size nn, we compute M(x)M(x) as follows. First, we run the reduction in Lemma 2.2 to obtain a collection of 3-CNF formulas φ1…φm\varphi_1 \ldots\varphi_m. This step takes time m⋅poly⁡(t(n))m \cdot\operatorname{poly}(t(n)). Then, since each φℓ\varphi_\ell has O(tlog⁡b)O(t \log b) variables and clauses, the assumption of Theorem 3 tells us that each 3-CNF can be solved in time 2O(tlog⁡b/s(tlog⁡b))2^{O(t \log b/s(t \log b))}, so solving all of them takes time m⋅2O(tlog⁡b/s(tlog⁡b))m \cdot2^{O(t \log b/s(t \log b))}. We accept iff any φℓ\varphi_\ell is satisfiable. Plugging in m=2O(t/b)m = 2^{O(t/b)} makes the total runtime 2O(t/b)⋅2O(tlog⁡b/s(tlog⁡b))2^{O(t/b)} \cdot2^{O(t \log b/s(t \log b))}. Taking b:=s(t(n))b := s(t(n)) makes this

2O(t/s(t))2O(tlog⁡s(t)/s(tlog⁡s(t)))=2O(tlog⁡s(t)/s(tlog⁡s(t)))2^{O(t/s(t))}2^{O(t \log s(t)/s(t \log s(t)))} = 2^{O(t \log s(t)/s(t \log s(t)))}

since ss is non-decreasing.

Proof of lem:cl-for-CSP and cor:cl

Proof of Lemma 2.1. Fix MM, tt, and bb. First, by Lemma 3.1, there is a bb-block-respecting Turing machine M′M' accepting the same language as MM, with D=O(1)D = O(1) tapes. Fix an input xx of length nn, and let T:=c⋅t(n)T := c \cdot t(n) for some c>0c > 0 be an upper bound on the runtime of M′M' on xx, which we can easily compute since tt is time-constructible. Then, let M^\widehat{M} be a copy of M′M' in which accepting and rejecting states are made “absorbing” (i.e., once reached, the machine remains in the same state, preserving the content of the tapes). This way, M^\widehat{M} runs forever on xx, but its state is accepting at time b⌈T/b⌉b\lceil T/b\rceil if and only if MM accepts on xx.3[eq] $

For ease of notation, let r:=⌈T/b⌉r := \lceil T/b\rceil, so we wish to represent the computation of M^\widehat{M} on xx for rr epochs of bb steps each. We enumerate all patterns (see Section 2.1) π∈{L,S,R}(r−1)×D\pi\in\{L,S,R\}^{(r-1)\times D}, and since there are 3(r−1)D=2O(t/b)3^{(r-1)D} = 2^{O(t/b)} of them, it suffices to show how to construct a given circuit-CSP Φπ\Phi_\pi corresponding to whether M^\widehat{M} is in an accepting state at time rbrb having followed pattern π\pi.

Let πi,j∈{L,S,R}\pi_{i,j} \in\{L,S,R\} denote the block movement at the end of epoch ii for tape jj, and let ai,ja_{i,j} be the index of the block of the head of tape jj during epoch ii. We thus have a1,j=0a_{1,j}=0 for j∈[D]j \in[D], and ai+1,j=ai,j+δ(πi,j)a_{i+1,j}=a_{i,j}+\delta(\pi_{i,j}), where δ\delta maps L→−1,S→0,R→1L \to-1,S \to0,R \to1.

For each epoch ii, let Ξi\Xi_i be the circuit obtained from Lemma 3.3 computing gM^,b(x(i),w(i),y(i))g_{\widehat{M},b}(x^{(i)},w^{(i)},y^{(i)}). Our goal is to combine the different Ξi\Xi_i in order to obtain Φπ\Phi_\pi, and the main challenge is the interaction between their variables (e.g., the final content of tape jj on a given block after a given epoch needs to match the initial content of a future epoch working on the same block). In order to do this formally, we will use a notion of formal substitution. First, note that we are free to “hardwire” constant values into circuits by using constant gates labeled with 0 or 1; these can be obtained trivially as (x∧¬x)(x \land\lnot x) and (x∨¬x)(x \lor\lnot x) for any variable xx. Now, we think of circuits as directed graphs whose vertices are labeled either as variables or gates. Under this perspective, we start with a disconnected graph where each component is one of the Ξi\Xi_i, and we will then merge them into a single circuit. Concretely, let us define a formal substitution as follows: let CC be a boolean circuit, whose set of input variables is VV; then, a formal substitution is simply a function σ:V→W∪{0,1}\sigma: V \to W \cup\{0,1\} where WW is some set of boolean variables. In turn, C[σ]C[\sigma] is the circuit obtained by simultaneously replacing each input variable v∈Vv \in V by σ(v)\sigma(v). In terms of the graph, Figure 5 illustrates the effect of formal substitution.

Formal substitution on circuit graphs

Figure 5. Formal substitution on circuit graphs. The substitution σ(x)=b\sigma(x)=b and σ(a)=1\sigma(a)=1, fixing b,cb,c.

Now, let us look more closely at the variables involved. Let Γ\Gamma and QQ be the alphabet and states of M^\hat{M}, respectively. We can write the input and output configurations x(i)x^{(i)} and y(i)y^{(i)} as

x(i)=(ui,1,…,ui,D,qi,hi,1,…,hi,D)andy(i)=(ui,1′,…,ui,D′,qi′,hi,1′,…,hi,D′),x^{(i)}=\left(u_{i,1},\ldots,u_{i,D},q_i,h_{i,1},\ldots,h_{i,D}\right)\quad\text{and}\quad y^{(i)}=\left(u'_{i,1},\ldots,u'_{i,D},q'_i,h'_{i,1},\ldots,h'_{i,D}\right),

where:

  • ui,ju_{i,j} consists of b⌈log⁡∣Γ∣⌉b\lceil\log|\Gamma|\rceil bits representing the content of block ai,ja_{i,j} before epoch ii, and ui,j′u'_{i,j} is analogous but for after epoch ii.

  • qiq_i consists of ⌈log⁡∣Q∣⌉\lceil\log|Q|\rceil bits representing the state before epoch ii, and qi′q'_i the state after epoch ii; and

  • hi,jh_{i,j} consists of ⌈log⁡(b+2)⌉\lceil\log(b+2)\rceil bits representing the initial head offset relative to block ai,ja_{i,j}, and hi,j′h'_{i,j} the final head offset.

Next, we will define a formal substitution σ⋆\sigma^\star that intuitively represents giving the correct input information to Ξi\Xi_i based on the results of previous epochs. It will be convenient to define two pieces of notation. First, for every epoch ii and tape jj, let prev⁡(i,j)\operatorname{prev}(i,j) be the last epoch before ii that visited block ai,ja_{i,j} (or 00 in case that block had not been previously visited). More formally,

prev⁡(i,j):=max⁡({0}∪{h∈[i−1]∣ah,j=ai,j}).\operatorname{prev}(i,j):=\max\left(\{0\}\cup\{h\in[i-1]\mid a_{h,j}=a_{i,j}\}\right).

Second, for each block index ai,ja_{i,j}, let Ij(ai,j)∈{0,1}⌈log⁡∣Γ∣⌉bI_j(a_{i,j})\in\{0,1\}^{\lceil\log|\Gamma|\rceil b} be the constant binary encoding of the initial content of that block on tape jj (e.g., on every tape except the input tape, it will simply consist of the constant encoding of the blank symbol). With this notation, we set

σ⋆(ui,j)={Ij(ai,j)if prev⁡(i,j)=0,uprev⁡(i,j),j′otherwise.\sigma^\star(u_{i,j})= \begin{cases} I_j(a_{i,j}) & \text{if }\operatorname{prev}(i,j)=0,\\ u'_{\operatorname{prev}(i,j),j} & \text{otherwise.} \end{cases}

That is, the initial content of a block comes either from the original state of the tapes, or from the output of the last time the machine touched that block. Similarly, we set

σ⋆(qi):={⌊qinit⌋if i=1,qi−1′otherwise,\sigma^\star(q_i):= \begin{cases} \lfloor q_{\mathrm{init}}\rfloor& \text{if }i=1,\\ q'_{i-1} & \text{otherwise,} \end{cases}

where ⌊qinit⌋\lfloor q_{\mathrm{init}}\rfloor is the constant binary encoding for the initial state of M^\hat{M}. So this substitution represents that the state at the beginning of an epoch is either the initial state or the one resulting from the previous epoch.

For the offsets of the heads, the substitution is a bit more cumbersome. For an integer v∈[0,b+1]v\in[0,b+1], let ⌊v⌋\lfloor v\rfloor denote its binary encoding on ⌈log⁡(b+2)⌉\lceil\log(b+2)\rceil bits. Then, for the first epoch, we have σ⋆(h1,j)=⌊1⌋\sigma^\star(h_{1,j})=\lfloor1\rfloor, since each head starts at the beginning of its corresponding block. For the epochs after the first, we have three cases:

Proof of fact:csp

  1. If πi,j=S\pi_{i,j}=S, then σ⋆(hi+1,j)=hi,j′\sigma^{\star}(h_{i+1,j})=h'_{i,j}.

  2. If πi,j=L\pi_{i,j}=L, then σ⋆(hi+1,j)=⌊b⌋\sigma^{\star}(h_{i+1,j})=\lfloor b\rfloor, and

  3. If πi,j=R\pi_{i,j}=R, then σ⋆(hi+1,j)=⌊1⌋\sigma^{\star}(h_{i+1,j})=\lfloor1\rfloor.

Furthermore, we need some consistency checks for the movement of the heads, defined as follows. If πi,j=S\pi_{i,j}=S, then the check Ei,jE_{i,j} is a circuit ensuring that hi,j′h'_{i,j} is indeed a number between 1 and bb. If πi,j=L\pi_{i,j}=L, then Ei,jE_{i,j} ensures that hi,j′=⌊0⌋h'_{i,j}=\lfloor0\rfloor, and if πi,j=R\pi_{i,j}=R, then Ei,jE_{i,j} ensures that hi,j′=⌊b+1⌋h'_{i,j}=\lfloor b+1\rfloor. Note that each Ei,jE_{i,j} can be implemented with O(log⁡b)O(\log b) gates.

Our constraint for every epoch i<ri<r is

Ci:=Ξi[σ⋆]∧⋀j=1DEi,j.C_i:=\Xi_i[\sigma^\star]\land\bigwedge_{j=1}^{D}E_{i,j}.

For the final epoch i=ri=r, let Ωi\Omega_i be a circuit whose input variables are qi′q'_i and that returns 1 if qi′q'_i equals the binary encoding of any of the accepting states from the set F⊆QF\subseteq Q. Then,

Ci:=Ξi[σ⋆]∧Ωi,C_i:=\Xi_i[\sigma^\star]\land\Omega_i,

and note that Ωi\Omega_i uses only a constant number of gates, since ∣Q∣=O(1)|Q|=O(1). Finally, we simply output

Φπ:=⋀i=1rCi.\Phi_\pi:=\bigwedge_{i=1}^{r}C_i.

The fact that MM accepts input xx if and only if some Φℓ\Phi_\ell is satisfiable holds essentially by construction. Each CiC_i has O(b)O(b) variables, and since there are r=O(t/b)r=O(t/b) of them, the total number of variables is O(t)O(t). The fact that each CiC_i has O(blog⁡b)O(b\log b) gates follows from the fact that each Ξi\Xi_i has O(blog⁡b)O(b\log b) gates per Lemma 3.3, and the Ei,jE_{i,j} have O(log⁡b)O(\log b) gates each. Moreover, each variable appears in at most two constraints: state variables qi/qi′q_i/q'_i and head offset variables are shared between consecutive epochs, and the variables representing tape contents at the end of an epoch can only be shared with the next epoch touching the corresponding block. Thus, the density is at most 2, and we conclude the proof. □

Proof of Lemma 2.2. By Lemma 2.1, we obtain circuit-CSPs Φ1,…,Φm\Phi_1,\ldots,\Phi_m such that MM accepts xx if and only if one of them is satisfiable. For each such Φπ\Phi_\pi, we iterate over its constraints: (S1,C1),…,(Sr,Cr)(S_1,C_1),\ldots,(S_r,C_r). Each CiC_i has O(b)O(b) variables and O(blog⁡b)O(b\log b) gates, so by Lemma 3.4, we can convert it into a 3-CNF formula ψi(Si,z(i))\psi_i(S_i,z^{(i)}), where the additional variables z(i)z^{(i)} are disjoint across different ii. Then, let φπ:=⋀i=1rψi(Si,z(i))\varphi_\pi:=\bigwedge_{i=1}^{r}\psi_i(S_i,z^{(i)}), and note it has O(t/b)⋅O(blog⁡b)=O(tlog⁡b)O(t/b)\cdot O(b\log b)=O(t\log b) variables and clauses. For correctness, assume a variable assignment aa satisfies Φπ\Phi_\pi, then Ci(a∣Si)=1C_i(a|_{S_i})=1 for every ii, so each ψi\psi_i has a satisfying extension z(i)z^{(i)}; since the z(i)z^{(i)} are disjoint, these combine into a satisfying assignment of φπ\varphi_\pi. Conversely, if (a,z(1),z(2),…)(a,z^{(1)},z^{(2)},\ldots) satisfies φπ\varphi_\pi, then each ψi\psi_i is satisfied, so Ci(a∣Si)=1C_i(a|_{S_i})=1 for all ii and aa satisfies Φπ\Phi_\pi. □

Proof of Lemma 1.3

We prove Lemma 1.3 assuming [16]’s Theorem D.1. To state [16]’s result, we need the following definition:

Definition 6.1 (Boolean tensor network). Let RR be a commutative ring. A Boolean tensor network over RR consists of a finite bipartite graph G=(V,E)G=(V,E), in which parallel edges are allowed, together with a function

Tv:{0,1}δ(v)→RT_v:\{0,1\}^{\delta(v)}\to R

for each vertex vv, where δ(v)\delta(v) is the set of edges incident to vv. Think of each edge ee as a Boolean variable xex_e, and of TvT_v as a weight that depends only on the variables of the edges at vv. The contraction of the network is the sum, over all ways of assigning a bit to every edge, of the product of the weights of all vertices:

Z=∑x∈{0,1}E∏v∈VTv(x∣δ(v)),Z=\sum_{x\in\{0,1\}^{E}}\prod_{v\in V}T_v(x|_{\delta(v)}),

where x∣δ(v)x|_{\delta(v)} is the restriction of xx to the edges at vv. The degree of the network is the maximum degree of GG.

We can now state a slightly simplified version of [16]’s Theorem D.1:

Theorem 4 ([16 Theorem D.1]). Let σ≥2\sigma\ge2, and let LL be the description length of a Boolean tensor network with O(σ)O(\sigma) edges, at most poly⁡(σ)\operatorname{poly}(\sigma) vertices and maximum degree at most ⌈σ9/10⌉\lceil\sigma^{9/10}\rceil. Let every TvT_v map to the ring R=Z/2rZR = \mathbb{Z}/2^r\mathbb{Z} for some 1≤r≤O(σ)1 \le r \le O(\sigma). Suppose each value of TvT_v can be computed from the description in time poly⁡(σ+L)⋅2O(σ9/10)\operatorname{poly}(\sigma+ L) \cdot2^{O(\sigma^{9/10})} and space poly⁡(σ+L)\operatorname{poly}(\sigma+ L). Then the contraction can be computed deterministically in time poly⁡(σ+L)⋅2O(σ/log⁡σ)\operatorname{poly}(\sigma+ L) \cdot2^{O(\sigma/\sqrt{\log\sigma})}.

We are now ready to prove that Lemma 1.3 follows from Theorem 4:

Proof of Lemma 1.3. Let Φ\Phi be a circuit-CSP with nn variables, arity at most n9/10n^{9/10} and constant density. We build a tensor network whose contraction is #Φ\#\Phi and then apply Theorem 4 with σ=n\sigma= n. We can assume without loss of generality that Φ\Phi’s constraint circuits all have at least one input variable; otherwise it is a constant, so we evaluate all such circuits, output 0 if any of them outputs 0, and delete them otherwise. Then, since the density is constant, we have ∑j∣Sj∣=O(n)\sum_j |S_j| = O(n), which implies that there are at most O(n)O(n) constraint circuits CjC_j.

From the circuit-CSP Φ\Phi, we will build a bipartite graph with vertices on the left side corresponding to constraints and vertices on the right side corresponding to variables. More formally, for each constraint (Sj,Cj)(S_j,C_j) of Φ\Phi we add a vertex vjv_j to our graph, and for each variable xix_i of Φ\Phi, we add a vertex uiu_i. We add an edge between vjv_j and uiu_i iff xi∈Sjx_i \in S_j. Set

Tvj(y)=Cj(y),Tui(y)={1if all bits of y are equal,0otherwise.T_{v_j}(y) = C_j(y), \qquad T_{u_i}(y) = \begin{cases} 1 & \text{if all bits of } y \text{ are equal},\\ 0 & \text{otherwise.} \end{cases}

We call each vertex uiu_i with the tensor function TuiT_{u_i} defined above an equality vertex, since it forces all assignments to its edges to be equal. This choice of TuiT_{u_i} means that whenever a term in the contraction is nonzero, an assignment to the edges corresponds exactly to an assignment of the original variables xix_i (since we do not allow xix_i to take on multiple values). Our choice of TvjT_{v_j} then further ensures that all circuits must evaluate to 1 with this assignment. Thus, summing over all these assignments, the contraction ZZ equals #Φ\#\Phi, the number of satisfying assignments to $\Phi. (A variable that occurs in no constraint gives a vertex uiu_i with no edges, which contributes a factor 1 instead of 2; we multiply ZZ by 2 for each such variable.)$

There is one issue with this construction: our assumption that the density is constant only bounds the average degree of the uiu_i’s, but to apply Theorem 4, we need a bound on the maximum degree of each vertex. We fix this by adding extra vertices. In the case that there is a uiu_i with degree di>n9/10d_i > n^{9/10}, we replace uiu_i with did_i vertices ui(1),…,ui(di)u_i^{(1)}, \ldots, u_i^{(d_i)} and place an edge between ui(ℓ)u_i^{(\ell)} and uiu_i’s ℓ\ellth neighbor for all ℓ∈[di]\ell\in[d_i]. We then add O(di)O(d_i) vertices to the other side of the bipartite graph and connect each of these vertices to two of the ui(ℓ)u_i^{(\ell)}’s such that there is a path in the graph between all the ui(ℓ)u_i^{(\ell)}’s. Then, if we make all these new vertices equality vertices, and use that equality is transitive, we can ensure that the assignments of the edges to all the ui(ℓ)u_i^{(\ell)}’s must be equal in order for that term in the contraction to be nonzero.

This fixes the problem at the cost of O(di)O(d_i) additional vertices and edges. Since the density is constant, we have ∑idi=∑j∣Sj∣=O(n)\sum_i d_i = \sum_j |S_j| = O(n). Therefore, in total, our graph will have O(n)O(n) vertices and edges. Each vjv_j has degree at most the arity n9/10n^{9/10}, each uiu_i that was not split has degree at most n9/10n^{9/10}, and each new vertex has constant degree. Each equality vertex is trivial to compute, and each TvjT_{v_j} computes CjC_j, which takes poly⁡(∣Φ∣)\operatorname{poly}(|\Phi|) time. Furthermore, the network is described by the graph and the circuits CjC_j, meaning L=poly⁡(∣Φ∣)L = \operatorname{poly}(|\Phi|). Finally, #Φ≤2n\#\Phi\le2^n, so computing the contraction modulo 2n+12^{n+1} gives #Φ\#\Phi exactly; we take r=n+1r = n + 1. Theorem 4 therefore computes #Φ\#\Phi in time 2O(n/log⁡n)poly⁡(∣Φ∣)2^{O(n/\sqrt{\log n})}\operatorname{poly}(|\Phi|). ∎

AI Disclosure

OpenAI’s Astra and Anthropic’s Opus 5.5 and Fable 5.1 were used throughout our process.

Acknowledgments

Bernardo is supported by NSF grant DMS-2434625. Carmen is supported by NSF awards 1942123, 2211237, 2224246, a Sloan Research Fellowship, a Google Research Scholar Award, Omer Reingold’s Simons Foundation Investigator Award, Stanford Computer Science Distinguished Fellowship, an NSF GRFP, and a Jump Trading PhD Fellowship. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not reflect the views of Jump Trading.

References

References

  1. [1]Charles H. Bennett and John Gill. Relative to a random oracle A, P^A ≠ NP^A ≠ co-NP^A with probability 1. SIAM Journal on Computing, 10(1):96–113, 1981. 1.1DOI
  2. [2]Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P vs. NP question. SIAM Journal on Computing, 4(4):431–442, 1975. 1.1DOI
  3. [3]Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. J. Comput. Syst. Sci., 49(1):24–39, 1994. doi:10.1016/S0022-0000(05)80084-4. 1.1DOI
  4. [5]Stephen A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. J. ACM, 18(1):4–18, 1971. doi:10.1145/321623.321625. 1.1DOI
  5. [6]Stephen A. Cook. Short propositional formulas represent nondeterministic computations. Information Processing Letters, 26(5):269–270, 1988. 1DOI
  6. [7]David Doty. An Oracle Strongly Separating Deterministic Time from Nondeterministic Time, via Kolmogorov Complexity, April 2010. arXiv:1004.3993 [cs.CC]. URL: http://arxiv.org/abs/1004.3993, doi:10.48550/arXiv.1004.3993. 1.1
  7. [9]Juris Hartmanis and Richard Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285–306, 1965. 1.1DOI
  8. [10]John E. Hopcroft and Jeffrey D. Ullman. Relations Between Time and Tape Complexities. J. ACM, 15(3):414–427, July 1968. URL: https://dl.acm.org/doi/10.1145/321466.321474, doi:10.1145/321466.321474. 1.1DOI
  9. [11]Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367–375, 2001. 1DOI
  10. [12]Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.DOI
  11. [13]Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, and Farbod Shokrieh. Improved Simulation of Nondeterministic Turing Machines. Theoretical Computer Science, 417:66–73, 2012. doi:10.1016/j.tcs.2011.05.018.DOI
  12. [14]Richard J. Lipton. Simulation of nondeterministic machines. Gödel’s Lost Letter and P=NP (blog), May 2009. Accessed: 2026-11-03. URL: https://rjlipton.com/2009/05/11/simulation-of-nondeterministic-machines/.
  13. [15]Shlomo Moran. Some results on relativized deterministic and nondeterministic time hierarchies. Journal of Computer and System Sciences, 22(1):1–8, 1981.DOI
  14. [16]OpenAI. The exponential time hypothesis is false. OpenAI Math Release preprint, October 2026. Revised 25 October 2026. URL: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.
  15. [17]Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361–381, 1979. doi:10.1145/322123.322138.DOI
  16. [18]Wolfgang J. Paul, Nicholas Pippenger, Endre Szemeredi, and William T. Trotter. On determinism versus non-determinism and related problems. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 429–438, November 1983. ISSN: 0272-5428. URL: https://ieeexplore.ieee.org/document/4568107, doi:10.1109/SFCS.1983.39.DOI
  17. [19]Rahul Santhanam. On separators, segregators and time versus space. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18–21, 2001, pages 286–294. IEEE Computer Society, 2001. doi:10.1109/CCC.2001.933895.DOI
  18. [20]Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4(2):177–192, 1970. doi:10.1016/S0022-0000(70)80006-X.DOI
  19. [21]G. S. Tseitin. On the complexity of derivation in propositional calculus. In A. O. Slisenko, editor, Studies in Constructive Mathematics and Mathematical Logic, volume 8 of Seminars in Mathematics, pages 234–259. Steklov Mathematical Institute, Leningrad, Russia, 1968. English translation: Consultants Bureau, New York, 1970, pp. 115–125.

Paper details

vlnc:W_tv8pqvec
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI’s Astra, Opus 5.5, Claude Fable 5.1 (bare)

View statement
Looking for related papers…
Contents