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
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
Mark44
#2
Apr26-12, 02:51 PM
Mentor
P: 21,215
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