3 Main Contributions
We express our results in terms of complexity classes defined by joint bounds on time and nondeterminism. Let NTIGU(
t(
n),
w(
n)) denote the class consisting of languages which can be decided by multitape nondeterministic Turing machines operating with time bound
O(
t(
n)) and using at most
w(
n) nondeterministic bits, for
n-bit inputs. (We follow prior usage with this definition [
4].)
An effective guessing hypothesis is a statement of the form: it is possible to speed up a computation by using more nondeterminism. We present two main results conditional on two different effective guessing hypotheses, one somewhat stronger than the other.
Our first result is that if even a small polynomial speedup can be achieved by introducing a polylogarithmic amount of nondeterminism, then we could decide all of P using nondeterministic linear time.
Our second result greatly weakens the effective guessing hypothesis while still yielding a surprising conclusion. In particular, the premise is weakened from polynomial to logarithmic speedup and from polylogarithmic to linear size witnesses. Being able to speed up computation by a logarithmic factor, even at the cost of making essentially every step nondeterministic, would imply a breakthrough nondeterministic algorithm for SAT on multitape Turing machines. This kind of effective guessing would allow us to overcome a barrier to progress that has stood for more than four decades.
Along the way to proving Theorem 2 we also derive an improved upper bound for SAT.
This improves a well-known upper bound SAT ∈NTIME(
n(
log n)
c) for some constant
c ≥ 1 that is not explicitly stated in the literature, obtained either by a direct argument [
5] or by using a random-access machine to perform the obvious guess-and-check algorithm in linear time, and using a standard simulation of RAMs by Turing machines [
6]. Theorem 3 allows us to take
c = 1.
4 Relationship to Prior Work
Some speedups are known to be impossible. This is the case for nondeterministic computations, which cannot be sped up polynomially by using a moderate amount of advice. In particular, Fortnow, Santhanam, and Trevisan showed that
\({\textsf {NP}}~ \not \subseteq {\textsf {NTIME}}(n^{c})/(\mathit {log}~ n)^{1/2c}\) for all
c [
7], and this result was extended by Fortnow and Santhanam to polynomial speedup and advice [
4].
Our work fits into the long tradition of conditional separations and containments of complexity classes. Previous work typically exploits classes that make nonuniform use of circuits. This includes Impagliazzo and Wigderson’s result that if E requires circuits of exponential size for infinitely many input sizes, then BPP = P [
8], Fortnow and Santhanam’s strengthening of the nondeterministic time hierarchy theorem in the presence of advice [
4], and the unconditional separation of Williams of ACC circuits of polynomial size and NEXP which was achieved by proving two conditional containments and then combining them to yield a contradiction [
9]. In contrast, we focus here on subclasses of classical nondeterministic time classes which are defined by bounding the amount of nondeterminism. Our Theorem 1 is also a significant extension of a result sketched by Bloch, Buss, and Goldsmith, weakening the effective guessing hypothesis used in their work from logarithmic to polylogarithmic nondeterminism [
10].
Our work further relates to questions raised by the classical result that
\({\textsf {DTIME}}(n) \subsetneq {\textsf {NTIME}}(n)\) of Paul et al. [
11]. This was obtained by assuming that DTIME(
n) and NTIME(
n) coincide, and then trading off an increase in alternations to obtain a speedup which contradicts a hierarchy theorem. Beginning with this strict containment, it is then natural to consider whether
\({\textsf {DTIME}}(t(n)) \subseteq {\textsf {NTIME}}(n)\) for any superlinear time-constructible function
t(
n). Our Theorem 2 demonstrates that a positive answer to this question for even a mildly superlinear function such as
t(
n) =
n log n would lead to a breakthrough for SAT. Furthermore, from a form of the nondeterministic time hierarchy theorem [
12, Corollary 2.3], the strict complexity class containment
\({\textsf {DTIME}}(n ~\mathit {log}~ n) \subsetneq {\textsf {NTIME}}(n ~\mathit {log}~ n)\) would straightforwardly follow. Although Paul et al. [
11] showed that the strict containment
\({\textsf {DTIME}}(t(n)) \subsetneq {\textsf {NTIME}}(t(n))\) holds for
t(
n) =
n, and Santhanam extended this to any
\(t(n) = o(n\lg ^{*} n)\) [
13, Theorem 2.5], such a result is not known for functions
t(
n) that grow at least as fast as
\(n\lg ^{*} n\). (The iterated logarithm
\(\lg ^{*} x\) is the minimal height of a tower of 2s representing a number at least as large as
x.) Note that we do not use the alternation-trading technique from [
11] in our work.
6 Preliminaries
With \(\mathbb {N}\) we mean the set \(\{0,1,2,\dots \}\). We assume a fixed alphabet Σ = {0,1} throughout. We also use the notation \(\lg x = \mathit {log}_{2} x\) throughout. For x,y ∈Σ∗, the expression 〈x,y〉 simply denotes the bits of x followed by those of y, also known as concatenation. This guarantees associativity: 〈x,〈y,z〉〉 = 〈〈x,y〉,z〉. For a word x ∈Σ∗, we denote by \(\lvert {x}\rvert \) the number of symbols in x, which may be 0 if x is the empty word. Hence \(\lvert {{\langle {x,y}\rangle }}\rvert = \lvert {x}\rvert + \lvert {y}\rvert \). In a slight abuse of notation, when \(f \colon \mathbb {N} \to \mathbb {N}\) is a function we will often write f(n) to emphasize this fact, rather than just f, and when c is a constant, we will sometimes use c to denote the constant function c(n) = c. With SAT we mean the Boolean Satisfiability problem for Boolean formulas in conjunctive normal form (CNF).
Our exposition is based on the concept of existential projection. We will use existential projections to define classes of languages with combined time and witness size bounds. This approach simplifies the bookkeeping required to track witness sizes in composed simulations, yet these classes are closely related to more familiar complexity classes. We first define the notion and then discuss some consequences and an example.
The witness size function w represents some portion of each word in the language which is set aside to record choices made by a nondeterministic computation. The existential projection then removes this portion of each word.
We now make precise how Definition 4 affects witness size changes in composition of existential projections.
We now define time-witness classes in terms of existential projections.
We need to be careful to account for the total nondeterminism when composing two or more nondeterministic simulations; such compositions are crucial for the proofs of our results. We have chosen to define time-witness classes via the existential projection because this notation assists in explicitly keeping track of witness size scaling in compositions. Existential projections also allow us to control the overhead of encoding. Such detailed bookkeeping becomes necessary when the number of compositions in an argument is allowed to grow with the instance size.
For a function
\(w \colon \mathbb {N} \to \mathbb {N}\), let
$$ {{\textsf{TIWI}}}(t(n),O(w(n))) = \bigcup_{c>0} {{\textsf{TIWI}}}(t(n),cw(n)). $$
As usual, polylog(
n) denotes the class of functions
$$ \bigcup_{c>0} \{ f(n) \colon \mathbb{N} \to \mathbb{N} \mid f(n) = O((\lg n)^{c}) \}. $$
As a notational convenience, if
ϕ(
n) is a logical expression in which the variable
n occurs free and there are no other free variables, then we say that
ϕ(
n) holds
eventually if there exists some
\(n_{0} \in \mathbb {N}\) such that
ϕ(
n) is a true sentence for all
\(n \in \mathbb {N}\) such that
n ≥
n0.
The following lemma will simplify several proofs. This result allows us to ignore minor differences in the witness size functions when comparing two time-witness classes, and instead to focus on how they behave asymptotically.
For functions \(w,t \colon \mathbb {N} \to \mathbb {N}\), we say that w(n) is computable in t(n) time if there is a deterministic Turing machine that when given x ∈Σ∗, in at most \(t(\lvert {x}\rvert )\) steps writes a word on its output tape with precisely \(w(\lvert {x}\rvert )\) symbols. For simplicity, we assume that all witness size functions in the following are computable within the provided time bounds. By first computing the witness size function for the given input, a Turing machine can determine where a word finishes and the witness bits begin, thereby avoiding overhead for self-terminating encodings or separator characters in the alphabet.
NTIGU(
t(
n),
w(
n)) is the class of languages decidable by a multitape Turing machine that takes at most
O(
t(
n)) steps and uses at most
w(
n) nondeterministic bits on any input of length
n (for instance, see [
4]). The following results explain our choice of Definition 6, by relating the time-witness TIWI classes to the more familiar NTIME (Lemma 8) and time-guess NTIGU (Lemma 9) classes.
First we consider the case where witness size is quite large, even possibly dominating the input size.
If
k ≥ 3 then any
k-tape Turing machine can be simulated by a two-tape machine with a logarithmic increase in time [
15]. This slowdown does not affect Lemma 8 as we are not trying to reduce the number of tapes: in the proof each inclusion increases the number of tapes. This increase does not matter for the purpose of establishing the result, or for the applications where we use it, although it might be important for other applications of the technique where the number of tapes has to be more carefully controlled.
Lemma 8 showed that TIWI classes for superlinear witness bounds lose the discrimination power of the NTIGU classes. However, our next result shows that TIWI and NTIGU classes coincide for at most linear witness size and many common time bounds.
Proof
First let K ∈TIWI(t(n),w(n)). Then there exists some language L ∈DTIME(t(n)) such that K = L[w(n)]. Suppose that M is a deterministic Turing machine which decides L in O(t(n)) steps. We need to decide whether x ∈ K using a nondeterministic machine \(M^{\prime }\). \(M^{\prime }\) first copies x to a tape (which will be the input tape of M), appends \(w(\lvert {x}\rvert )\) bits to this tape the values of which are determined nondeterministically, and then simulates M. The simulation can be performed using a constant number of deterministic steps per step of M, so the total number of steps to decide whether x ∈ K is at most \(a\cdot t(\lvert {x}\rvert +w(\lvert {x}\rvert ))+b\cdot w\lvert {x}\rvert \) for some constants a,b. Moreover, \(M^{\prime }\) uses \(w(\lvert {x}\rvert )\) nondeterministic bits and accepts x if, and only if, there is some y ∈Σw(n) such that 〈x,y〉∈ L. This is equivalent to saying that \(M^{\prime }\) accepts x iff x ∈ K, so \(M^{\prime }\) correctly decides K.
We now claim that if T(n) ≤ a ⋅ t(n + w(n)) + b ⋅ w(n) eventually for constants a,b, then the conditions guarantee that T(n) = O(t(n)). Therefore K ∈NTIGU(t(n),w(n)) by putting T(n) as the largest number of steps taken by \(M^{\prime }\) to decide an input of n bits. To prove the claim, suppose there are constants a,b such that T(n) ≤ a ⋅ t(n + w(n)) + b ⋅ w(n) eventually. Since \(t(n) = O(n^{c}(\lg n)^{d})\), we have some constant e so that \(t(n) \le e\cdot n^{c}(\lg n)^{d}\) eventually. Then \(T(n) \le a\cdot t(n+w(n))+b\cdot w(n) \le a\cdot e(n+w(n))^{c}(\lg (n+w(n)))^{d} + b\cdot w(n) \le a\cdot e(2n)^{c}(1+\lg n)^{d} + b\cdot n \le a\cdot e\cdot (2n)^{c}(2\lg n)^{d} + b\cdot n = (a 2^{c} 2^{d} e)n^{c}(\lg n)^{d} + b\cdot n\) eventually. As c ≥ 1 and d ≥ 0 it follows that \(T(n) = O(n^{c}(\lg n)^{d})\). Now since \(t(n) = {\Omega }(n^{c}(\lg n)^{d})\), we have that T(n) = O(t(n)), and we are done.
For the other direction, suppose K ∈NTIGU(t(n),w(n)). There is then some nondeterministic Turing machine \(M^{\prime }\) which decides K using O(t(n)) steps and with w(n) bits of nondeterminism. \(M^{\prime }\) accepts x precisely when there is some y ∈Σw(n) representing the nondeterministic moves made by \(M^{\prime }\) in reaching an accepting state (within O(t(n)) steps). We build a deterministic Turing machine M, which when given x and the nondeterministic moves y as input 〈x,y〉, simulates \(M^{\prime }\) using a number of deterministic steps per step of \(M^{\prime }\) that is bounded by some constant a. To achieve this we first compute \(w(\lvert {x}\rvert )\) in at most \(O(t(\lvert {x}\rvert )\) steps and store this on a unary tape, which we can then use to determine where x ends and y begins. Hence M on input 〈x,y〉 takes at most \(a\cdot t(\lvert {x}\rvert ) + b\lvert {y}\rvert \) steps, so \(O(t(\lvert {x}\rvert +\lvert {z}\rvert ))\) steps. We can now let language L be the language of words 〈x,y〉 accepted by M. There is some y ∈Σw(n) such that machine M accepts 〈x,y〉 iff \(M^{\prime }\) accepts x. Then K = L[w(n)] and L ∈DTIME(t(n)), so K ∈TIWI(t(n),w(n)). □
In the proof of Lemma 9 each inclusion increases the number of tapes by one. This does not affect our results but might restrict some applications.
While classes such as NTIGU(t(n),w(n)) measure the time bound in terms of the input, TIWI(t(n),w(n)) measures the time bound as a function of both the input and the witness. For witnesses growing strictly faster than the size of the input, the two definitions can diverge where TIWI(t(n),O(w(n))) is not equal to NTIGU(t(n),O(w(n))). To see this, take t(n) = n and w(n) = n2. We have that NTIGU(n,O(n2)) = NTIGU(n,O(n)) = NTIME(n) because additional guess bits beyond O(t(n)) do not help us. However, NTIME(n2) = TIWI(n,O(n2)) by Lemma 8. Therefore, \({\textsf {NTIGU}}(n,O(n^{2})) = {\textsf {NTIME}}(n) \subsetneq {\textsf {NTIME}}(n^{2}) = {{\textsf {TIWI}}}(n,O(n^{2}))\) by the nondeterministic time hierarchy theorem.
Notice from the preceding discussion that as the witness size grows beyond the input size, the NTIGU classes no longer capure new languages while the TIWI classes become equivalent to the coarser classical nondeterministic time classes. Even though these two definitions can diverge when the witness size is larger than the input size, Lemma 9 allows us to use TIWI rather than NTIGU in the subsequent discussion, because in this work we are interested in witnesses of moderate size, at most as large as the input size and computable within the given time bounds. The choice of TIWI avoids technical difficulties arising from instance size blowup when composing simulations, and essentially amounts to preallocating the nondeterministic bits which are used in a computation and including them in the instance size.
7 Strong Effective Guessing Would Imply Linear-Time Simulation of P
In this section we show that a strong form of guessing would imply that all of P is contained in NTIME(
n). It appears to us that this is unlikely to be true. Even though such an inclusion in turn would imply that P ≠NP, many other rather less likely consequences would also follow. These include improving the current best
O(
n2.37286) algorithm for multiplication of
n by
n matrices (see [
16]) to
\(\tilde {O}(n^{2})\) time, reducing the time for general graph maximum matching from
\(\tilde {O}(n^{2.5})\) (see [
17]) to
\(\tilde {O}(n^{2})\), and reducing the
nk/c time (for some
c such that 1 ≤
c <
k) to decide if an input graph contains a
k-clique to
\(O(n\lg n)\) time, all achieved through the use of nondeterminism. Yet it is not at all clear that allowing guessing could significantly speed up so many well-studied and disparate algorithms. (Here we use the common convention that
\(\tilde {O}(t(n))\) denotes the class of functions
\(\bigcup _{c>0} O(t(n)(\lg t(n))^{c})\).)
Informally, our argument for Theorem 1 works as follows. We have defined the class \({{\textsf {TIWI}}}(n,\lg n)\), which by Lemma 5 can be regarded as the class of languages decided by nondeterministic machines that use linear time and \(\lg n\) bits of nondeterminism. We suppose that \({\textsf {DTIME}}(n^{2}) \subseteq {{\textsf {TIWI}}}(n,\lg n)\). By a padding argument it follows that \({\textsf {DTIME}}(n^{4}) \subseteq {{\textsf {TIWI}}}(n^{2},\lg n)\). Now suppose \(L \in {{\textsf {TIWI}}}(n^{2},\lg n)\); this means that there is a language \(L^{\prime } \in {\textsf {DTIME}}(n^{2})\) such that x ∈ L if there is a y of length \(\lg n\) and \(xy \in L^{\prime }\). Again applying our hypothesis, this time to \(L^{\prime }\), we conclude via Lemmas 7 and 8 that \(L \in {{\textsf {TIWI}}}(n,\lg n)\). We therefore conclude that \({\textsf {DTIME}}(n^{4}) \subseteq {{\textsf {TIWI}}}(n,\lg n)\). We can then use this step in an induction argument. We now proceed with a formal version of this argument.
In preparation for our result, we need to demonstrate that time-witness classes are structurally well-behaved. We first establish conditions which ensure that increases in witness size are kept reasonable when applying effective guessing.
We continue with a useful amplification property of time-witness classes in the presence of effective guessing. By analogy with superadditive functions (see [
18]), we say that a function
\(f \colon \mathbb {N} \to \mathbb {N}\) is
weakly superadditive if
f(
n +
d) ≥
f(
n) +
d for all
\(d,n \in \mathbb {N}\). Note that any function
f(
n) =
nc, where
c ≥ 1, is weakly superadditive.
We say that a function
f(
n) is
subpolynomial if for every
c > 0 we have that
f(
n) =
o(
nc), and
semihomogeneous (see [
18]) if for any
d > 1 there is a constant
C =
C(
d) such that eventually
f(
dn) ≤
C ⋅
f(
n). Note that any polylogarithmic function (such as
\(f(n) = (\lg n)^{3}\)) is subpolynomial and also semihomogeneous.
This leads up to our first amplification argument, showing that a form of effective guessing with small witnesses can be amplified to yield a larger speedup at the cost of only a moderate amount of additional guessing.
We now wrap up our second amplification argument into a theorem.
Via Lemma 9, Theorem 1 is a corollary of Theorem 14 for the special case that
v(
n) is a subpolynomial function that grows faster than any polylogarithmic function;
\(v(n) = (\lg n)^{\lg \lg n}\) is an example of such a function. A result similar to Theorem 14 was sketched in [
10], with a logarithmic witness bound
v(
n) rather than our stronger subpolynomial bound. To extract the most out of the iterated guessing technique, we have found that it is crucial (as we have done) to carefully take into account how the witness size grows as simulations are composed.
8 Effective Guessing Would Imply a SAT Breakthrough
We now show that if general computations can be significantly sped up by using nondeterministic guessing to replace part of the computation, then this would imply a breakthrough for solving SAT. More precisely, we show that using guessing to obtain an at least logarithmic factor reduction in time would imply that SAT can be decided in linear time on a nondeterministic multitape Turing machine.
1 Simple nondeterministic Turing machine algorithms for SAT use
\(O(n(\lg n)^{c})\) time, for some constant
c ≥ 1, but this bound has resisted improvement for several decades and the at least logarithmic factor has stubbornly remained [
5,
6].
A high level sketch of the argument for proving Theorem 2 is as follows. First, we show that any n-bit CNF formulas (in a reasonable encoding) can have at most \(4n/\lg n\) variables. Then we establish a fairly precise time bound for sorting on deterministic multi-tape Turing machines: a list of m integers, each of size \(\lg n\), can be sorted in at most \(O(m(\lg m)(\lg n))\) steps. Combining these results we can show that SAT is in \({{\textsf {TIWI}}}(n\lg n,4n/\lg n)\). Now if \({\textsf {DTIME}}(n\lg n)\) were contained in NTIME(n), then \({{\textsf {TIWI}}}(n\lg n,4n/\lg n)\) would be contained in NTIME(n), and therefore SAT ∈NTIME(n). We proceed by proving technical results which will allow us to formalize this argument.
The following lemma shows that a nontrivial speedup of deterministic computation would also allow computations with a significant nondeterministic component to be sped up.
Although Lemma 15 is closely related to Lemma 11, the weaker hypothesis of the Weak Speedup Lemma means that these results are not directly comparable.
8.1 Improved Algorithms For SAT From Effective Guessing
We now apply the Weak Speedup Lemma to show that effective guessing implies improved algorithms for SAT.
In Corollary 16, the time upper bound
t(
n) for SAT enables the efficient guessing hypothesis to yield an improved algorithm for SAT. Classical results imply that
\(\text {SAT} \in {{\textsf {TIWI}}}(n(\lg n)^{c},n)\) for some unspecified constant
c. This is because a guess-and-check procedure can be implemented via sorting [
5], and the number of variables determinines the witness size yet cannot exceed the input size. We could therefore conclude a linear time upper bound for SAT from an effective guessing hypothesis of the form
\({\textsf {DTIME}}(n(\lg n)^{c}) \subseteq {\textsf {NTIME}}(n)\).
A smaller time bound for SAT permits a weaker effective guessing hypothesis. How weak can the hypothesis be made? It turns out that we can actually take c = 1 with some additional work. This sharper bound requires two ingredients.
The first ingredient is a reasonable encoding of SAT, which distinguishes between formulas in conjunctive normal form (CNF) which only differ by a permutation of their variable names. Reasonable encodings are used in Cook’s original proof of the Cook–Levin theorem [
20] and Karp’s list of 21 NP-complete problems [
21]. In fact, we are not aware of any work which relies on a particular encoding of SAT yet does not use a reasonable encoding of SAT. Furthermore, the standard DIMACS CNF encoding used by SAT solvers
2 also qualifies as reasonable. We show that a reasonable encoding of SAT has the property that an
n-bit CNF formula cannot represent more than
\(O(n/\lg n)\) different variables, eventually.
Second, we need sharp time bounds for sorting on a Turing machine. Standard mergesort algorithms are slightly wasteful when implemented on a Turing machine, so we take a closer look at Schnorr’s classical approach (from [
5]) to obtain a more precise time bound.
The saving in the witness size due to a reasonable encoding is offset by overhead from sorting, but combining these two ingredients allows us to conclude c = 1.
8.2 Bounding the Number of Variables in a CNF Formula
The following technical lemmas will be used to relate the number of variables in a SAT instance to its size.
We now assert that an encoding of SAT which removes all symmetries due to variable names does not constitute a reasonable encoding. An unreasonable encoding could represent a CNF formula by a binary encoded integer which represents one particular CNF formula out of a predetermined list of equivalence classes of CNF formulas, with formulas regarded as equivalent up to reordering and renaming of variables. We instead consider only reasonable encodings, which have the property that if two CNF formulas can be obtained from each other by simply permuting variable names, then these formulas will be represented by different words in the language. With this restriction on what constitutes a reasonable encoding of SAT, we now prove an upper bound on how many variables can appear in a SAT instance in terms of its size.
8.3 A More Precise Sorting Time Bound
Results about sorting on a Turing machine are used in many classical papers. However, as far as we are aware, a time bound has not been expressed in the literature in the precise form that we will present here. We do not claim originality for such a result, but also have not been able to locate a proof with this bound. We therefore provide a proof for completeness.
Proof
We use a form of bottom-up mergesort. Instead of a random access algorithm such as that of Batcher [
23], we use a procedure that uses a fixed number of tapes and only sequential access, and can therefore be efficiently implemented on a deterministic multitape Turing machine. This algorithm is a more detailed version of that outlined by Schnorr [
5, Program
p1]. These additional details allow a more precise analysis of the time bound, which Schnorr was not attempting to optimise.
The algorithm proceeds in stages. At each stage we use three tapes containing permutations of the list of m integers: Result, Source, and Target. During each stage, Source and Target are piecewise merged to form Result. Result then becomes the Source for the next stage, and is copied to Target to begin the next stage. Half the elements to be merged in each stage are on Source and the other half on Target: the actual contents of Source and Target are identical but we pay attention to a different pattern of sequences on Source compared to Target. We use two copies of the list (one on Source and one on Target), rather than a single source tape, to avoid back-and-forth tape head moves. This is key to keeping the runtime under control.
After \(\lceil \lg m \rceil \le 2\lg m\) stages the current Result tape contains a sorted list. Moreover, each stage uses \(O(m\lg n)\) steps. This is because we can use a small fixed number of tapes to keep track of various unary quantities, and two tapes as temporary workspace to copy the integers on Source and Target that are the current focus of attention. This allows the machine to move the heads on Result, Source, and Target tapes only in one direction, with no backward motion required. Backward motion is only used when the heads are repositioned to the start of each tape, at the end of each stage. Moreover, the head movements on the auxiliary tapes only require a constant factor overhead. The overall time bound then follows.
We first pad the input with dummy values that represent a number larger than the largest integer represented using \(\lg n\) bits, so that the number of values in the list is a power of 2 (and, in particular, \(\lg m\) is a non-negative integer). The overhead of this padding stage is included in the unspecified constant factor in the overall time. (Moreover this also only increases the space used by at most a factor of 2.) We now outline the key steps for the case where m is a power of 2.
For each \(i=0,1,\dots ,(\lg m) - 1\), if Source and Target at the start of stage i contain m/2i sequences of sorted sublists, each sublist of length 2i, then at the end of the stage Result will contain m/2i+ 1 sorted subsequences, each containing 2i+ 1 elements. At stage i, the Source tape head is at the start of the tape, and we move the Target tape head to the position after the 2ith entry in the list (position \(2^{i}\lg n\) if the first position on the tape is numbered 0). Once the first sublist has been processed, we move the heads forward by \(2^{i}\lg n\) positions. We proceed until the Target tape head reaches the position after the end of the whole list, position \(m\lg n\).
To process a single pair of sublists S and T (on the Source and Target tapes, respectively), we first set up a unary counter using an auxiliary tape to keep track of the length of these sublists, then scan the elements sequentially and write the sublist formed by merging S and T to the Result tape. At each step we are deciding which of a pair of elements to write to the result tape. We write the smaller of the two current elements to the Result tape. We do this by copying the current elements to two auxiliary tapes, and during copying flagging which tape contains the smaller of the two elements. The auxiliary tapes are then rewound, and the flagged tape is copied to the Result tape. □
Schnorr proved a time bound of
\(O(m(\lg m)^{c}(\lg n))\) steps for some unspecified
c [
5]. By a more detailed analysis of the tape head motion than was considered in Schnorr’s argument we have obtained this more precise exponent for the logarithmic factor of
c = 1.
8.4 Improving the Time-Witness Bound For SAT
We are now able to prove a time-witness upper bound on SAT.
We restate this in terms of the NTIGU notation.
Our time-witness bound for SAT then yields the main result of this section.
9 Conclusion and Further Work
Our contributions in this work demonstrate that effective guessing has unlikely consequences. We therefore propose an ineffective guessing conjecture, that it is not in general possible to speed up a computation significantly by using more nondeterminism.
More precisely, we propose the following ineffective guessing conjecture:
According to this ineffective guessing conjecture, it is not in general possible to obtain even a slightly greater than logarithmic speedup by making essentially every step of a computation nondeterministic. Furthermore, our ineffective guessing conjecture implies that the effective guessing hypothesis from Theorem 1, with a polynomial speedup, is too strong while the weaker effective guessing hypothesis from Theorem 2 could still hold.
To put Theorems 14 and 2 into context, the effective guessing hypotheses used in these theorems fall between two extremes.
$$ \begin{array}{@{}rcl@{}} \textbf{excessively-weak EGH} &:& {\textsf{DTIME}}(n) \subseteq {\textsf{NTIGU}}(n, 0)\\ \textbf{weak EGH} &:& {\textsf{DTIME}}(n\lg n) \subseteq {\textsf{NTIME}}(n)\\ \textbf{strong EGH} &:& (\exists c > 1) (\forall d > 0) {\textsf{DTIME}}(n^{c}) \subseteq {\textsf{NTIGU}}(n, n^{d})\\ \textbf{excessively-strong EGH} &:& (\exists c > 0) {\textsf{DTIME}}(n^{2+c}) \subseteq {\textsf{NTIGU}}(n,\lg n) \end{array} $$
The hypothesis from Theorem 14 is the strong EGH, while Theorem 2 posits the weak EGH. To be clear, both of these hypotheses currently remain open, although we have shown that they have somewhat unlikely consequences.
Excessively weak forms of effective guessing are always true such as \({\textsf {DTIME}}(n) \subseteq {\textsf {NTIGU}}(n, w(n))\) which holds for any function w(n), even w(n) = 0. This therefore forms one extreme, a hypothesis about effective guessing that is too weak to be interesting. On the other hand, we show in the following that excessively strong forms of effective guessing (such as that stated above) can be ruled out unconditionally.
Since the strong EGH trivially implies the weak EGH, we can therefore rank the hypotheses in terms of logical strength as follows:
$$ \begin{array}{@{}rcl@{}} \textbf{excessively-strong EGH} && \textbf{[false]}\\ \Downarrow &&\\ \textbf{strong EGH} && \textbf{[open]}\\ \Downarrow&&\\ \textbf{weak EGH} && \textbf{[open]}\\ \Downarrow&&\\ \textbf{excessively-weak EGH} && \textbf{[true]} \end{array} $$
Finally, our effective guessing hypotheses focus on nondeterministic linear time because the Paul et al. [
11] result that
\({\textsf {DTIME}}(n) \subsetneq {\textsf {NTIME}}(n)\) invites many questions about the potential computational power of nondeterministic linear time. A natural future direction would be to consider the computational power of NTIME(
nk) for
k > 1. In particular, it is still is not known whether
\({\textsf {DTIME}}(n^{k}) \subsetneq {\textsf {NTIME}}(n^{k})\) for any
k > 1. Furthermore, there are many additional open questions such as whether any languages exist in NTIME(
nk) ∖NTIGU(
nk,
o(
nk)).