Define an oracle for language L to be a \"magical device\" that, on input w, wit

Question

Define an oracle for language L to be a "magical device" that, on input w, within zero time, can answer whether or not w element of L. We can define a Turing Machine that is equipped for a language L analogously: it can query the oracle for L whenever it wants (there is a special "oracle tape" for which the TM writes the input w for the oracle). An oracle for a complexity class C is the same but can answer, in zero time, about any language in C. We say, for a complexity class C and an oracle for complexity class M, denoted C^M, to be the set of all languages decided by any TM for any language in C equipped with an oracle for M. For example, P^P is the set of all problems that are computable in polynomial time with instant access to an oracle for any language in P. Now, we define the polynomial hierarchy as follows: set sigma^P_0 to be P, sigma^P_1 = NP, and for all i greaterthanorequalto 1, sigma^P_i + 1 = NP^sigma^P_i. Define the polynomial co-hierarchy as: set gamma^P_0 to be P, gamma^P_1 = coNP, and for all i greaterthanorequalto 1, gamma^P_i + 1 = coNP^P_i (where coNP is the set of all languages whose complements are in NP) Denote PH = union_i greaterthanorequalto 0 sigma^P_i One can prove that also PH = union_i greaterthanorequalto 0 gamma^P_i Prove that if sigma ^P_i = gamma^P_i, then sigma^P_i + 1 = gamma^P_i + 1. Also prove that if PH has a complete problem then sigma^P_i = sigma^P_i + 1 for some finite value of i.

Explanation / Answer

ANSWER::

In order to define the complexity classes formally, it is useful to introduce the notion of a polynomial time relation: Definition 1 A relation R(x, y1, . . . , yn) is a polynomial time relation if there is a (deterministic) Turing machine V and polynomial p such that V decides R(x, y1, . . . , yn) in time p(|x|). We then define NP as follows: Definition 2 A language L is in the class NP if and only if there exists a polynomial time relation R such that x L if and only if y such that R(x, y) holds. We can also define the complementary class coNP: Definition 3 A language L is in the class coNP if and only if its complement L is in NP; equivalently, a language L is in coNP if and only if there exists a polynomial time relation R such that x L if and only if y, R(x, y) holds

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.