Above NP,one can define more classes by using more (alternating)quantifiers. 2={x:3y1Vy2(x,yu,y2)=1}for some P. ={x:y13y2(x,y1,y2)=1 for some中∈P. Basically,they are one-level upper than NP and co-NP.One can define and II for larger k.Taking the union for all k(independent of the problem input size),we get the class PH(Polynomial Hierarchy).The classes and Ip are usually called the k-th layer of PH, and the first layer contains NP and co-NP.It's not hard to see from the definition that and IIWhile each layer has complete problems,PH doesn't unless it collapses to a certain level. Most researchers believe that PH doesn't collapse,and use this as a computational assumption.A basic fact is that if=II,then PH==IIP,thus PH collapses to the k-th level.For example,one can show that if the problem Graph Isomorphism is NP complete, then PH collapses to the second level. Advice is a string given to a Turing machine.It can depend on the input size,but not the input itself.We use TIME(t(n))/l(n)to denote the language decided by a t(n)-time Turing machine augmented with a l(n)-bit advice for inputs of size n.The class P/poly coincides with the class of languages decidable by polynomial-size circuits.The following theorem says that it's unlikely that the power of advice is powerful for NP. Theorem(Karp-Lipton)NP∈P/poly→PH=. (Proof idea.NP P/poly implies the existence of a circuit family to decide an NP language.This existence is the one to show I.) Randomness plays an important role in algorithm designing.A language L is in BPP if it can be decided with bounded error,say,1/3,by a polynomial-time Turing machine.Though many people believe that BPP=P,we can't even rule out the possibility that BPP=NEXP. What we do know includes the facts that BPP P/poly and that BPP E2n IP. (Proof idea of BPP P/poly:Reduce the error to exponential small and then find a random string that is correct for all inputs of a certain size.Use this string as the advice.Proof idea of BPP:Reduce the error to exponential small and then prove that xEL iff thereAbove NP, one can define more classes by using more (alternating) quantifiers. 𝚺𝟐 𝐩 = {𝑥: ∃𝑦1∀𝑦2𝜙(𝑥, 𝑦1 , 𝑦2 ) = 1} for some 𝜙 ∈ 𝐏. 𝚷𝟐 𝐩 = {𝑥: ∀𝑦1∃𝑦2𝜙(𝑥, 𝑦1 , 𝑦2 ) = 1} for some 𝜙 ∈ 𝐏. Basically, they are one-level upper than NP and co-NP. One can define 𝚺𝐤 𝐩 and 𝚷𝐤 𝐩 for larger k. Taking the union for all k (independent of the problem input size), we get the class PH (Polynomial Hierarchy). The classes 𝚺𝐤 𝐩 and 𝚷𝐤 𝐩 are usually called the k-th layer of PH, and the first layer contains NP and co-NP. It’s not hard to see from the definition that 𝚺𝐤 𝐩 ⊆ 𝚷𝐤+𝟏 𝐩 and 𝚷𝐤 𝐩 ⊆ 𝚺𝐤+𝟏 𝐩 . While each layer has complete problems, PH doesn’t unless it collapses to a certain level. Most researchers believe that PH doesn’t collapse, and use this as a computational assumption. A basic fact is that if 𝚺𝐤 𝐩 = 𝚷𝐤 𝐩 , then 𝐏𝐇 = 𝚺𝐤 𝐩 = 𝚷𝐤 𝐩 , thus PH collapses to the k-th level. For example, one can show that if the problem Graph Isomorphism is NP complete, then PH collapses to the second level. Advice is a string given to a Turing machine. It can depend on the input size, but not the input itself. We use 𝐓𝐈𝐌𝐄(𝑡(𝑛))/𝑙(𝑛) to denote the language decided by a 𝑡(𝑛)-time Turing machine augmented with a 𝑙(𝑛)-bit advice for inputs of size n. The class P/poly coincides with the class of languages decidable by polynomial-size circuits. The following theorem says that it’s unlikely that the power of advice is powerful for NP. Theorem (Karp-Lipton) 𝐍𝐏 ⊆ 𝐏/𝐩𝐨𝐥𝐲 ⇒ 𝐏𝐇 = 𝚺𝟐 𝒑 . (Proof idea. 𝐍𝐏 ⊆ 𝐏/𝐩𝐨𝐥𝐲 implies the existence of a circuit family to decide an NP language. This existence is the one to show 𝚷𝟐 𝒑 ⊆ 𝚺𝟐 𝒑 .) Randomness plays an important role in algorithm designing. A language L is in BPP if it can be decided with bounded error, say, 1/3, by a polynomial-time Turing machine. Though many people believe that 𝐁𝐏𝐏 = 𝐏, we can’t even rule out the possibility that 𝐁𝐏𝐏 = 𝐍𝐄𝐗𝐏. What we do know includes the facts that 𝐁𝐏𝐏 ⊆ 𝐏/𝐩𝐨𝐥𝐲 and that 𝐁𝐏𝐏 ⊆ 𝚺𝟐 𝒑 ∩ 𝚷𝟐 𝒑 . (Proof idea of 𝐁𝐏𝐏 ⊆ 𝐏/𝐩𝐨𝐥𝐲: Reduce the error to exponential small and then find a random string that is correct for all inputs of a certain size. Use this string as the advice. Proof idea of 𝐁𝐏𝐏 ⊆ 𝚺𝟐 𝒑 ∩ 𝚷𝟐 𝒑 : Reduce the error to exponential small and then prove that 𝑥 ∈ 𝐿 iff there