Friday, 6 September 2013

Computational Complexity

One of the main objectives of the the theory of computation is to determine which languages $L$ (as described in the previous section) can be recognized by some circuit family, or equivalently, some Turing machine. Another objective for the theory of computation, that of complexity theory, pertains only to the specific class of problems that are recognizable by some circuit family/Turing machine. Thus, for the rest of this paper, we will only be concerned with those languages (decision problems) that are recognized by some circuit family/Turing machine. Complexity theory is concerned with quantifying computational resources such as  the time and space (memory) needed to perform particular computational tasks. Problems are grouped into complexity classes so that different problems belong to the same complexity class if they share similar resources. Roughly speaking, complexity theory classifies problems according to how hard or easy they are using a certain model of computation, and tries to understand the relationships between various complexity classes.

Since complexity theory is largely concerned with upper bounds on certain behavior, asymptotic or  big-O' notation will be used. If $f$ and $g$ are two functions, write $f(n)=O(g(n))$ if for some positive integer $n_0$ and every $n\geq n_0$, there exists some positive constant $c$ such that $f(n)\leq cg(n)$. That is, for suitably large $n$, the function $f$ is bounded above by $g$ up to some  constant factor. Likewise, in complexity theory, lower bounds are also of interest in regards to limiting behavior. Therefore, big-$\Omega$' notation will also be used to signify when some function is bounded below by another. Formally, write $f(n)=\Omega(g(n))$ if for some positive integer $n_0$ and every $n\geq n_0$, there exists some positive constant $c$ such that $cg(n)\leq f(n)$. Informally, this means that for sufficiently large $n$ the function $f(n)$ is always greater than $g(n)$  up to some  constant factor.

The purpose of big-O' and big-$\Omega$'' notation is to analyze long term behavior and characterize its essential properties. These functions that quantitatively describe the resources needed to perform a computation or solve a problem are generally functions of the size $n$ of the input bitstrings. In this context, some function $f(n)$ describes how the resource requirements change in terms of the input size $n$. Thus, what is meant by "long term behavior" of a particular algorithm is how the amount of resources needed to compute the algorithm grows as the size of the input is made arbitrarily large. Based only off of the resources needed for small input sizes it may not be obvious how the resources grow when the algorithm is run on larger input sizes. Therefore, it is essential and often of great practical importance to understand how a certain algorithm behaves for larger inputs.

The following sections of this section will introduce some relevant complexity classes in the classical context. After the postulates of quantum mechanics are introduced in the next chapter, analogous complexity class for the quantum model of computation will be defined.

Time Complexity

In order to describe the complexity classes relevant for our purposes, define the size of a circuit to be the number of gates that comprise the circuit. Moreover, assume that each logic gate in a circuit can yield an output in some finite amount of time. What this time may really be is a question that is to be determined by the hardware used in the actual physical realization of the logic gate. For the purposes of complexity theory we are not concerned with the precise physical time taken to execute a particular logic gate. Instead, we will assume that each gate is executed by some constant unit time interval. This allows us to reason about different algorithms more abstractly without having to worry about hardware issues. Thus, the time it takes a given circuit to calculate its final output will be proportional to the size of the circuit. Therefore, time complexity can be synonymously thought of as circuit size complexity.

Given a circuit family $\{C_n\}$ that decides a particular language in time given by $O(f(n))$, where $f(n)$ is some function of the size $n$ of the input, we say that the language or problem is in the time complexity class $TIME(f(n))$.  For instance, a problem is said to be solvable in polynomial time if it is in $TIME(n^k)$ for some finite k.

Complexity Class: P

The complexity class $P$  consists of all problems that are in the classes $TIME(n^k)$ for all finite k. That is $P\equiv\bigcup_{k=0}^{\infty}TIME(n^k)$. The class $P$ is generally referred to as deterministic polynomial time, and contains all problems which are considered to be "easy" or "tractable". Thus, problems in $P$ are ones that can be solved efficiently by some circuit family or deterministic Turing machine. For example, the decision problem of testing whether or not a given number is a prime is in the class $P$.

There is one important subtlety that must be addressed so that the equivalence between Turing machines and circuit families remains true relative to the complexity class $P$. Previously, a circuit family $\{C_n\}$ was said to be uniform if there existed a deterministic Turing machine which was able to provide a description of the circuit $C_n$ given $n$ as input. This property is independent of the running time of such a Turing machine. There is a stronger constraint that a circuit family must satisfy if its associated language is to belong in $P$. A circuit family  ${C_n}$ is uniformly polynomial if there exist a Turing machine which can output the description of the circuit $C_n$ in time $O(n^k)$ for some $k$. Therefore,  a problem computed by a uniformly polynomial circuit family  share the same time resources as the same problem computed by a deterministic Turing machine running in polynomial time.

Complexity Class: BPP

The time complexity class analogous to $P$ for randomized circuit families is called $BPP$ (for Bounded-error Probabilistic Polynomial time). A language $L$ is in $BPP$ if there exists a randomized uniformly polynomial circuit family $\{C_n\}$ which can decide the language in a time bounded by some polynomial $O(n^k)$ for some $k$. Equivalently, $BPP$ contains the languages that can be efficiently recognized by a randomized Turing machine with a small probability of error.  Clearly, we have the set inclusion $P\subseteq BPP$ since the languages in $P$ are simply those with a success probability of $1$, but the relation $P=BPP$ remains as an open question for the field. This latter statement would imply that all languages that can be computed probabilistically in polynomial time can also be computed deterministically with certainty.

Complexity Class: NP

The time complexity class $NP$ contains all languages which can be decided by a nondeterministic Turing machine in time that is at most some polynomial $O(n^k)$ for some $k$. Nondeterministic Turing machines can be simulated by deterministic Turing machines, but this simulation generally requires exponentially more time for the deterministic Turing machine compared to its nondeterministic counterpart. Thus, even though some problem may by in $NP$ this may not necessarily imply that the same problem is also in $P$. It seems as if nondeterministic Turing machines may be able to solve some problems faster than deterministic Turing machines.

There is an alternative way to describe the complexity class $NP$ without reference to the notion of nondeterminism. Although it may not be possible for a  deterministic Turing machine or circuit family to solve an instance of a problem in $NP$ in polynomial time, it may be easy for a deterministic Turing machine or circuit family to at least verify a solution if it happened to somehow be given one as input. Now the problems in $NP$ can be equivalently thought about as those problems which permit a particular  solution to be checked or verified by a deterministic Turing machine or uniformly polynomial circuit family running in time bounded by some polynomial $O(n^k)$ for some $k$. This alternate definition of $NP$ is made more formal as follows. Let $L$ be a language in $NP$ and suppose $M(a,b)$ is a function of bitstrings $a$ and $b$ corresponding to some decision problem that can be computed in polynomial time on some deterministic Turing machine. Moreover, let $n$ be the size of some bitstring $x$  and the size of the bitstring $y$ be $m$ such that $m$ is bounded above by some polynomial in terms of $n$. If $x\in L$, then there exists a $y$ such that $M(x,y)=1$, and if $x\not\in L$ then $M(x,y)$ for all $y$. Here, the bitstring $y$ serves as the \emph{certificate} for the verification of a string $x\in L$.

Since solutions to problems in $P$ can be computed in polynomial time, these problems are trivially in $NP$. Hence, $P\subseteq NP$, but the claim that $NP\subseteq P$ or that $P=NP$ remains as one of the biggest open problems for complexity theory and computer science. If $P=NP$ were true, this would essentially imply that that coming up with a solution to a problem is just as easy as verifying that some provided solution is indeed a correct solution for that problem.

As an example, the decision problem associated to factoring an integer is in $NP$. Stated formally, this problem asks: Given integers $N$ and and $m$, does there exist any factors $l$ of $N$ such that $l\leq m$? Since the decision problem of verifying that some potential factor $l$ is indeed a factor of $N$ is in $P$, this implies that the problem of factoring is in $NP$. There is currently no known classical algorithm for a deterministic or randomized Turing machine which can solve the factoring problem in polynomial time. Interestingly enough, as it will be shown in later chapters, there exists an algorithm for quantum computers which can solve the factoring problem in polynomial time with only some probability of error.