PED Home Page
Recall that a decision problem takes as input a finite length binary string and returns as output a 0 or a 1, hence a decision problem
We measure the running time of an algorithm as the number of steps taken on inputs of length n
That is, if A is an algorithm (ADA program, say) that solves a decision problem, f, the running time of A is a function R : N -> N, so that R( n ) is the worst-case number of steps taken on inputs of length n.
The Time Complexity of a decision problem, f, is the running time of the `best' algorithm A for f.
Thus we say that a decision problem, f, has
Thus we say that a decision problem, f, has
Thus we can define complexity classes, e.g.
TIME ( n ) is the set of decision problems for which an algorithm running in at most n steps on inputs of length n exists.
TIME ( n^2 ) is the set of decision problems for which an algorithm running in at most n^2 steps on inputs of length n exists.
TIME ( 2^n ) is the set of decision problems for which an algorithm running in at most 2^n steps on inputs of length n exists.
And in general,
Which complexity classes correspond to decision problems with `efficient' (for run-time) algorithms?
Intuitively we regard an algorithm with worst-case run-time of n, n^2, n^3, etc as being `efficient' since the time taken to return an answer for input of length n is `acceptable' even for large values of n; and the amount of additional computation needed for inputs of length n+1 does not `greatly exceed' the time on inputs of length n.
On the other hand, intuitively, we would regard an algorithm with worst-case run-time of 2^n, 3^n, n^n, n, n^{logn}, etc as being `inefficient' since even for moderate values of n the time taken to return an answer on input of length n is `unacceptable'; and the amount of additional computation needed for inputs of length n+1 considerably exceeds the time on inputs of length n.
How can we distinguish run-times in the second category from run-times in the first?
All of the run-times in the first category have the following property:
For each `efficient' run-time there is a constant, k, such that the running time is at most n^k when n is large enough.
A decision problem, f, for which there is an algorithm taking at most n^k steps on inputs of length n (i.e. f in TIME ( n^k )) is called a
For each `inefficient' run-time there is NO constant, k, such that the running time is at most n^k when n is large enough.
A decision problem, f, for which there is NO algorithm taking at most n^k steps on inputs of length n (i.e. f is not in TIME ( n^k )) is called a
There are very few `natural' examples of decision problems for which such lower bounds have been proved.
A major open problem in Computational Complexity Theory is to develop arguments by which important computational problems can have their time complexity described exactly.
For `almost all' `interesting' problems no lower bound on Time Complexity larger than OMEGA( n ) has been obtained.
Example Open Problems
We have seen that multiplication of 2 n-digit numbers has Time Complexity at worst n^{log3}. It is conjectured that
Multiplication of 2 n by n integer matrices can be done in time O(N^1.81) (where N = n^2). It is conjectured that
It is unknown whether there is a polynomial time algorithm that can determine if a given n-digit number is a Prime Number.
It is unknown whether there is a polynomial time algorithm that will factorise an n digit number.
Computational Complexity Theory involves a large number of subfields each of which is ultimately concerned with problems such as those above, e.g.
The study of the last field is over 50 years old.
It is convenient to use a single symbol to denote the class of all decision problems for which time efficient algorithms exist.
P = { f : f has a polynomial time algorithm }
= Union over all k TIME ( n^k )