======================================================================
=                  Computational complexity theory                   =
======================================================================

                             Introduction
======================================================================
Computational complexity theory focuses on classifying computational
problems according to their inherent difficulty, and relating these
classes to each other. A computational problem is a task solved by a
computer. A computation problem is solvable by mechanical application
of mathematical steps, such as an algorithm.

A problem is regarded as inherently difficult if its solution requires
significant resources, whatever the algorithm used. The theory
formalizes this intuition, by introducing mathematical models of
computation to study these problems and quantifying their
computational complexity, i.e., the amount of resources needed to
solve them, such as time and storage. Other measures of complexity are
also used, such as the amount of communication (used in communication
complexity), the number of gates in a circuit (used in circuit
complexity) and the number of processors (used in parallel computing).
One of the roles of computational complexity theory is to determine
the practical limits on what computers can and cannot do. The P versus
NP problem, one of the seven Millennium Prize Problems, is dedicated
to the field of computational complexity.

Closely related fields in theoretical computer science are analysis of
algorithms and computability theory. A key distinction between
analysis of algorithms and computational complexity theory is that the
former is devoted to analyzing the amount of resources needed by a
particular algorithm to solve a problem, whereas the latter asks a
more general question about all possible algorithms that could be used
to solve the same problem. More precisely, computational complexity
theory tries to classify problems that can or cannot be solved with
appropriately restricted resources. In turn, imposing restrictions on
the available resources is what distinguishes computational complexity
from computability theory: the latter theory asks what kind of
problems can, in principle, be solved algorithmically.


                        Computational problems
======================================================================
A traveling salesman tour through 14 German cities.


 Problem instances
===================
A computational problem can be viewed as an infinite collection of
'instances' together with a 'solution' for every instance. The input
string for a computational problem is referred to as a problem
instance, and should not be confused with the problem itself. In
computational complexity theory, a problem refers to the abstract
question to be solved. In contrast, an instance of this problem is a
rather concrete utterance, which can serve as the input for a decision
problem. For example, consider the problem of primality testing. The
instance is a number (e.g., 15) and the solution is "yes" if the
number is prime and "no" otherwise (in this case, 15 is not prime and
the answer is "no"). Stated another way, the 'instance' is a
particular input to the problem, and the 'solution' is the output
corresponding to the given input.

To further highlight the difference between a problem and an instance,
consider the following instance of the decision version of the
traveling salesman problem: Is there a route of at most 2000
kilometres passing through all of Germany's 15 largest cities? The
quantitative answer to this particular problem instance is of little
use for solving other instances of the problem, such as asking for a
round trip through all sites in Milan whose total length is at most 10
km. For this reason, complexity theory addresses computational
problems and not particular problem instances.


 Representing problem instances
================================
When considering computational problems, a problem instance is a
string over an alphabet. Usually, the alphabet is taken to be the
binary alphabet (i.e., the set {0,1}), and thus the strings are
bitstrings. As in a real-world computer, mathematical objects other
than bitstrings must be suitably encoded. For example, integers can be
represented in binary notation, and graphs can be encoded directly via
their adjacency matrices, or by encoding their adjacency lists in
binary.

Even though some proofs of complexity-theoretic theorems regularly
assume some concrete choice of input encoding, one tries to keep the
discussion abstract enough to be independent of the choice of
encoding. This can be achieved by ensuring that different
representations can be transformed into each other efficiently.


 Decision problems as formal languages
=======================================
Decision problems are one of the central objects of study in
computational complexity theory. A decision problem is a special type
of computational problem whose answer is either 'yes' or 'no', or
alternately either 1 or 0. A decision problem can be viewed as a
formal language, where the members of the language are instances whose
output is yes, and the non-members are those instances whose output is
no. The objective is to decide, with the aid of an algorithm, whether
a given input string is a member of the formal language under
consideration. If the algorithm deciding this problem returns the
answer 'yes', the algorithm is said to accept the input string,
otherwise it is said to reject the input.

An example of a decision problem is the following. The input is an
arbitrary graph. The problem consists in deciding whether the given
graph is connected or not. The formal language associated with this