Question

Suppose that A and B are two oracles. One of them is an oracle for TQBF, but if you don’t know which. Give an algorithm that has access to both A and B, and that is guaranteed to solve TQBF in polynomial time.

Short answer

An oracle machine is a type of Turing Machine having many different tapes and these tapes are called oracle tapes. The different states may be represented$q_{states}$ .

Step-by-step solution

 Using Baker Gill Solovay Theorem

TQBF is referred as True Qualified Boolean Formula. To show TQBF in polynomial problem having access to Turing machine A and B can be solved using Baker Gill Solovay Theorem.

For our convenience the problem is broken into two parts.

For Oracle A:

• Let, TQBF has access to A then,$\mathit{A}\mathbf{=}\mathit{T}\mathit{Q}\mathit{B}\mathit{F}$ .
• The above problem can be solved by showing ${\mathit{P}}^{\mathbf{A}}\mathbf{=}\mathit{N}{\mathit{P}}^{\mathbf{B}}$.
• We know that$\mathit{T}\mathit{Q}\mathit{B}\mathit{F}$ is PSPACE problem,
• Therefore,$\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}\mathbf{}\underline{\mathbf{\subset }}\mathbf{}{\mathit{P}}^{\mathbf{T}\mathbf{Q}\mathbf{B}\mathbf{F}}$ and$\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}{\mathit{E}}^{\mathbf{T}\mathbf{Q}\mathbf{B}\mathbf{F}}\underline{\mathbf{\subset }}\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}$
• Hence, by the above results we can say that${\mathit{P}}^{\mathbf{A}}\mathbf{=}\mathit{N}{\mathit{P}}^{\mathbf{B}}$

Solving the part two of the problem

For Oracle B:

• It is required to show that ${\mathit{P}}^{\mathbf{A}}\mathbf{\ne }\mathit{N}{\mathit{P}}^{\mathbf{B}}$for oracle B.
• Now, define a language L as:${\mathit{L}}_{\mathbf{B}}\mathbf{=}\left\{0^{n}lw\left\{\in 0,1\right\}\right\}$where,$\mathit{B}\left(w\right)\mathbf{=}\mathbf{1}$
• For any oracle B the defined language L is$\mathit{N}{\mathit{P}}^{\mathbf{B}}$
• If $\mathit{X}\mathbf{=}{\mathbf{0}}^{\mathbf{n}}$with$\left|w\right|\mathbf{=}\left|x\right|$ then, the machine’s output will be 1.
• Here we can say that $\mathit{T}\mathit{Q}\mathit{B}\mathit{F}\mathbf{\in }\mathit{N}\mathit{L}$which shows that $\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}\mathbf{\in }\mathit{N}\mathit{L}$
• Baker Gill theorem states that$\mathit{N}\mathit{L}\mathit{\varphi }\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}$
• Now, using Baker Gill and hierarchy Theorem, it can be said that ${\mathit{P}}^{\mathbf{A}}\mathbf{\ne }\mathit{N}{\mathit{P}}^{\mathbf{B}}$

Thus, from the results of the two parts it is proven that TQBF is in polynomial time for both oracle A and B.