CSC 341: April 27, 2007
From CSWiki
Contents |
Instructor's notes for the class session
Time complexity functions and classes
Let M be any Turing machine that halts on every input. Let t(n) be the greatest number of transitions that M makes before halting on any input of length n. The function t is the time complexity function for M.
For any function 
, there is a time complexity class TIME(f(n)). A language L is a member of this class if, and only if, a Turing machine with a time complexity function that is O(f(n)) decides L.
Time complexity depends both on the particular design of the automaton used and on the system of encoding used for the input. If these are unspecified, it is more or less standard to assume a deterministic Turing machine with a single, one-dimensional tape, extending infinitely rightwards, and a single read/write head, and an input alphabet comprising at least two symbols.
The relationships between time-complexity functions for different models of computation can be formulated precisely and studied mathematically. For instance, Sipser proves that, for every multitape Turing machine with time complexity function t, there is a single-tape Turing machine with a time complexity function that is O(t2(n)) (Theorem 7.8).
Non-determinism appears to make an even larger difference: For every single-tape, nondeterministic Turing machine with time complexity function t, there is a single-tape, deterministic tape Turing machine with a time complexity function that is 2O(t(n)) (Theorem 7.11).
Polynomial-time complexity
The polynomial-time complexity class P is the grand union, over all natural numbers k, of the time complexity classes TIME(nk). In other words, a language L is a member of P if, and only if, there is a Turing machine that decides L and has a polynomial time complexity function (or a time complexity function that is bounded above by some polynomial).
Many familiar languages, including all context-free languages, are members of P. (Sipser offers 
as a non-context-free language that is also a member of P.) Languages that are not decidable at all are, of course, not members of P.
There are many languages that are known to be decidable, but not known either to be members of P or to be non-members of P. These languages correspond to problems for which (1) algorithmic solutions have been discovered, and (2) all the known algorithms have time complexity functions that increase faster than any polynomial, but (3) the possibility of a different algorithm with a polynomial time complexity function has never been disproven.
Study questions
- Prove that every regular language is a member of the TIME(n) complexity class.
- Prove that the set FIBO of binary numerals that denote elements of the Fibonacci sequence is a member of P.
Proposed Solutions
- Every regular language is recognized by a DFA. A DFA can be simulated by a TM that only moves rightward on its input, so each symbol on the tape of such a TM would be seen only once, and that's how we know that every regular language is an element of the TIME(n) complexity class.
- To be a member of P, a set must be decidable in polynomial time, or essentially have a Turing-machine that accepts it.
Turing-machine F , described below decides FIBO.
F = “On input string w:
1. Scan across the tape and determine what natural number is represented by the binary sequence.
2. Repeat:
* Find the next number in the Fibonacci sequence (initialized to starting at 1).
* If the current value is equal to our input, accept. If it is greater than our input, reject.
Now we must show that each step runs in polynomial time. Step 1 takes n time, so it is fine. Numbers in the Fibonacci sequence increase exponentially, so how far into the Fibonacci sequence we must search increases logarithmically in relation to the length of the input. So step 2 will run in polynomial time. Therefore F is a member of P.
