2
$\begingroup$

Theorem 7.11 in Introduction to the theory of computation 3rth edition says

Let $t(n)$ be a function where $t(n)>n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(t(n))}$ time deterministic single tape Turing machine.

I can understand that in this proof when we have a nondeterministic TM which every node in it can at most go to $b$ other nodes in its computation tree, then the time complexity of a deterministic Turing machine simulating it would be $O(t(n)b^{t(n)})$. But I'm not sure if I understand the $2^{O(t(n))}$ correctly.

Does it means that if $f(n) \in 2^{O(t(n))}$ then $\exists b\in \mathbb{N} \; f(n)\in O(b^{t(n)})?$

On the other hand, the claim 1.5 in the Computational complexity book says

For every $f : \{0, 1\}^∗ \rightarrow \{0, 1\}$ and time-constructible $T : N\rightarrow N$, if $f$ is computable in time $T(n)$ by a TM $M$ using alphabet $\Gamma$, then it is computable in time $4 log |\Gamma|T(n)$ by a TM $M$ using the alphabet $\{0,1,\square,\rhd\}$.

So every nondeterministic TM M running in $t(n)$ time can have an equivalent nondeterministic TM using $\{0,1\}$ alphabet running upper hand in $|\Gamma|^2t(n)$. Thus this equivalent TM's computation tree has at most 2 different branches in each step. Then we can have a deterministic simulator of that TM running in time $O(2^{|\Gamma|^2t(n)})$.

The intersection of 2 above statement suggests that carelessly we can say $O(2^{t(n)})=2^{O(t(n))}$, but we know $\forall b>2,\; b^{t(n)}\notin O(2^{t(n)})$.

Unfortunately, I didn't find any definition of $2^{O(t(n)}$. I wish to know is there any formal definition for $2^{O(t(n))}$?

- Edit: There is a similar question here. But I'm doubting its answer is the same since the big O notation in the power is not just $O(1)$.

Suppose we have nondeterministic TM that each node of it goes to 3 other nodes. Then there is a deterministic Turing machine that simulates it in time $t(n)3^{t(n)}$. So we can't say that there is a constant $k$ that $t(n)3^{t(n)} < 2^{kt(n)}.$

Meanwhile, when I think more, this definition holds if we ignore the Sipser proof. I mean if we begin the proof by the statement that every nondeterministic TM has a version $\{0,1\}$ alphabet running in $c.t(n)$ then the answer's definition is correct.

I wonder if there is bad use of big O notation in the Sipser's book or $2^{O(t(n))}$ has a different definition.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of What does $\log^{O(1)}n$ mean? $\endgroup$ – David Richerby Nov 16 '18 at 18:14
  • $\begingroup$ It's not exactly the same question but the same principles apply. $\endgroup$ – David Richerby Nov 16 '18 at 18:15
  • $\begingroup$ @DavidRicherby, Thank you for the link. By its best answer If I have $f(n) \in 2^{O(t(n))}$, I should think it as $\exists n_0,c\; \forall n> n_0 \; |f(n)| < 2^{ct(n)} $. But if for example I have a nondet. TM that each node of it goes 4 other nodes, then det. TM simulating it runs in $t(n)3^{t(n)}$ and I think it doesn't satisfy that definition. Or I'm misunderstanding something? $\endgroup$ – Doralisa Nov 16 '18 at 18:26
  • $\begingroup$ correcting my above comment, " ... nondet. TM that each nodes of it goes 3 other nodes ..." $\endgroup$ – Doralisa Nov 16 '18 at 18:34
  • $\begingroup$ I have not read beyond the second paragraph. Here is what I am thinking. $f(n)=2^{O(t(n))}$ means, by applying $log_2$ to both sides of the equality, $\log_2f(n)=O(t(n))$. Please note that everything here is well-defined! (assuming $f(n)>0$ for all $n$, or $f(n)>0$ eventually.) Let me see what happens in the question, comments and the answer then. $\endgroup$ – Apass.Jack Nov 19 '18 at 2:09
2
$\begingroup$

This is perfectly standard use of big O notation, despite some purists disliking it. Here is what the passage you quoted means:

Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) = O(t(n))$.

This is still somewhat ambiguous, since it’s perhaps not clear what variables the big O depends on. In this case, big O hides a universal constant:

There exists a constant $C>0$ such that the following holds.

Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) \leq Ct(n)$ for all $n$.

This allows us to rephrase the statement in yet another way:

There exists a constant $C>0$ such that the following holds.

Let $t(n)$ be a function where $t(n) > n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{Ct(n)}$ time deterministic single tape Turing machine.

(This assumes that by “$f(n)$ time machine” we mean a machine running in time at most $f(n)$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.