Petting Zoo
From Qwiki
Under construction! Once finished, the Petting Zoo will introduce complexity theory to newcomers unready for the terrifying and complex beasts lurking in the main zoo. It will be a gentler source of information about major complexity classes, problems, and reductions. It is meant to be self-contained and does not require previous knowledge of complexity theory.
Terminology
To understand what is going on here in the complexity zoo, there is some terminology that you need to be comfortable with. You may skip over any term explained here if you think you are comfortable with it.
Alphabet
An alphabet Σ is a finite set of character(s). For example {a, b, ..., z }, { 0, 1, ..., 9}, {a, b, ..., z, 0, 1, ..., 9}, { 0, 1}, {1}, etc.
Word
Given an alphabet Σ, a word w is any string whose characters are in Σ. Examples of valid words over the alphabet {a, b, ..., z} are "word", "science", "kqtdnb" and "complexityzoo".
Language
A Language is a set of words over a given alphabet. For example we could define the language L1 to be the set {word, science, kqydnrp, complexityzoo}. A language could contain a finite or infinite number of words. We could define the language ODD which contains words over the alphabet { 0, 1, ..., 9} as ODD={w : w is an odd number} = {1, 3, 5, 7, ..., 19, 21, 23, ...}.
Turing Machine
A Turing machine is a theoretical computer model that has an infinite length tape, for scratch work when computing, and a read/write head that can move left or right to any point on the tape. A Turing machine may have multiple tapes, but additional tapes do not give it any extra computational power, although it might make the process of computation more convenient.
A Turing machine also has a finite set of states Q and a transition function δ, which tells the machine which state to move to given a current state and a character. You may think of the states and the transition function as the engine behind the Turing machine. There is one start state q0 where computation begins, an accept state qaccept and a reject state qreject. Whenever computation reaches the accept state, the machine halts and accepts the input string and when computation reaches the reject state, the machine halts and rejects the input string.
Given an input, which is a string made up of characters of the Turing machine's alphabet Σ, the Turing machine starts in state q0 and reads the characters of the strings in sequence and moves from state to state based on the character read and the current state.
We say that a Turing machine M recognizes a language L if M reaches the accept state if and only if the input is in the language L. Furthermore, a language is Turing recognizable if there exists a Turing machine that recognizes it. For example ODD is turing recognizable because we can construct a turing machine that accepts words in ODD and rejects all other words not in ODD.
A Turing machine is a very powerful model which can do any task a real computer can do.
Non-deterministic Turing Machine
What we just described is a deterministic turing machine. This is because given any current state and a character of the input word, the turing machine can move to one and only one possible state.
However, in the same situation, a non-deterministic turing machine could have zero, one, or more than one possible states it can choose to move to. This means that on any given word w, a non-deterministic Turing machine has many different computational paths to choose from. If any of these paths leads to the accept state (even if some of the other paths leads to the reject state) the Turing machine accepts the word. The non-deterministic Turing machine does not have to check all the possible computational paths because, if there exists an accepting computation path for a word, the non-deterministic Turing machine will "guess" correctly on each character of the input word which branch to follow in order to reach the accepting state.
This feature of the non-deternimistic Turing machine gives it the ability to compute faster than (or at least as fast as) a deterministic Turing machine. However, this does not give the non-deterministic Turing machine any computational advantage over the deterministic Turing machine because for every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine which recognizes the same language that the non-deterministic Turing machine recognizes. A deterministic turing machine is a special case of a non-deterministic Turing machine. This means that trivially, there is a non-deterministic Turing machine for every deterministic Turing machine (i.e., the same one).
Complexity Classes
A complexity class is a set of languages that share some property. For the most part, the shared property is described in terms of the amount of resources, such as time and memory (or space), needed by a Turing machine to accept words in languages in the class.
P NP DTIME(f(n)) DSPACE(f(n) coNP PSPACE EXP NEXP L NL PP BPP RP ZPP BQP IP AM MA PH P/poly SZK QMA NC #P FP
P: Polynomial Time
P stands for polynomial time, and it represents the set of languages that can be recognized by a deterministic Turing machine within p(n) steps where p is a polynomial function and n is the size of the input. This means that for any language L in P, there is a deterministic Turing Machine that will accept only words in L in nk steps or less, where k is a constant.
NP: Non-deterministic Polynomial Time
NP stands for non-deterministic polynomial time, and it represents the set of languages that can be recognized by a non-deterministic Turing machine within p(n) steps where p is a polynomial function and n is the size of the input.
It is obvious that any language L in P is also in NP because a deterministic Turing machine is also a non-deterministic Turing machine. If there exists a deterministic Turing machine M that accepts words in L in polynomial time, then the same turing machine M is a non-deterministic Turing machine that accepts words in L in polynomial time.
However, it is not known whether every language in NP is also in P. This is arguably the biggest unsolved problem in the field of complexity theory.
PP: Probabilistic Polynomial Time
Motivation: While an efficient randomized algorithm for primality testing had been known since the mid-1970's, it was not until 2002 whether an efficient deterministic algorithm even existed (there did). Is this true an general -- does every problem with an efficient randomized algorithm, also have an efficient deterministic counterpart? Or are randomized algorithms inherently more powerful than deterministic ones? In other words, what kind of relationships can we discover once we introduce randomization into our models of computation?
Definition: PP is the class of decision problems solvable in polynomial time by a probabilistic Turing machine M, with error less than 1/2.
However, note that PP is not truly a good notion of efficient randomized computation: a PP algorithm is free to accept with probability 1/2 + ε (say, ε = 2-2n) if the answer is "yes", and with probability 1/2 - ε if the answer is "no", but no mere mortal could actually distinguish the two cases efficiently.
Example: An example of a PP problem (in fact, a PP-complete problem) is, given a Boolean formula with n variables, to decide whether at least half of the 2n settings of the variables cause the formula to evaluate to true.
Results:
- NP ⊆ PP. To see this, note that PP contains the NP-complete problems: again, given a Boolean formula with n variables, accept immediately with probability 1/2-2-2n; otherwise, choose a random truth assignment and accept if and only if it satisfies the formula. Then the total probability of accepting will be greater than 1/2 if there is at least one satisfying assignment for the formula, and less than 1/2 otherwise.
BPP: Bounded-Error Probabilistic Polynomial Time
Motivation: Above, we considered one randomized complexity class, PP, but argued that PP did not quite capture the notion of efficient randomized computation. Can we find a randomized complexity class that does?
Definition: BPP is a "plausibly efficient" variant of PP. It is the class of decision problems solvable in polynomial time by a probabilistic Turing machine M, where M correctly accepts or rejects an input with probability greater than 2/3.
In fact, we can replace 2/3 by any constant greater than 1/2: by repeating our algorithm and taking the majority of the outputs as the answer, we can make the probability of error arbitrarily small (in polynomial time).
Why does BPP better capture the notion of efficient randomization than PP does? The difference between the two classes is that since BPP requires a correct probability to be "far away" from 1/2, errors can be made arbitrarily small in polynomial time; however, because PP allows correct probabilities to be arbitrarily close to 1/2, making errors arbitrarily small can take exponential time.
Results:
- It is not known whether BPP contains complete problems.
- BPP = co-BPP.
- The relationship between BPP and NP is unknown. However, BPP ⊆ NPNP.
- BPP is low for itself: a BPP machine with access to a BPP oracle is no more powerful than the machine by itself.
Notes: The analogue of BPP for a quantum Turing machine is BQP.
RP: Randomized Polynomial Time
Motivation: The error probability of a BPP algorithm can easily made be made arbitrarily small; say, smaller than the probability that your cracked egg will reassemble itself. But while an arbitrarily small probability of error is fine for most applications, when managing a nuclear power plant (as one example), sometimes absolute certainty is a requirement.
Definition: RP is the class of languages recognized in polynomial time by a probabilistic Turing machine M, such that M accepts inputs in the language with probability at least 1/2, and M rejects inputs not in the language with probability 1. In other words, if the algorithm ever accepts, we can be certain that the answer is "yes" (but if the algorithm rejects, there is a chance that the algorithm is wrong).
As with BPP, by making independent repetitions of the algorithm, the probability of false negatives can be made arbitrarily small in polynomial time.
Results:
- RP ⊆ NP.
Notes: coRP is the class of problems with a polynomial-time randomized algorithm that accepts with probability 1 if the answer is "yes", and with probability less than 1/2 if the answer is "no". In other words, if the algorithm ever rejects, we can be certain that the answer is "no" (but if the algorithm accepts, there is a chance that the algorithm is wrong).
ZPP: Zero-Error Probabilistic Polynomial Time
Motivation: RP algorithms always correctly accept (but may incorrectly reject), and coRP algorithms always correctly reject (but may incorrectly accept). What about algorithms that may not answer, but are always correct when they do (i.e., they both correctly accept and correctly reject)?
Definition: ZPP = RP ∩ coRP; that is, it is the class of problems two probabilistic algorithms: one that always accepts correctly (a RP algorithm), and one that always rejects correctly (a coRP algorithm). This means that, by running both algorithms, in expected polynomial time, we will always have a correct answer.
An equivalent definition of ZPP is the class of problems solvable by a polynomial-time probabilistic algorithm that is always correct when outputting "yes" or "no", but can also output "I don't know" up to 1/2 of the time.
Results:
- ZP ⊆ RP ⊆ BPP ⊆ PP.
BQP: Bounded-Error Quantum Polynomial Time
Motivation: BPP is widely considered to be the class of efficiently computable problems in a classical universe. What about in a quantum mechanical universe?
Definition: BQP is the class of decision problems solvable in polynomial time by a quantum Turing machine, with probability of error less than 1/3.
As with BPP, we can replace 1/3 with any constant less than 1/2.
Results:
- BPP ⊆ BQP ⊆ PP
- BQP is low for PP: a PP machine gains no additional power from having a BQP-oracle.
IP: Interactive Proof
Motivation: What is a proof? The usual way to prove a result is to write down a sequence of statements that can easily be verified to be true. Notice that this notion of proof is essentially the definition of NP (the class of languages whose elements have short and quickly checkable proofs of membership)! However, we can consider other notions of proof. For example, when a professor writes down a proof, the professor and students often interact with each other: before they will accept a theorem, the (computationally bounded!) students demand and verify a sequence of explanations from the (all-powerful) professor. Are these two notions of proof equivalent? Or can we prove statements in the second (interactive classroom) model that we cannot in the first (the textbook model)?
Definition: In a k-round interaction on input x, a verifier V (the student) tries to determine whether to accept an input x, by asking the prover P (the professor) a series of k questions which the teacher must answer. Each of the student's questions can be based on x, his previous questions, and a random string hidden from the professor; and each of the professor's answers can depend on x and on his previous answers (the professor does not have access to a random string). After the k rounds of question-and-answer, the student must decide whether to accept or reject x.
Now, restrict the student's questions to be formulated in polynomial time (i.e., if the student uses a function f to determine what questions he should ask, then f should run in time polynomial in the length of x), but let the all-knowing professor have unlimited power in answering. Under these restrictions, IP is the class of all languages L such that the student will correctly determine whether an input x is in L at least 2/3 of the time, in a polynomial number of rounds.
Example: Two graphs G1 and G2 are isomorphic if by permuting the vertices of one of the graphs, we can produce the other. The Graph Isomorphism problem, of determining whether two graphs are isomorphic, is clearly in NP, since we can use the permutation of the vertices as a certificate; but the NP-status of the opposite problem, of determining whether two graphs are not isomorphic, is unclear. However, Graph Non-Isomorphism is in IP, as follows.
The verifier randomly chooses i from {1, 2}, and randomly permutes the vertices of Gi to get a graph H. V then sends this new graph to the prover, and asks which graph H came from. The prover identifies whether G1 or G2 produced H and sends this answer back to the verifier. After k rounds, V accepts if P's answers are all correct, and rejects otherwise. Since P has only a 1/2 chance of guessing correctly if G1 and G2 are not in fact isomorphic, then the probability that V accepts when G1 are not actually isomorphic is 2-k, so this protocol is sound (and clearly complete).
Results:
- IP = PSPACE. (IP is contained in PSPACE because one can show it is possible to compute the optimum prover using polynomial space, and then use this optimum prover to simulate an interaction.)
- NP is the subclass of IP in which the verifier does not use any randomization.
- BPP is the subclass of IP in which the verifier ignores the prover.
AM: Arthur-Merlin
Motivation: In the definition of IP above, the verifier had access to private random strings unknown to the prover. Indeed, the IP protocol crucially depended on this fact. What happens if the verifier's random strings are made public to the prover?
Definition: AM[k] is a k-round interactive proof, in which a polynomial-time verifier (Arthur) asks the computationally unbounded prover (Merlin) a series of questions which Merlin answers. Arthur's questions can depend on the input, his previous questions, and a public random string; Merlin's questions can depend on the input and his previous answers. Notice AM[k] differs from IP in that Arthur and Merlin are limited to k rounds of interaction, and Arthur's random strings are now made public.
AM is defined to be the class AM[2].
Results:
- AM = AM[k] for k ≥ 2.
- AM[k] ⊆ IP[k], for every k.
- IP[k] ⊆ AM[k+2]. (Thus, Graph Non-Isomorphism is actually in AM also.)
MA: Merlin-Arthur
Motivation: Remember that one notion of proof is captured by NP, the class of languages with short proofs of membership that can be quickly verified. We can think of this in IP terms as a one-round interaction in which the almighty prover sends a certificate of membership to the verifier, who must check it in polynomial time. What happens if we allow the verifier to be wrong with some small probability?
Definition: MA is the set of decision problems whose solutions can be verified, with high probability, in polynomial time. In other words, the prover (the all-powerful Merlin) sends a string to the (mere mortal) Arthur, who must correctly accept or reject the input (with the help of Merlin's string and a random string) with probability at least 2/3, in polynomial time.
Results:
- NP is the subclass of MA in which Arthur does not use any randomization.
- BPP is the subclass of MA in which Arthur ignores Merlin.
- MA is the subclass of AM in which Arthur does nothing in the first round.
PH: Polynomial Hierarchy
An oracle for a language A is a device that can return whether any string w is a member of A. An oracle Turing machine MA is a Turing machine that can also query an oracle for A. (To query the oracle, the machine writes a string on a special oracle tape, enters a special query state, and is then informed in a single computation step whether the query string is in A.)
If we have all the Turing machines that decide the languages in the complexity class C, then we can produce the class CA by giving these Turing machines an oracle for A. For example, PA contains the languages decidable with a polynomial time oracle Turing machine that uses an oracle for A.
- There is an oracle A such that PA = NPA...
- But there is also an oracle B such that PB ≠ NPB!
Consider the class PSAT. Since SAT is NP-complete, we can replace the SAT oracle with an oracle for any language in NP, and so we can write PSAT as PNP instead. Just as we were interested in P's nondeterministic version, NP, we will probably be interested in PNP's nondeterministic version, NPNP. We can then repeat to get the class PNPNP, and so on, to get a hierarchy of classes:
Let Δ0P = Σ0P = Π0P = P. Then for i > 0, let
PH is the union of all of these classes.
Another, equivalent, definition is the following. Notice that any NP instance is of the form "Does there exist an X such that A(X) = 1?" (where A is a function computable in polynomial time). Likewise, any coNP instance is of the form "For every X, does A(X) = 1?". Adding quantifiers produces: "Does there exist an X such that for every Y, A(X, Y) = 1?" and "For every X, does there exist a Y such that A(X, Y) = 1?"; these are called Σ2P and Π2P, respectively. To produce Σ3P and Π3P, we add another quantifier: "Does there exist an X such that for every Y there exists a Z such that A(X, Y, Z) = 1?" and "For every X, does there exist a Y such that for all Z, A(X, Y, Z) = 1?". Generalizing in the obvious way, we can produce ΣkP and ΠkP for any positive integers k, and taking the union of these two classes over all k gives PH.
We can think of each level of the polynomial hierarchy as a generalization of NP and coNP.
- If P = NP, then the polynomial hierarchy collapses completely, to P.
- If NP = coNP, then the polynomial hierarchy collapses to the first level, NP.
- Proving that Graph Isomorphism is NP-complete would collapse PH to the second level.
P/Poly: Nonuniform Polynomial Time
An advice string is an extra input to a Turing Machine that depends only on the length of the input. Let A(n) be a function from integers to advice strings. Then a Turing machine M decides a language L with advice A(n) if M(x, A(|x|) = "yes" whenever x ∈ L, and M(x, A(|x|) = "no" whenever x ∉ L. In other words, the advice A(n) helps M decide all strings of length n correctly.
One definition of P/poly is the class of languages recognized by a polynomial-time Turing machine with polynomial-bounded advice functions (the advice strings are polynomial in the length of the input). In other words, a language L is in P/poly if there is a set of advice strings {a0, a1, ...}, where each ai is polynomial in i, and an input x is in L if and only if M(x, a|x|) = "yes".
Another definition is that P/poly is the class of languages with a polynomial-size non-uniform circuit family. In other words, there must exist a polynomial-bounded family of circuits {C0, C1 such that x = x1...xn is in L if and only if Cn(x1,...,xn) accepts.
Example: Miller-Rabin primality test.
TODO: Add example.
P/poly allows time and program size to grow as the input grows.
- BPP ⊆ P/poly.
- If NP ⊆ P/Poly, then the polynomial hierarchy collapses (to the second level).
- If NP ⊄ P/Poly, then P ≠ NP.
- P/poly contains noncomputable languages.
- P/poly contains an uncountable number of languages.
P/f(n) is the generalization of P/poly that allows advice strings of length f(n).
QMA: Quantum MA
SZK: Statistical Zero-Knowledge
NC: Nick's Class
NC is the class of decision problems solvable in polylogarithmic time on a parallel computer with a polynomial number of processors. Equivalently, it is the set of problems decidable by uniform Boolean circuits with a polynomial number of gates and polylogarithmic depth.
AC is a related class, in which gates are allowed to have unbounded fanin (in NC, the fanin is at most 2).
NC can be thought of as the parallel analogue to P; that is, the set of problems efficiently solvable on a parallel computer.
- NCi ⊆ ACi ⊆ NCi+1.
- PARITY is in NC1.
Cryptographic Primitives
One-Way Functions Trapdoor One-Way Functions One-Way Permutation Pseudorandom Generators Pseudorandom Functions Pseudorandom Permutations Public-Key Cryptosystems PKC Secure (Against Chosen Ciphertext Attack) Computational Zero-Knowledge Proof Systems Statistical Zero-Knowledge Proof Systems Homomorphic Public-Key Cryptosystems
RSA Diffie-Helman Ajtai-Dwork McEliece Regev ElGamal Elliptic Curve Cryptosystems
Major Theorems
Savitch's Theorem Ladner's Theorem Blum Speedup Theorem Impagliazzo-Widgerson Theorem Toda's Theorem Natural Proofs
