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 - presented by OpenAI and Anthropic imply , and that a stronger consequence of their proof yields More generally, we show that any subexponential time algorithm for solving circuit-CSPs transfers to a deterministic simulation of 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 variables and clauses can be solved in time .
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 based on Lemma 1.1 fails: the most efficient known version of Cook–Levin reduces acceptance of a nondeterministic Turing machine running in time to the satisfiability of a 3-CNF formula over variables and clauses [6]. Plugging this into Lemma 1.1 yields , which is worse than the trivial upper bound of . 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 such that , we have
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).

Figure 1. A circuit-CSP over variables and constraints of arity 5 and density .
Definition 1.2 (Circuit-CSP). A circuit-CSP consists of Boolean variables together with constraints , where each is a tuple of distinct variables from and each is a Boolean circuit on inputs. An assignment to satisfies if for all . The arity of is , and its density is .
For instance, if all are disjunctions of literals (variables or negations thereof), then this definition corresponds to a -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 , , and be growth functions such that and . Suppose that circuit-CSP over variables with arity at most and density at most can be solved in time , then
Notice that as long as , 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 variables with arity at most and constant density can be solved in time .
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 and be growth functions. Suppose that 3-SAT over variables and clauses can be solved in time , then
This conclusion is weaker than Theorem 2 since it has an extra factor of in the exponent. Setting and applying Lemma 1.1 gives the following corollary, which is a weaker version of Theorem 1: .
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 , which was then improved to by Santhanam [19]. For upper bounds, the question we study here, even less was known. Lipton conjectured that for any ,
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 upper bound with an improvement in the constant . 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 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:
where the subscript 1 indicates single-tape machines. The first inclusion was proven by Hopcroft and Ullman [10] (and strictly speaking requires ), 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 be a nondeterministic multitape Turing machine that runs in time , and let be such that . Then, there is a deterministic algorithm that takes an input to of length and returns circuit-CSPs for in time , such that
accepts input if and only if some is satisfiable, and
each has variables, arity , density at most 2, and constraint circuits each of size .
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 be a nondeterministic multitape Turing machine that runs in time , let be a length input to , and let . There is a deterministic algorithm that maps to 3-CNF formulas that runs in time for such that
accepts input if and only if some is satisfiable, and
each has variables and clauses.
If we set in the above, an inspection of the proof shows that this results in a single 3-CNF formula over variables. Additionally, the runtime can be made 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.
Table 1. Three encodings of a nondeterministic time- Turing machine. The machine accepts iff some output is satisfiable. Variable and constraint bounds are per output. At , 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 is a sub-exponential reduction family (SERF) from the language , 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:
Use a result of [17] to convert the nondeterministic TM into a size circuit , and then,
use a result of [21] to convert this circuit into a 3-CNF over variables.
The bound on the number of variables results from encoding the entire Turing machine as a single large circuit . Suppose that instead, we were somehow able to break the Turing machine up into size segments and encode each segment individually. This would result in circuits each of size . Then, when we reach step 2, we would have a 3-CNF over different variables. This is the entire idea of the proof. It turns out that when we break the Turing machine up into size segments, there are ways to do so. This is why we end up with different 3-CNFs in the statement of Lemma 2.2, and also why we cannot afford to make arbitrarily small.
How to segment an NTM. Our technique is similar to that of [13 Section 5]. We split the runtime of a -time Turing machine into epochs, each of length . Additionally, we split each of the Turing machine’s tapes into contiguous blocks, each consisting of cells. Then, a result of [HPV77] (restated in Lemma 3.1) allows us to assume without loss of generality that 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 and a fixed tape , that tape head will stay within a single block (see Figure 2). We let be the pattern that ’s heads take (see Figure 3). Specifically,

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

Figure 3. The same 3-tape Turing machine at the start of epochs and ; the block that each head stays in during that epoch is shaded. In this example, the pattern for epoch is : 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.
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 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 . Using a result of [17] (restated in Lemma 3.3), we construct, for each epoch , a constraint circuit of size that ensures the validity of the computation of within that epoch. The final circuit-CSP comes from taking the AND of all the ’s.
The variables of circuit fall into three groups:
describes the block configuration at the start of epoch (the block contents, head positions, and state),
describes the block configuration at the end of epoch , and
are the nondeterministic choices made by during epoch .
Then, checks whether is an honest description of the configuration after running for steps from configuration with nondeterministic choices . If it’s the last epoch, we of course additionally check whether accepts.
The variables and are shared among circuits. Each block’s content in is the corresponding part of for the last epoch that worked on that block, as determined by , and the state and head positions come from . 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 are identified with the inputs for block 0 in , and similarly, the output variables corresponding to block 1 in are identified with the inputs for block 1 in .

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 . The variables below encode epoch ’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 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 in the previous step into a 3-CNF formula over variables using a result of [21] (Lemma 3.4). There are different constraint circuits, so taking the AND of all of them results in a 3-CNF over 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:
Divide the Turing machine’s runtime into epochs, applying [HPV77] to show it can be made block-respecting. Each pattern for how the heads move between blocks at the boundaries of each epoch will give rise to a different circuit-CSP.
For a fixed pattern , use [17] to convert each epoch into a constraint circuit. Taking the AND of all these circuits results in a circuit-CSP.
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 and . All functions 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 -block-respecting Turing machine has each tape divided into blocks of size , and tape heads are only allowed to cross from one block to another at time steps that are integer multiples of (so at most one block crossing every 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 over variables representing the content of the 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 be a -tape nondeterministic Turing machine running in time . Then, for every function with , there exists a nondeterministic Turing machine that accepts the same language as . Furthermore, uses tapes, runs in time , and is -block-respecting when receiving an input of length .
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 -tape deterministic Turing machine over an alphabet , and set of states , we define its set of block configurations as for , representing the content of a size- block on each of the tapes, together with a state, and an offset describing the starting position of each head within the block (the positions 0 and 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
which maps a block configuration to the one resulting after steps of computation by if all heads stayed within their block in the first steps of computation, and to if some head exited its block in the first steps or began in position 0 or . Informally, the result of Pippenger–Fischer says , interpreted as a boolean function, can be computed by a circuit with gates. More formally, let be the number of bits required to describe a block configuration, and let 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 be a -tape deterministic Turing machine, and let be an integer. Let be such that for if and only if and are encodings of block configurations and , respectively, and . Then a circuit for with gates can be computed deterministically in time .
There is a natural analogue of the above for nondeterministic Turing machines. We assume that a nondeterministic machine makes one binary choice per step, or equivalently, it can read the th bit of a witness during the th step. For a block configuration and a witness , let be defined exactly as in the deterministic case except now it additionally takes in as input. This gives a nondeterministic block computation
Lemma 3.3 (Converting NTMs into circuits [17]). Let be a -tape nondeterministic Turing machine, and let be an integer. Let be such that for and if and only if and are encodings of block configurations and , respectively, and . Then a circuit for with gates can be computed deterministically in time .
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 be a circuit over variables with gates of fan-in at most 2. There is a 3-CNF formula over variables and clauses such that for every assignment to the variables we have if and only if . Furthermore can be computed in time .
Proofs of thm:lossless-general and thm:lossy-general
Proof of Theorem 2 assuming Lemma 2.1. Let be a nondeterministic Turing machine with running time , and be the arity function in the hypothesis. Given an input of length , we will deterministically decide whether accepts as follows. First, we use the algorithm from Lemma 2.1 on , , and for some sufficiently small , thus obtaining a collection of circuit-CSPs , each with variables, where for some fixed . This step takes time .2 The assumption of Theorem 2 tells us that each of these circuit-CSPs with variables, arity , and density at most 2 can be solved in time . There are such Circuit-CSPs, so solving all of them takes time . We output that accepts iff any is satisfiable. Condition 1 of Lemma 2.1 ensures the correctness of this algorithm. Plugging in , the total runtime is
since by hypothesis.
Proof of Theorem 3 assuming Lemma 2.2. The proof is nearly identical to that of Theorem 2. Given a nondeterministic TM running in time and an input of size , we compute as follows. First, we run the reduction in Lemma 2.2 to obtain a collection of 3-CNF formulas . This step takes time . Then, since each has variables and clauses, the assumption of Theorem 3 tells us that each 3-CNF can be solved in time , so solving all of them takes time . We accept iff any is satisfiable. Plugging in makes the total runtime . Taking makes this
since is non-decreasing.
Proof of lem:cl-for-CSP and cor:cl
Proof of Lemma 2.1. Fix , , and . First, by Lemma 3.1, there is a -block-respecting Turing machine accepting the same language as , with tapes. Fix an input of length , and let for some be an upper bound on the runtime of on , which we can easily compute since is time-constructible. Then, let be a copy of 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, runs forever on , but its state is accepting at time if and only if accepts on .3[eq] $
For ease of notation, let , so we wish to represent the computation of on for epochs of steps each. We enumerate all patterns (see Section 2.1) , and since there are of them, it suffices to show how to construct a given circuit-CSP corresponding to whether is in an accepting state at time having followed pattern .
Let denote the block movement at the end of epoch for tape , and let be the index of the block of the head of tape during epoch . We thus have for , and , where maps .
For each epoch , let be the circuit obtained from Lemma 3.3 computing . Our goal is to combine the different in order to obtain , and the main challenge is the interaction between their variables (e.g., the final content of tape 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 and for any variable . 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 , and we will then merge them into a single circuit. Concretely, let us define a formal substitution as follows: let be a boolean circuit, whose set of input variables is ; then, a formal substitution is simply a function where is some set of boolean variables. In turn, is the circuit obtained by simultaneously replacing each input variable by . In terms of the graph, Figure 5 illustrates the effect of formal substitution.

Figure 5. Formal substitution on circuit graphs. The substitution and , fixing .
Now, let us look more closely at the variables involved. Let and be the alphabet and states of , respectively. We can write the input and output configurations and as
where:
consists of bits representing the content of block before epoch , and is analogous but for after epoch .
consists of bits representing the state before epoch , and the state after epoch ; and
consists of bits representing the initial head offset relative to block , and the final head offset.
Next, we will define a formal substitution that intuitively represents giving the correct input information to based on the results of previous epochs. It will be convenient to define two pieces of notation. First, for every epoch and tape , let be the last epoch before that visited block (or in case that block had not been previously visited). More formally,
Second, for each block index , let be the constant binary encoding of the initial content of that block on tape (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
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
where is the constant binary encoding for the initial state of . 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 , let denote its binary encoding on bits. Then, for the first epoch, we have , 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
If , then .
If , then , and
If , then .
Furthermore, we need some consistency checks for the movement of the heads, defined as follows. If , then the check is a circuit ensuring that is indeed a number between 1 and . If , then ensures that , and if , then ensures that . Note that each can be implemented with gates.
Our constraint for every epoch is
For the final epoch , let be a circuit whose input variables are and that returns 1 if equals the binary encoding of any of the accepting states from the set . Then,
and note that uses only a constant number of gates, since . Finally, we simply output
The fact that accepts input if and only if some is satisfiable holds essentially by construction. Each has variables, and since there are of them, the total number of variables is . The fact that each has gates follows from the fact that each has gates per Lemma 3.3, and the have gates each. Moreover, each variable appears in at most two constraints: state variables 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 such that accepts if and only if one of them is satisfiable. For each such , we iterate over its constraints: . Each has variables and gates, so by Lemma 3.4, we can convert it into a 3-CNF formula , where the additional variables are disjoint across different . Then, let , and note it has variables and clauses. For correctness, assume a variable assignment satisfies , then for every , so each has a satisfying extension ; since the are disjoint, these combine into a satisfying assignment of . Conversely, if satisfies , then each is satisfied, so for all and satisfies . □
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 be a commutative ring. A Boolean tensor network over consists of a finite bipartite graph , in which parallel edges are allowed, together with a function
for each vertex , where is the set of edges incident to . Think of each edge as a Boolean variable , and of as a weight that depends only on the variables of the edges at . 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:
where is the restriction of to the edges at . The degree of the network is the maximum degree of .
We can now state a slightly simplified version of [16]’s Theorem D.1:
Theorem 4 ([16 Theorem D.1]). Let , and let be the description length of a Boolean tensor network with edges, at most vertices and maximum degree at most . Let every map to the ring for some . Suppose each value of can be computed from the description in time and space . Then the contraction can be computed deterministically in time .
We are now ready to prove that Lemma 1.3 follows from Theorem 4:
Proof of Lemma 1.3. Let be a circuit-CSP with variables, arity at most and constant density. We build a tensor network whose contraction is and then apply Theorem 4 with . We can assume without loss of generality that ’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 , which implies that there are at most constraint circuits .
From the circuit-CSP , 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 of we add a vertex to our graph, and for each variable of , we add a vertex . We add an edge between and iff . Set
We call each vertex with the tensor function defined above an equality vertex, since it forces all assignments to its edges to be equal. This choice of means that whenever a term in the contraction is nonzero, an assignment to the edges corresponds exactly to an assignment of the original variables (since we do not allow to take on multiple values). Our choice of then further ensures that all circuits must evaluate to 1 with this assignment. Thus, summing over all these assignments, the contraction equals , the number of satisfying assignments to $\Phi. (A variable that occurs in no constraint gives a vertex with no edges, which contributes a factor 1 instead of 2; we multiply 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 ’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 with degree , we replace with vertices and place an edge between and ’s th neighbor for all . We then add vertices to the other side of the bipartite graph and connect each of these vertices to two of the ’s such that there is a path in the graph between all the ’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 ’s must be equal in order for that term in the contraction to be nonzero.
This fixes the problem at the cost of additional vertices and edges. Since the density is constant, we have . Therefore, in total, our graph will have vertices and edges. Each has degree at most the arity , each that was not split has degree at most , and each new vertex has constant degree. Each equality vertex is trivial to compute, and each computes , which takes time. Furthermore, the network is described by the graph and the circuits , meaning . Finally, , so computing the contraction modulo gives exactly; we take . Theorem 4 therefore computes in time . ∎
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]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]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]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
- [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
- [6]Stephen A. Cook. Short propositional formulas represent nondeterministic computations. Information Processing Letters, 26(5):269–270, 1988. 1DOI
- [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
- [9]Juris Hartmanis and Richard Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285–306, 1965. 1.1DOI
- [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
- [11]Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367–375, 2001. 1DOI
- [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
- [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
- [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/.
- [15]Shlomo Moran. Some results on relativized deterministic and nondeterministic time hierarchies. Journal of Computer and System Sciences, 22(1):1–8, 1981.DOI
- [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.
- [17]Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361–381, 1979. doi:10.1145/322123.322138.DOI
- [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
- [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
- [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
- [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.