課程名稱︰資訊工程理論基礎 課程性質︰必修 課程教師︰呂育道 開課學院：電資 開課系所︰資工所 考試日期（年月日）︰2013/1/8 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Notes: You may use any results proved in the class unless stated otherwise. Recall: ● RP: If L∈RP, then there exists a randomized polynomial-time TM M such that: -if x∈L, then at least half of the computation paths of M on x halt with "yes"; -if x!∈L, then all computation paths halt with "no." ● BPP: If L∈BPP, then there exists a randomized polynomial-time TM M such that: -If x∈L, then at least 3/4 of the computation paths of M on x lead to "yes"; -If x!∈L, then at least 3/4 of the computation paths of M on x lead to "no." ● IP: If L∈IP, then there exits an interactive proof system (P,V) such that the prover runs in exponential time and the verifier runs in probabilistic polynomial time and: -If x∈L, then the probability that x is accepted by the verifier is at least 1-2^-|x|. -If x!∈L, then the probability that x is accepted by the verifier with any prover replacing the original prover is at most 2^-|x| Note that the number of rounds and the lengths of the messages are both polynomials in |x|. You can assume V sends out the first message. Problem 1 (25 points) Prove (a) RP is in BPP and (b) BPP is in PSPACE. Problem 2 (25 points) Please compute the Jacobi symbol (1003|1151). You need to write down the calculations instead of merely giving the answer. (Hint: Let p and q be two odd numbers, not necessarily primes. The law of quadratic reciprocity says (p|q)(q|p)=(-1)^[(p-1)(q-1)/4].) Problem 3 (25 points) Define IP* as IP except that the prover now runs in (deterministic) polynomial space instead of exponential time. Show that IP* is in PSPACE. (You cannot use the known fact IP=PSPACE.) Problem 4 (25 points) Prove that there is no ε-approximation algorithm for 6-COLORING if ε<1/7 and assuming P≠NP. (Hint: Recall that an ε-approximation algorithm F guarantees that OPT≦c(F(G))≦OPT/(1-ε) where c(F(G))) is the number of colors the polynomial-time algorithm F uses to color G. What is the quality of the coloring scheme if you color the input graph using the alleged ε-approximation algorithm?) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.29.119