91Ó°ÊÓ

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{⊂}}\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{⊂}}\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}}$

For Oracle B:

• It is required to show that ${\mathit{P}}^{\mathbf{A}}\mathbf{≠}\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\{∈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{∈}\mathit{N}\mathit{L}$which shows that $\mathit{P}\mathit{S}\mathit{P}\mathit{A}\mathit{C}\mathit{E}\mathbf{∈}\mathit{N}\mathit{L}$
• Baker Gill theorem states that$\mathit{N}\mathit{L}\mathit{Ï•}\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{≠}\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.