Register to reply

Turing machine - polynomial time expression

by xeon123
Tags: expression, machine, polynomial, time, turing
Share this thread:
xeon123
#1
Apr26-12, 02:22 PM
P: 81
In the Turing Machine, the machine accepts a word if the computation terminates in the accepting state. The language accepted by the machine, L(M), has associated an alphabet Δ and is defined by

L(M) = {w [itex]\in[/itex] [itex]\Delta[/itex]}

This means that the machine understands the word w if w belongs to the language.
We denote by Tm(w) the number of steps in the computation of M on the input w. If the computation never halts, then Tm(w)=infinity.

Also, we denote the worst case run time of M as

Tm(n) = max{Tm(w)}

which means the biggest words in the dictionary (I suppose).

But, we say that M runs in polynomial time if there exists k such that for all n, T(n)[itex]\leq[/itex] n^k + k.

I don't understand what n^k+k means. Can anyone explain me the last expression?

Thanks,
Phys.Org News Partner Mathematics news on Phys.org
Researcher figures out how sharks manage to act like math geniuses
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
Mark44
#2
Apr26-12, 02:51 PM
Mentor
P: 21,409
Quote Quote by xeon123 View Post
In the Turing Machine, the machine accepts a word if the computation terminates in the accepting state. The language accepted by the machine, L(M), has associated an alphabet Δ and is defined by

L(M) = {w [itex]\in[/itex] [itex]\Delta[/itex]}

This means that the machine understands the word w if w belongs to the language.
We denote by Tm(w) the number of steps in the computation of M on the input w. If the computation never halts, then Tm(w)=infinity.

Also, we denote the worst case run time of M as

Tm(n) = max{Tm(w)}

which means the biggest words in the dictionary (I suppose).

But, we say that M runs in polynomial time if there exists k such that for all n, T(n)[itex]\leq[/itex] n^k + k.

I don't understand what n^k+k means. Can anyone explain me the last expression?

Thanks,
Your definition for polynomial time seems to be a little off. It's usually defined as T(n) ≤ nk, without the additional k term that you showed.

If you do a search for "polynomial time" this is one of the links that you'll see: http://www.wordiq.com/definition/Polynomial_time.


Register to reply

Related Discussions
Polynomial expression of Pendulum period... with respect to angle (large) Introductory Physics Homework 1
Evalute expression of associated Legendre's polynomial Calculus 2
Is it true that the derivative of 1/(random polynomial expression) is 0? Calculus & Beyond Homework 3
Black Hole Time Machine (time dilation) Special & General Relativity 13
Touring Grad Schools Academic Guidance 3