RelativizationOracle Turing machinesTheorem 9.20(2)Theorem 9.20(1)Limits of the simulation methodRelativizationRelativizationSection 9.2 Giorgi Japaridze Theory of ComputabilityOracle Turing machines9.2.aGiorgi Japaridze Theory of ComputabilityDefinition 9.17 An oracle for a language A is device that is capable of reportingwhether any given string w is a member of A. An oracle Turing machine (OTM) MA is a modified Turing machine that has the additional capability of querying an oracle. Whenever MA writes a string on a special oracle tape, it is informed whether that string is a member of A, in a single computation step. Let PA be the class of languages decidable with a polynomial time OTM that uses oracle A. Define NPA similarly.Example 9.18 NPPSAT (why?).Theorem 9.20(2)9.2.bGiorgi Japaridze Theory of ComputabilityTheorem 9.20(2) PTQBF = NPTQBF. Proof. The containment PTQBF  NPTQBF is trivial. And the containment NPTQBF  PTQBF follows from the following chain of containments: NPTQBF 1 NPSPACE 2 PSPACE 3 PTQBF 1 because we can convert the nondeterministic polynomial time OTM to a nondeterministic polynomial space TM that computes the answers to queries regarding TQBF instead of using the oracle. 2 follows from Savitch’s theorem. 3 because TQBF is PSPACE-complete.Note: In this theorem, instead of TQBF, we could have taken any other PSPACE-complete problem.Theorem 9.20(1)9.2.cGiorgi Japaridze Theory of ComputabilityTheorem 9.20(1) An oracle A exists whereby PA ≠ NPA. Proof. For any oracle A, let LA={w | xA (|x|=|w|)}. Obviously LA is in NPA(why?). To show that, on the other hand, LA is not in PA , we design A as follows. Let M1,M2, … be a list of all polynomial time OTMs. For simplicity, we may assume that each Mi runs in time ni. Construction proceeds in stages, each stage declaring certain finitely many strings to be in or out of A. Initially we have noinformation about A. We begin with stage 1. Stage i: We choose n greater than the length of any string whose membership (in A) status has already been determined, also making sure that n is large enough to satisfy 2n>ni. Then we run Mi on input 1n and respond to its oracle queries as follows. If Mi queries a string y whose status has already been determined, we respond consistently. If y’s status is undetermined, we respond NO to the query and declare y to be out of A. We continue simulation until Mi halts. If it accepts 1n, we declare all the remaining strings of length n to be out of A. If Mi rejects 1n, we find a string of length n that Mi has not queried and declare that string to be in A. Such a string must exist because, within the ni steps available to Mi, it could not have queried all of the 2n strings of length n. It can be seen that Mi accepts 1n iff 1nLA. Hence Mi does not decide LA.Limits of the simulation method9.2.dGiorgi Japaridze Theory of ComputabilityWe have proved so many theorems using the method of simulation (of one machine by another). An import of Theorem 9.20 is that the same method is unlikely to be successfully used for solving the P=NP? problem.Indeed, if a machine M can simulate a machine N, then, for any oracle Q, MQ can also simulate NQ, because whenever NQ queries the oracle, so can MQ, and therefore the simulation can proceed as before. Consequently, if we could prove by simulating that P and NP are the same, we could conclude that they are the same relative to any oracle as well. But Theorem 9.20(1) shows that they are not the same relative to the oracle A.Similarly, if we could prove by simulating that P and NP are different, we could conclude that they are different relative to any oracle as well. But Theorem 9.20(2) shows that they are not the same relative to the oracle