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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Possible duplicate of What does $\log^{O(1)}n$ mean? $\endgroup$
    – David Richerby
    Commented Nov 16, 2018 at 18:14
  • $\begingroup$ It's not exactly the same question but the same principles apply. $\endgroup$
    – David Richerby
    Commented Nov 16, 2018 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
    Commented Nov 16, 2018 at 18:26
  • $\begingroup$ correcting my above comment, " ... nondet. TM that each nodes of it goes 3 other nodes ..." $\endgroup$
    – Doralisa
    Commented Nov 16, 2018 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$
    – John L.
    Commented Nov 19, 2018 at 2:09

1 Answer 1

Reset to default
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)$.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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