Complexity Theory

Overview

Complexity theory deals with how efficiently problems can be solved. Even though a problem is decidable, it may not be possible to solve in a reasonable amount of time for large input sizes.

Complexity theory includes techniques to quantify the running time of algorithms, as well as the classification of different problems according to how much running time is required.

Measuring Complexity

Consider the language $A = \{0^k1^k\; |\; k \ge 0\}$. This is a decidable problem. The following Turing machine decides $A$:

$M_1 =$ "On input string $w$:

Scan right across the tape an reject if a 0 is found after a 1.
Repeat if both 0s and 1s remain on the tape:
1. Scan across the tape, crossing off a single 0 and a single 1.
If any 0s or 1s remain, reject.
Otherwise, accept.

How long this algorithm takes to execute will depend on the length of $w$. We often call the length of the input $n$ and say that the running time or time complexity of the algorithm is some function of $f(n)$.

What is $f(n)$ for the above algorithm?

Estimating Complexity

Describing the time complexity of an algorithm with an exact function is rarely done. There are several reasons for this:

Usually algorithms are expressed at a higher level than the computer system they are actually run on. So the number of steps in the algorithm may not correspond to the number that are actually executed.
For long or complex algorithms, counting steps will be very tedious.
The detailed function is rarely useful in practice; estimations suffice.

Instead we will talk about how the number of steps scale as $n$ increases. Big-O notation is used to express this concept mathematically.

Big-O Notation

We do this with Big-O notation which considers only the highest order term of a complexity function, disregarding the co-efficient as well as any lower order terms.

For example, $f(n) = 3n^3 + n^2 + 20n + 36$ would be estimated as just $n^3$. This is written as $f(n) = \mathcal O(n^3)$.

Formally, Big-O notation is defined as follows:

Let $f$ and $g$ be functions of $n$. We say that $f(n) = \mathcal O(g(n))$ if there exist positive integers $c$ and $n_0$ such that $f(n) \le c \times g(n)$ for all $n \ge n_0$.

If we say that$f(n) = \mathcal O(g(n))$, it means that for some constant, all values of that constant times $g(n)$ will be greater than $f(n)$ for sufficiently large values of $n$.

Big-O analysis is often called asymptotic analysis as it is concerned with how functions behave for large input values.

Analyzing Algorithms

The algorithm for deciding $\{0^k1^k\; |\; k \ge 0\}$ is given again below:

$M_1 =$ "On input string $w$:

Scan right across the tape an reject if a 0 is found after a 1.
Repeat if both 0s and 1s remain on the tape:
1. Scan across the tape, crossing off a single 0 and a single 1.
If any 0s or 1s remain, reject.
Otherwise, accept.

To determine the complexity of this algorithm, we look over the description and consider how the number of steps increases as the input size increases. Does it remain constant? Double? Increase more?

How would we write the complexity using Big-O?

Complexity Classes

A complexity class defines a group of languages that can be decided with algorithms of a certain complexity. Complexity classes allow us to quantify "easy" problems and "hard" ones.

We say that $TIME(t(n))$ is the set of all languages that are decided by $O(t(n))$ Turing machines.

Because the language $A = \{0^k1^k\; |\; k \ge 0\}$ is decided by the $\mathcal O(n^2)$ Turing machine above, we say that $A \in TIME(n^2)$.

A common question is whether there is another Turing machine which decides a given language asymptotically more efficiently.

Note that a Turing machine that decides $A$ two times or even one hundred times faster than $M_1$ does not change the complexity class as that only changes the co-efficient of the complexity function.

It turns out there is an algorithm which decides $A$ more efficiently than $M_1$. That machine is given below:

$M_2 =$ "On input string $w$:

Scan across the tape and reject if a 0 is found after a 1.
Repeat as long as some 0s and some 1s remain on the tape:
1. Scan across the tape, checking whether the total number of 0s and 1s is even or odd. If it is odd, reject.
2. Scan across the tape, crossing off every other 0 starting with the first 0.
3. Scan across the tape, crossing off every other 1 starting with the first 1.
If any 0s or 1s remain, reject.
Otherwise accept.

What is the complexity of this algorithm? What complexity class does that put $A$ in?