FIT2014 Lecture Notes - Lecture 19: Invertible Matrix, Euclidean Algorithm, Lexicographical Order
29 Jun 2018
School
Department
Course
Professor
Lecture 19: Polynomial time, and the class P
Decidable languages
- Solvable in principle
- Doesn’t matter which computer you are using or the hardware etc
- How we are trying to talk about the time
Time Complexity
- The time taken by a Turing machine M on an input x is the number of steps M takes until it halts.
- tM(n) = maximum time taken by M for any input of length n
- It’s a function of n, which can be any positive integer. For it to be defined, M must halt on all inputs.
- Worst case
Example: Turing machine to decide whether a string ends in b
- moves to the right until reaches first blank symbol, then does one step to the left and accepts if the
symbol there is b, otherwise rejects
- time complexity? n + 1
Example: Turing machine to decide whether a string is a palindrome ◦ time complexity?
- ½ . n(n+2)
Example: Turing machine to decide whether a string is empty
time complexity? 1
Exercise: consider any regular language. What can you say about its time complexity? See Lecture 14 on Turing
Machines: finite automaton → Turing machine
Time Complexity Depends on the type of Turing machine (or computer) used. Such as number of symbols,
whether tape is infinite in both direction.
We will use time complexity to define “efficiently solvable”. But setting a specific threshold (e.g., 3n5 ) is too
arbitrary, and the meaning of “efficiently solvable” is then either tied to a specific type of Turing machine
(computer) or can change with time (as technology improves).
Polynomial time
A Turing machine M has polynomial time complexity if its time complexity is O(nk), for some fixed k.
tM(n) = O(nk).
The power, k, is fixed. It does not depend on the input. But different polynomial time Turing machines often
have different k’s
