Chapter 7. Complexity concepts

Because of its generality and uniformity, the model of Turing machines can be used for observations in several algorithm related questions. For example, with the help of it, one can express the complexity of tasks.

In general, we call a task difficult, if its solution requires operations, which are hard to understand, unusual or it exceeds our abilities. However, a computer has no such problems, if the solution is programmed properly. Thus, from the viewpoint of algorithms, we have to reconsider the concept of difficulty. If we expect an answer from a computer, then the only thing we can sense about the "problems" of it, if we have to wait too long. We will express the this property (and some other) by the use of Turing machines.

7.1. Time, space and program complexity

First we define the time, space and program complexity of deterministic and nondetreministic Turing machines. Using these concepts we are able to express the different resource needs of algorithms (Turing machines).

Since usually an algorithm is not for solving a particular task but a class of tasks, thus we have to be able to express the resource needs for the complete class of tasks.

The most important complexity concept is time complexity.

Definition 7.1.

Let  be a deterministic Turing machine and let  be a word. Furthermore,
let be the computation of  on the input . 
Assume, that there exists  such that  is a final configuration.
The least such a value for  is called the length of the computation. 
If such  exists, then we say that the computation is infinite. 
The notation  for the length of the computation of the Turing machine  on 
the input word  is:  or .

The length of a computation is used as the expression of running time, without telling anything about the concept of time resource. Hence we can define the general time needs of a Turing machine.

Definition 7.2.

Let  be a deterministic Turing machine. 
The time complexity of  is the function , where 

         

If it causes no confusion, we may omit the symbol of the Turing machine from the notation of time complexity.

The time complexity, defined above, expresses what is the length of computation for a given Turing machine on bounded size input words in the worst case. This is why it is sometimes called the worst case complexity.

One may define the average case complexity, too. It is more expressive from the view point of standard programming, but in general it is much more difficult to compute. It is necessary to know some kind of distribution of input data, which is usually not obvious.

Remark 7.3.

If a Turing machine has well defined time complexity for all
, then it terminates on all input, i.e. the recognized language
is recursive. 

Remark 7.4.

Let  be a deterministic Turing machine with time complexity . The
value  is the length of the longest computation on an input word
not longer than , while the value  is the length of the 
longest computation on an input word not longer than . 
Since the latter case includes all input words from the previous one, 
thus . 
It means that the function  is monotone increasing.

By a similar approach one may define the space needs of an algorithm (Turing machine).

Definition 7.5.

Let  be a deterministic Turing machine and let  be a word. Furthemore, 
let  be the computation of  on the input . 
Assume, that  and let .
If there exists, the value  is called the space needs of the computation.
If no such value exists, the space needs is called infinite. 
The space needs of the computation of on the input  is denoted by .

Using the concept of space needs one may define space complexity

Definition 7.6.

Let  be a deterministic Turing machine. The space complexity of 
is the function , where 
         

The notation of the Turing machine can be omitted here, too, if it causes no confusion.

Similarly as in the case of time complexity one may have the following remark.

Remark 7.7.

Let  be a deterministic Turing machine and let  beits space complexity.
The value  is the largest space needs on input word of length at most ,
while the value  is the largest space needs on input word of length 
at most . Since the latter case includes all input words from the previous 
one, thus . This means that  is monotone increasing.

Finally one can define the complexity of a Turing machine itself.

Definition 7.8.

Let  be a deterministic Turing machine and let  be its program. The 
program complexity of  is the value .

Remark 7.9.

By Definition 7.8., the program complexity does not depend on
the length of the input word. However, the implementation of 
an algorithm (which is a program) may depend. If the size of the input
is above a limit, then the program may need another structure,
to handle system memory, accessing the input, etc.

Similarly to the deterministic case one can define time and space complexity for nondeterministic Turing machines, too. However, since the general definitions are less expressive, we introduce them only for acceptor Turing machines.

Definition 7.10.

Let  be a nondeterministic acceptor Turing machine and let  be 
a word. Assume that there exists a computation of  on the input ,
which terminates in an acceptin state. The length of the shortes
accepting computation is called the length of the computaiton. 
If there are no computation terminating in an accepting state, then
the length of the computation is infinite. 
Similarly as in the deterministic case, the length of the computation
of  on the input  is denoted by .

For nondeterministic Turing machines, the length of the computation is defined only for input words, which are accepted by the Turing machine. Thus the definition of time complexity should be changed, too.

Definition 7.11.

Let  be a nondeterministic Turing machine. 
The time complexity of  is the function , where
.

The space complexity of nondeterministic Turing machines is the following.

Definition 7.12.

Let  be a nondeterministic acceptor Turing machine and let  be 
a word. Assume that  has a computation, which terminates in an 
accepting state on the input . 
Let  be a possible computation of  on the input , 
which terminates in ana ccepting state. Assume that  
and let .
The space need of the computation  is .
The least space need of the possible computations on the input 
word  is called the space need of the computation. 
If there are no accepting computation, then the space need is 
infinite. 
The space need of  on the input  is denoted by .

As in the case of time complexity, the space need is defined only for input words, which are accepted by the Turing machine. Thus the space complexity requires some modification, too.

Definition 7.13.

Let  be a nondeterministic Turing machine. 
The space complexity of  is a function , where

         

The following theorem is some additional property of recursive languages. It says, if a language is recursively enumerable and its time complexity is not too big, then the language is recursive. Reversing the statement, if a language is not recursive and there exists a Turing machine which accepts it, then its time complexity (function) is uncomputable big. It yields some really fast increasing function, since the Ackermann function is still computable.

Theorem 7.14.

Let  be a language. Assume that ther exists a function , 
which can be computed by a Turing machine and let  be a 
deterministic Turing machine, such that . 
If  terminates on the members of  after at most  
steps, then .

Proof

Let be the Turing machine, which computes , i.e. and let be the limited time Turing machine created from , as we have seen before. Using these Turing machines, compose the following:

1. According to the input , the new Turing machine writes a sequence of 's of length to tape .

2. Start on the input word . If during the computation the part corresponding to terminates, then its decision is the actual decision. If the limiting part terminates first, then the answer is "no".

Clearly the Turing machine terminates on every input word and it accepts an input word if and only if it is accepted by . This is because if accepts it, then the length of computation is not more than . By definition, it means . ✓