Definice 1 (PQUERY(A)). Třídu PQUERY(A) definujeme jako množinu všech jazyků přijímaných deterministickými Turingovými stroji s orakulem A, které pracují v prostoru polynomiálním vzhledem k délce vstupu a které kladou orákulu pouze polynomiálně mnoho dotazů.

Věta 1. ∀A PQUERY(A) = P(A) ⇔ A je PSPACE-těžký problém.

Důkaz. Nejprve dokažme implikaci z prava doleva.

Necht’ A je PSPACE-těžký problém, tedy A na je polynomiálně převoditelný každý problém z třídy PSPACE. Vztah P(A) ⊆ PQUERY(A) platí triviálně, nebot’ omezení doby výpočtu omezuje množství použitého prostoru zároveň s omezením počtu dotazů oraculu. Tedy stroj pracující v polynomiálním čase tím spíše pracuje v polynomiálním prostoru a klade pouze polynomiálně mnoho dotazů.

Ukažme opačnou inkluzi, tedy PQUERY(A) ⊆ P(A). Necht’ C ∈ PQUERY(A) a necht’ M je deterministický Turingův stroj s oraculem, který tuto skutečnost dokazuje. Označme p(n) polynom, který omezuje použitý prostor strojem M nad vstupem x délky n.

Zvolme kódování konfigurací stroje M nad abecedou {0, 1}. Pro každou konfiguraci I uvažujme část výpočtu stroje M, která začíná konfigurací I, končí konfigurací J, kde J je bud’ tázací nebo koncová konfigurace, a která neobsahuje jiné tázací konfigurace, než je J. Protože M je deterministický stroj, je konfigurace J jednoznačně dána. Označme Leap(I) funkci, která pro I vrací kód příslušné konfigurace J. Definujeme množinu B:

B = {< I, x > |x je prefixem leap(J)}. (1)

Ukažme, že B ∈ PSPACE. To dokazuje stroj, který začne v konfiguraci I a simuluje stroj M, dokud nedosáhne tázací nebo koncové konfigurace. Následně zkontroluje, zda je x prefixem kódu výsledné konfigurace.

Protože podle předpokladů je A PSPACE-těžký problém, je na něj B polynomiálně převoditelný. Tedy stroj s oraculem A dokáže B rozhodovat v polynomiálním čase. Toho využijeme při simulaci M.

Algoritmus je následující:

vstup x

I := počáteční konfigurace M na vstupu x

loop zkonstruuj J := leap(I) je-li J koncová konfigurace, ukonči smyčku necht’ w je dotazované slovo zeptej se A na w I := následující konfigurace v závislosti na výsledku dotazu

end loop

podle J přijmi nebo odmítni

Tělo cyklu se vykoná polynomiálně mnoho krát, nebot’ každý průchod cyklem odpovídá jednomu dotazu stroje M, který se však mohl ptát pouze polynomiálně krát. Ukážeme-li, že leap(I) lze zkonstruovat v polynomiální čase, je první část důkazu hotová.

Pro konstrukci leap(I) použijeme prefixové vlastnosti jazyka B. Je zřejmé, že délka kódu konfigurace je pouze polynomiální vzhledem k velikosti vstupu (za předpokladu použití ”rozumného” kódování). Následující algoritmus pracuje v polynomiálním čase.

vstup I

y := λ

while y není kódem konfigurace a |y| ≤ p(|x|) do

if < I, y0 >∈ B then y := y0 else y := y1 end while if y je kódem konfigurace then return y else odmítneme Celkem tedy dostáváme, že za předpokladu, že A je PSPACE-těžký, platí

PQUERY(A) = P(A).

Nyní ukažme opačnou implikaci, tedy že z PQUERY(A) = P(A) plyne, že A je PSPACE-těžký. Tato implikace je snazší. Uvědomme si, že A je PSPACEtěžký, právě když ∀B ∈ PSPACE : B ∈ P(A).

Zřejmě PSPACE = PQUERY(∅) ⊆ PQUERY(A) = P(A), tedy tvrzení platí.

Věta popisuje rozdíl ve složitosti mezi třídou PQUERY a P ve vztahu k úplným problémům třídy PSPACE. Ukazuje se, že pouze ”dostatečně těžké” problémy dokáží zajistit rovnost relativizovaných tříd a naopak každý jazyk, který tuto rovnost zajistí, je již ”dostatečně težký” a umožňuje řešení PSPACE problémů v polynomiálním čase.