\documentclass[10pt,fleqn,a4paper]{article}
\usepackage[latin2]{inputenc}
\usepackage[czech]{babel}
\usepackage{amsmath,amsfonts,amsthm}
\newtheorem{definice}{Definice}
\newtheorem{dusledek}{D\accent23usledek}
\newtheorem{tvrzeni}{Tvrzen\'\i{}}
\newtheorem{veta}{V\v eta}
\newtheorem{fakt}{Fakt}
\newtheorem{lemma}{Lemma}
\newsymbol\subsetneqq 2320
\newcommand{\oops}[1]{\textrm{#1}}
\newcommand{\ops}[1]{\emph{\textrm{#1}}}
\renewcommand{\labelenumi}{\arabic{enumi})}
\renewcommand{\labelenumii}{\alph{enumii})}
\begin{document}
\begin{definice}[PQUERY(A)]
T\v r\'\i{}du \oops{PQUERY}($A$) definujeme jako mno\v zinu v\v sech jazyk\accent23u p\v rij\'\i{}man\'ych deterministick\'ymi Turingov\'ymi stroji s orakulem $A$, 
kter\'e pracuj\'\i{} v prostoru polynomi\'aln\'\i{}m vzhledem k d\'elce vstupu a kter\'e kladou or\'akulu pouze polynomi\'aln\v e mnoho dotaz\accent23u.
\end{definice}
\begin{veta}
$\forall A \ops{ PQUERY}(A) = \ops{P}(A) \Leftrightarrow A$ je \ops{PSPACE}-t\v e\v zk\'y probl\'em.
\end{veta}
\begin{proof}
Nejprve doka\v zme implikaci z prava doleva. 

Nech\v t $A$ je \oops{PSPACE}-t\v e\v zk\'y probl\'em, tedy $A$ na je polynomi\'aln\v e p\v revoditeln\'y ka\v zd\'y probl\'em z t\v r\'\i{}dy \oops{PSPACE}. Vztah $\oops{P}(A) \subseteq \oops{PQUERY}(A)$ plat\'\i{} trivi\'aln\v e, nebo\v t 
omezen\'\i{} doby v\'ypo\v ctu omezuje mno\v zstv\'\i{} pou\v zit\'eho prostoru z\'arove\v n s omezen\'\i{}m po\v ctu dotaz\accent23u oraculu. Tedy stroj pracuj\'\i{}c\'\i{} v polynomi\'aln\'\i{}m \v case 
t\'\i{}m sp\'\i{}\v se pracuje v polynomi\'aln\'\i{}m prostoru a klade pouze polynomi\'aln\v e mnoho dotaz\accent23u.

Uka\v zme opa\v cnou inkluzi, tedy $\oops{PQUERY}(A) \subseteq \oops{P}(A)$. Nech\v t $C \in \oops{PQUERY}(A)$ a nech\v t $M$ je 
deterministick\'y Turing\accent23uv stroj s oraculem, kter\'y tuto skute\v cnost dokazuje. Ozna\v cme $p(n)$ polynom, kter\'y omezuje pou\v zit\'y prostor 
strojem $M$ nad vstupem $x$ d\'elky $n$.

Zvolme k\'odov\'an\'\i{} konfigurac\'\i{} stroje $M$ nad abecedou $\{0,1\}$. Pro ka\v zdou konfiguraci $I$ uva\v zujme \v c\'ast v\'ypo\v ctu stroje $M$, 
kter\'a za\v c\'\i{}n\'a konfigurac\'\i{} $I$, kon\v c\'\i{} konfigurac\'\i{} $J$, kde $J$ je bu\v d t\'azac\'\i{} nebo koncov\'a konfigurace, a kter\'a neobsahuje 
jin\'e t\'azac\'\i{} konfigurace, ne\v z je $J$. Proto\v ze $M$ je deterministick\'y stroj, je konfigurace $J$ jednozna\v cn\v e d\'ana. Ozna\v cme Leap($I$) 
funkci, kter\'a pro $I$ vrac\'\i{} k\'od p\v r\'\i{}slu\v sn\'e konfigurace $J$. 
Definujeme mno\v zinu $B$:
\begin{equation}
B = \{<I,x> | x \mbox{ je prefixem leap(}J)\}.
\end{equation}
Uka\v zme, \v ze $B \in \oops{PSPACE}$. To dokazuje stroj, kter\'y za\v cne v konfiguraci $I$ a simuluje stroj $M$, dokud nedos\'ahne t\'azac\'\i{} 
nebo koncov\'e konfigurace. N\'asledn\v e zkontroluje, zda je $x$ prefixem k\'odu v\'ysledn\'e konfigurace.

Proto\v ze podle p\v redpoklad\accent23u je $A$ \oops{PSPACE}-t\v e\v zk\'y probl\'em, je na n\v ej $B$ polynomi\'aln\v e p\v revoditeln\'y. Tedy stroj s oraculem $A$ 
dok\'a\v ze $B$ rozhodovat v polynomi\'aln\'\i{}m \v case. Toho vyu\v zijeme p\v ri simulaci $M$.

Algoritmus je n\'asleduj\'\i{}c\'\i{}:

vstup $x$ \par
$I := \mbox{po\v c\'ate\v cn\'\i{} konfigurace } M \mbox{ na vstupu } x$ \par
loop \par
\ \ \ zkonstruuj $J := leap(I)$\par
\ \ \ je-li $J$ koncov\'a konfigurace, ukon\v ci smy\v cku\par
\ \ \ nech\v t $w$ je dotazovan\'e slovo\par
\ \ \ zeptej se $A$ na $w$\par
\ \ \ $I := \mbox{ n\'asleduj\'\i{}c\'\i{} konfigurace v z\'avislosti na v\'ysledku dotazu}$\par
end loop\par
podle $J$ p\v rijmi nebo odm\'\i{}tni\par

T\v elo cyklu se vykon\'a polynomi\'aln\v e mnoho kr\'at, nebo\v t ka\v zd\'y pr\accent23uchod cyklem odpov\'\i{}d\'a jednomu dotazu stroje $M$, kter\'y se v\v sak mohl pt\'at
pouze polynomi\'aln\v e kr\'at. Uk\'a\v zeme-li, \v ze leap($I$) lze zkonstruovat v polynomi\'aln\'\i{} \v case, je prvn\'\i{} \v c\'ast d\accent23ukazu hotov\'a.

Pro konstrukci leap($I$) pou\v zijeme prefixov\'e vlastnosti jazyka $B$. Je z\v rejm\'e, \v ze d\'elka k\'odu konfigurace je pouze polynomi\'aln\'\i{} 
vzhledem k velikosti vstupu (za p\v redpokladu pou\v zit\'\i{} "rozumn\'eho" k\'odov\'an\'\i{}). N\'asleduj\'\i{}c\'\i{} algoritmus pracuje v polynomi\'aln\'\i{}m \v case.

vstup $I$ \par
$y := \lambda$\par
while $y \mbox{ nen\'\i{} k\'odem konfigurace a } |y| \leq p(|x|)$ do\par
\ \ \ if $<I,y0> \in B$ then $y:=y0$ else $y:=y1$\par
end while\par
if $y$ je k\'odem konfigurace then return $y$ else odm\'\i{}tneme

Celkem tedy dost\'av\'ame, \v ze za p\v redpokladu, \v ze $A$ je \oops{PSPACE}-t\v e\v zk\'y, plat\'\i{} $\oops{PQUERY}(A) = \oops{P}(A)$.

Nyn\'\i{} uka\v zme opa\v cnou implikaci, tedy \v ze z $\oops{PQUERY}(A) = \oops{P}(A)$ plyne, \v ze $A$ je \oops{PSPACE}-t\v e\v zk\'y. Tato implikace je 
snaz\v s\'\i{}. Uv\v edomme si, \v ze $A$ je \oops{PSPACE}-t\v e\v zk\'y, pr\'av\v e kdy\v z $\forall B \in \oops{PSPACE}: B \in \oops{P}(A)$. 

Z\v rejm\v e $\oops{PSPACE} = \oops{PQUERY}(\emptyset) \subseteq \oops{PQUERY}(A) = \oops{P}(A)$, tedy tvrzen\'\i{} plat\'\i{}.
\end{proof}

V\v eta popisuje rozd\'\i{}l ve slo\v zitosti mezi t\v r\'\i{}dou PQUERY a P ve vztahu k \'upln\'ym probl\'em\accent23um t\v r\'\i{}dy PSPACE. Ukazuje se, \v ze pouze "dostate\v cn\v e t\v e\v zk\'e" 
probl\'emy dok\'a\v z\'\i{} zajistit rovnost relativizovan\'ych t\v r\'\i{}d a naopak ka\v zd\'y jazyk, kter\'y tuto rovnost zajist\'\i{}, je ji\v z "dostate\v cn\v e te\v zk\'y" a umo\v z\v nuje 
\v re\v sen\'\i{} PSPACE probl\'em\accent23u v polynomi\'aln\'\i{}m \v case. 
\end{document}