随机算法 (Fall 2011)/Complexity Classes

Upper bounds, lower bounds

Bounds are just inequalities (in a general sense, e.g. asymptotic inequalities). An inequality

[math]\displaystyle{ A\le B }[/math]

is read "[math]\displaystyle{ A }[/math] is a lower bound of [math]\displaystyle{ B }[/math]" or equivalently "[math]\displaystyle{ B }[/math] is an upper bound of [math]\displaystyle{ A }[/math]".

In Computer Science, when talking about upper or lower bounds, people really mean the upper or lower bounds of complexities.

In this lecture, we are focused on the time complexity, although there are other complexity measures in various computational models (e.g. space complexity, communication complexity, query complexity).

The complexity is represented as a function of [math]\displaystyle{ n }[/math], where [math]\displaystyle{ n }[/math] is the length of the input.

There are two kinds of complexities:

Complexity of algorithms

For an algorithm [math]\displaystyle{ A }[/math], the (worst-case) time complexity of [math]\displaystyle{ A }[/math] is the maximum running time over all inputs [math]\displaystyle{ x }[/math] of length [math]\displaystyle{ n }[/math].

Complexity of problems

For a computational problem, its time complexity is the time complexity of the optimal algorithm which solves the problem.

The complexity of an algorithm tells how good the algorithm is, yet the complexity of a problems tells how hard the problem is. While the former is what we care mostly about in practice, the later is more about the fundamental truths of computation.

In Theoretical Computer Science, when talking about upper or lower bounds, people usually refer to the bounds of the complexities of problems, rather than those of algorithms. Therefore, an upper bound means an algorithm; and a lower bound means bad news such as impossibility results.

Today's lecture is devoted to lower bounds, i.e. the necessary prices which have to paid by any algorithms which solve the given problems. Speaking of necessary prices, we have to be specific about the model, the mathematical rules which stipulate what is problem and what is algorithm.

Decision problems

Computational problems are functions mapping inputs to outputs. Sometimes, an input is called an instance of the problem and an output is called a solution to that instance. The theory of complexity deals almost exclusively with decision problems, the computational problems with yes-or-no answers.

For a decision problem [math]\displaystyle{ f }[/math], its positive instances are the inputs with "yes" answers. A decision problem can be equivalently represented as the set of all positive instances, denoted [math]\displaystyle{ L }[/math]. We call [math]\displaystyle{ L }[/math] a formal language (not entirely the same thing as the c language). The task of computing [math]\displaystyle{ f(x) }[/math] is equivalent to that of determining whether [math]\displaystyle{ x\in L }[/math]. Therefore the two formulations of "decision problems" and "formal languages" can be interchangeably used.

Turing Machine

In order to study complexities, which deal with the limits of computations, we have to be clear about what computation is, that is, modeling computations.

This work was done by Alan Turing in 1937. The model is now referred by the name Turing machine.

Complexity Classes

Problems are organized into classes according to their complexity in respective computational models. There are nearly 500 classes collected by the Complexity Zoo.

P, NP

A deterministic algorithm [math]\displaystyle{ A }[/math] is polynomial time if its running time is within a polynomial of [math]\displaystyle{ n }[/math] on any input of length [math]\displaystyle{ n }[/math].

Definition (P)

The class P is the class of decision problems that can be computed by polynomial time algorithms.

We now introduce the infamous NP class.

Definition (NP)

The class NP consists of all decision problems [math]\displaystyle{ f }[/math] that have a polynomial time algorithm [math]\displaystyle{ A }[/math] such that for any input [math]\displaystyle{ x }[/math], [math]\displaystyle{ f(x)=1 }[/math] if and only if [math]\displaystyle{ \exists y }[/math], [math]\displaystyle{ A(x,y)=1 }[/math], where the size of [math]\displaystyle{ y }[/math] is within polynomial of the size of [math]\displaystyle{ x }[/math]

Informally, NP is the class of decision problems that the "yes" instances can be verified in polynomial time. The string [math]\displaystyle{ y }[/math] in the definition is called a certificate or a witness. Provided a polynomial size certificate, the algorithm [math]\displaystyle{ A }[/math] verifies (instead of computing) the [math]\displaystyle{ f(x) }[/math] for any positive instance [math]\displaystyle{ x }[/math] in polynomial time.

Example

Both the problems of deciding whether an input array is sorted and deciding whether an input graph has Hamiltonian cycles are in NP. For the former one, the input array itself is a certificate. And for the later one, a Hamiltonian cycle in the graph is a certificate (given a cycle, it is easy to verify whether it is Hamiltonian).

This definition is one of the equivalent definitions of the NP class. Another definition (also a classic one) is that NP is the class of decision problems that can be computed by polynomial time nondeterministic algorithms.

Common misuses of the terminology:

• "This algorithm is NP." --- NP is a class of decision problems, not algorithms.
• "This problem is a NP problem, so it must be very hard." --- By definition, a problem is in NP if its positive instances are poly-time verifiable, which implies nothing about the hardness. You probably means the problem is NP-hard.
• "NP problems are the hardest problems." --- There are infinitely many harder problems outside NP. Actually, according to a widely believed conjecture, there are infinitely many classes of problems which are harder than NP (see [1]).

Note that unlike P, the definition of NP is asymmetric. It only requires the positive instances (the [math]\displaystyle{ x }[/math] that [math]\displaystyle{ f(x)=1 }[/math]) to be poly-time verifiable, but does not say anything about the negative instances. The class for that case is co-NP.

Definition (co-NP)

The class co-NP consists of all decision problems [math]\displaystyle{ f }[/math] that have a polynomial time algorithm [math]\displaystyle{ A }[/math] such that for any input [math]\displaystyle{ x }[/math], [math]\displaystyle{ f(x)=0 }[/math] if and only if [math]\displaystyle{ \exists y }[/math], [math]\displaystyle{ A(x,y)=0 }[/math], where the size of [math]\displaystyle{ y }[/math] is within polynomial of the size of [math]\displaystyle{ x }[/math]

Clearly, P [math]\displaystyle{ \subseteq }[/math] NP [math]\displaystyle{ \cap }[/math] co-NP. Does P = NP [math]\displaystyle{ \cap }[/math] co-NP? It is an important open problem in the complexity theory which is closely related to our understanding of the relation between NP and P.

ZPP, RP, BPP

Now we proceeds to define complexity classes of the problems that is efficiently computable by the randomized algorithms, i.e. the randomized analogs of P.

In the last class we learned that there are two types of randomized algorithms: Monte Carlo algorithms (randomized algorithms with erros) and Las Vegas algorithms (randomized algorithms with random running time but with no erros). For Monte Carlo algorithms, there are two types of errors: one-sided errors where the algorithm errs only for positive instances, and two-sided errors where there are both false positives and false negatives. Therefore, there are three cases to deal with:

1. Las Vegas algorithms, the corresponding class is ZPP (for Zero-error Probabilistic Polynomial time).
2. Monte Carlo algorithms with one-sided error, the corresponding class is RP (for Randomized Polynomial time).
3. Monte Carlo algorithms with two-sided error, the corresponding class is BPP (for Bounded-error Probabilistic Polynomial time).

We first introduce the class ZPP of the problems which can be solved by polynomial time Las Vegas algorithms. For Las Vegas algorithms, the running time is a random variable, therefore we actually refer to the Las Vegas algorithms whose expected running time is within a polynomial of [math]\displaystyle{ n }[/math] for any input of size [math]\displaystyle{ n }[/math], where the expectation is taken over the internal randomness (coin flippings) of the algorithm.

Definition (ZPP)

The class ZPP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in expected polynomial time for any input such that for any input [math]\displaystyle{ x }[/math], [math]\displaystyle{ A(x)=f(x) }[/math].

Next we define the class RP of the problems which can be solved by polynomial time Monte Carlo algorithms with one-sided error.

Definition (RP)

The class RP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in worst-case polynomial time such that for any input [math]\displaystyle{ x }[/math], if [math]\displaystyle{ f(x)=1 }[/math], then [math]\displaystyle{ \Pr[A(x)=1]\ge 1-1/2 }[/math]; if [math]\displaystyle{ f(x)=0 }[/math], then [math]\displaystyle{ \Pr[A(x)=0]=1 }[/math].

Remark

The choice of the error probability is arbitrary. In fact, replacing the 1/2 with any constant [math]\displaystyle{ 0\lt p\lt 1 }[/math] will not change the definition of RP.

Example

Define the decision version of the minimum cut problem as follows. For a graph [math]\displaystyle{ G }[/math], [math]\displaystyle{ f(G)=1 }[/math] if and only if there exists any cut of size smaller than [math]\displaystyle{ k }[/math], where [math]\displaystyle{ k }[/math] is an arbitrary parameter. The problem [math]\displaystyle{ f }[/math] can be solved probabilistically by Karger's min-cut algorithm in polynomial time. The error is one-sided, because if there does not exists any cut of size smaller than [math]\displaystyle{ k }[/math], then obviously the algorithm cannot find any. Therefore [math]\displaystyle{ f\in }[/math]RP.

Like NP, the class RP is also asymmetrically defined, which hints us to define the co-RP class.

Definition (co-RP)

The class co-RP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in worst-case polynomial time such that for any input [math]\displaystyle{ x }[/math], if [math]\displaystyle{ f(x)=1 }[/math], then [math]\displaystyle{ \Pr[A(x)=1]= 1 }[/math]; if [math]\displaystyle{ f(x)=0 }[/math], then [math]\displaystyle{ \Pr[A(x)=0]\ge 1-1/2 }[/math].

We then define the class BPP of the problems which can be solved by polynomial time Monte Carlo algorithms with two-sided error.

Definition (BPP)

The class BPP consists of all decision problems [math]\displaystyle{ f }[/math] that have a randomized algorithm [math]\displaystyle{ A }[/math] running in worst-case polynomial time such that for any input [math]\displaystyle{ x }[/math], if [math]\displaystyle{ f(x)=1 }[/math], then [math]\displaystyle{ \Pr[A(x)=1]\ge 1-1/4 }[/math]; if [math]\displaystyle{ f(x)=0 }[/math], then [math]\displaystyle{ \Pr[A(x)=0]\ge 1-1/4 }[/math].

Remark

Replacing the error probability from [math]\displaystyle{ \frac{1}{4} }[/math] to [math]\displaystyle{ \frac{1}{3} }[/math], or any constant [math]\displaystyle{ 0\lt p\lt \frac{1}{2} }[/math] will not change the definition of the BPP class.

---

What is known (you can even prove by yourself):

• RP, BPP, ZPP all contain P
• RP [math]\displaystyle{ \subseteq }[/math] NP
• ZPP = RP[math]\displaystyle{ \cap }[/math]co-RP;
• RP [math]\displaystyle{ \subseteq }[/math] BPP;
• co-RP [math]\displaystyle{ \subseteq }[/math] BPP.

Open problem:

• BPP vs P (the second most important open problem in the complexity theory to the NP vs P).