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
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
Mark44
#2
Apr26-12, 02:51 PM
Mentor
P: 21,261
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