Complexity Classes

Determining if a problem is computable at all is interesting, but this distinction is not fine enough to determine if a problem can realistically be solved by a physical computer in a reasonable amount of time. If a computation will take billions of years to compute, it may as well be uncomputable from the perspective of the pragmatist. An algorithm can be characterized by the number of operations and amount of memory it requires to compute an answer given an input of size $N$. These characterizations of the algorithm determine what is called the algorithms complexity. Specifically, the complexity of an algorithm is determined by looking at how the number of operations and memory usage required to complete the program scales with the size of the input of the program. Computer Scientists have grouped problems into the following complexity classes:

P:

Polynomial time, the running time of the given algorithm is in the worst case some polynomial function of the size of the input. For example if an algorithm with an input size of 10 bits which took $10^4 + 7*10^2 + 1001$ operations to compute is a polynomial time algorithm.

NP:

Nondeterministic polynomial time, a candidate for an answer can be verified as a correct answer or not in polynomial time.

NP-complete:

A set of problems such that if any member is in P, the the set P equals the set NP. (Cormen, Leiserson, Rivest)

Problems which can be solved in polynomial time or less are generally deemed to be ``tractable.'' Problems which require more than polynomial time are usually considered to be ``intractable,'' for example an algorithm which would take $2^n$ operations for an input size of $n$ would be considered intractable, as the number of operations grows exponentially with the input size, not polynomially.

It should be noted at this point that in Shor's Algorithm, we will be given $n$, a number to be factored. In $n$'s most compact representation, it will take $\lceil \log n \rceil$ bits to be encoded. When discussing the running time of algorithms, we must always speak in reference to the encoded input size. For Shor's algorithm (or any algorithm whose input is an integer), the ``input size'' grows logarithmically with the value of $n$ to be factored.

A stronger version of the Church-Turing Thesis has been phrased as:

Any physical computing device can be simulated by a Turing machine in a number of steps polynomial in the resources used by the computing device.

As an aside, whether or not P and NP describe the same set of problems is one of the most important open questions in computer science. Should a polynomial time algorithm for any NP-complete problem be discovered, then we would know that P and NP are the same set. Many NP-complete problems have known algorithms which can compute their solutions in exponential time, whether there exists any polynomial time algorithms is unknown.

When discussing the complexity of a problem it is important to distinguish between there being no known algorithm to compute it in polynomial time, and there being no algorithm to compute it in polynomial time. There are many problems whose best known algorithm requires an exponential number of steps to compute a solution. These problems are generally considered to be intractable. Determining the prime factors of a large number is one such problem, and its assumed intractability is the bases for most cryptography.

The interest in quantum computing is twofold. First it is of interest if a quantum computer can solve problems which are uncomputable on a classical computer, and second it is of interest if a quantum computer can make problems thought of as intractable, tractable.