What happens to the coefficient in O(t(n)b^{t(n)})?

Click For Summary

Discussion Overview

The discussion revolves around the asymptotic analysis of the running time of deterministic Turing machines equivalent to nondeterministic Turing machines, specifically focusing on the expression O(t(n)b^{t(n)}) and its simplification to 2^{O(t(n))}. Participants explore the implications of coefficients in asymptotic notation and the dominance of exponential terms.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant questions the simplification of O(t(n)b^{t(n)}) to 2^{O(t(n))}, noting that the coefficient O(t(n)) seems to disappear in the process.
  • Another participant suggests that the right-hand side can be broken into two parts, each asymptotically larger than the factors on the left-hand side.
  • A further inquiry is made about the specific case where t(n) = n^2 and the maximum branching factor is 2, asking if the running time can be simplified to just 2^{O(n^2)} and why this is the case.
  • One participant proposes a method of expressing the right-hand side as the square of 2^{(1/2) O(t(n))} to illustrate the breakdown into two parts.
  • Another participant points out that this manipulation may not have a clear purpose, questioning the necessity of such a breakdown.
  • It is noted that 2^{O(t(n))} is asymptotically larger than t(n), which supports the argument that the exponential term dominates the polynomial term in the analysis.

Areas of Agreement / Disagreement

Participants express differing views on the simplification process and the treatment of coefficients in asymptotic notation. There is no consensus on the necessity or clarity of breaking down the expressions into parts.

Contextual Notes

The discussion highlights the complexity of asymptotic notation and the assumptions regarding the dominance of exponential terms over polynomial terms. Specific cases and examples are used to illustrate points, but the implications of these examples remain unresolved.

gnome
Messages
1,031
Reaction score
1
In Sipser, "Introduction to the Theory of Computation", a proof that "every t(n) time nondeterministic single-tape Turing machine (where t(n) ≥ n) has an equivalent 2O(t(n)) time deterministic single-tape Turing machine" shows that the running time of the equivalent NTM is [itex]O(t(n)b^{t(n)})[/itex] and then concludes with the statement:

[tex]O(t(n)b^{t(n)}) = 2^{O(t(n))}[/tex]

which is not entirely clear to me.

b in this case is just a constant representing the maximum branching factor of the NTM.

I guess that [itex]2^{O(t(n))}[/itex] is equivalent to [itex]b^{t(n)}[/itex] since b is a constant and therefore [itex]log_2{b}[/itex] is a constant so we get

[tex]b^{t(n)} = 2^{(log_2 b)* t(n)} = 2^{O(t(n))}[/tex]

Correct?

But, then what happened to the other O(t(n)) (the coefficient of the original expression)? That was not a constant term. It might be n, or nlogn, or n2, or whatever, but certainly not a constant. So why did it just disappear? Is it just that the exponential term so dominates that the t(n) coefficient is dropped as insignificant?
 
Physics news on Phys.org
It didn't just disappear -- you have to break the RHS into two parts, each part asymptotically bigger than one of the factors of the LHS.
 
I don't understand your meaning. Where are the two parts in [itex]2^{O(t(n))}[/itex]?

Or to put it another way: for argument's sake, suppose that every branch of the original NTM has a length of at most n2, so t(n) = n2 in the original NTM. And further, suppose that the maximum branching factor was just 2. Then we would have the total number of nodes [itex]= O(2^{n^2})[/itex] and the time for traveling from the root to a node = [itex]O({n^2})[/itex]. Therefore, the running time of the equivalent deterministic machine = [itex]O(n^22^{n^2})[/itex]. Can this be simplified to just [itex]2^{O(n^2)}[/itex]? Why?
 
You can almost always break things into two parts if you're creative! How about writing it as the square of 2(1/2) O(t(n))?
 
But what is the point of that? (And anyway, ½O(t(n)) is the same as O(t(n)), isn't it?)
 
Because you can prove 2^O(t(n)) is asymptotically larger than t(n), and equal to O(b^t(n)), therefore 2^O(t(n)) * 2^O(t(n)) must be asymptotically at least as large as O(t(n) * b^t(n)).

But what is the point of that? (And anyway, ½O(t(n)) is the same as O(t(n)), isn't it?)

Yep! But writing it that way makes it clear how I'm breaking it into two parts.
 
OK, I see your point.

Thanks, Hurkyl.
 

Similar threads

Electromagnetic waves incident on an anti-reflective coating
  • · Replies 3 ·
Replies
3
Views
3K
MHB Equivalent RAM Program: Hints to Show Complexity $O(T^2(n))$
  • · Replies 9 ·
Replies
9
Views
3K
Graduate Laurent series for algebraic functions
  • · Replies 9 ·
Replies
9
Views
3K
MHB K^n as a K[T]-module - Exercise 1.2.8 (a) - Berrick and Keating (B&K)
  • · Replies 3 ·
Replies
3
Views
2K
Challenge Intermediate Math Challenge - July 2018
  • · Replies 16 ·
Replies
16
Views
7K
Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K
Graduate Determine PDE Boundary Condition via Analytical solution
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Predicting how far an object will fly
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Atmospheric Density vs Altitude in an O'Neil Cylinder
  • · Replies 1 ·
Replies
1
Views
3K
Can a PTM simulate a one-tape Turing machine in O(T^2) time?
  • · Replies 9 ·
Replies
9
Views
4K