Introduction to Complexity Theory

### Computational Complexity Theory

Computability Theory is concerned with the question

### For which decision problems do algorithms exist

Computational Complexity Theory is concerned with the question

### For which decision problems do efficient algorithms exist

This raises the questions:
• What `resources' do we wish to be employed `efficiently'
• What do we mean by `efficient'?
The two significant `resources' (or complexity measures) of interest are

and

### SPACE

i.e. The number of steps an algorithm takes (in the worst-case) to return its answer. The amount of memory needed in which to run the algorithm.

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

### f : { 0, 1 }^* -> { 0, 1 }

may be seen as an infinite sequence of decision problems [fn], where

### fn : { 0, 1 }^n -> { 0, 1 }

is the problem f limited to inputs containing exactly n bits.

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

### Time ComplexityT( n )

if there is an an algorithm, A, for f such that

### The number of steps taken by A on inputs of length n is always less than or equal to T( n )

The Space Complexity of a decision problem, f, is the amount of memory used by the `best' algorithm A for f.

Thus we say that a decision problem, f, has

### Space ComplexityS( n )

if there is an an algorithm, A, for f such that

### The number of memory locations used by A on inputs of length n is always less than or equal to S( n )

These definitions allow us to classify decision problems according to their Time (Space) Complexity.

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,

### TIME ( T(n) )

is the set of decision problems for which an algorithm running in at most T(n) steps on all inputs of length n exists.

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

### Polynomial Time Complexity Decision Problem

All of the run-times in the second category do not have this property, i. e.

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

### Non-Polynomial Time Complexity Decision Problem

It is possible to show (by diagonalisation) that for all run-time functions, T(n):

### There exist decision problems, f, such that the Time-Complexity of f is greater than T(n)

(thus there are decision problems which do have non-polynomial time complexity)

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 is in TIME( n log n )

This conjecture remains unproven.

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

### Matrix-Multiplication is in TIME( N log N )

Again this remains unproven.

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.

### Complexity Theory of Boolean Functions

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 )
``` PED Home Page