Running Time (P vs NP)
The running time of a TM $M$ is the function $t_M(n)$ where the function equals:
The maximum number of steps that $M$ takes on any input of length $n$.
This is basically big O notation.
Efficiency & the Church-Turing Thesis
Although different types of Turing machines are equally as powerful:
- They can’t all compute the same problem in the same running time.
Cobham-Edmonds Thesis
A computational problem can be feasibly solved on a computational device only if they can be computed in polynomial time, i.e., in time $O(n^c)$ where $n$ is the size of the input and $c$ is some constant.
This can differ between machine architectures.
P vs NP
- $P$ is the class of language that can be decided on a TM with polynomial running time in the input length.
- $NP$ is the class of language that can be decided on a nondeterministic TM with polynomial running time in the input length
It is an open question whether $P=NP$.