- What `resources' do we wish to be employed `efficiently'
- What do we mean by `efficient'?

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 )