[Teoria złożoności] Dowód przynależności

[marta_53]

Udowodnij, że:

Predykat \(\displaystyle{ L}\) należy do klasy \(\displaystyle{ BPP}\) wtedy i tylko wtedy, gdy istnieje predykat \(\displaystyle{ R \left( \overline{x}, \overline{y}\right)}\) rozstrzygalny deterministycznie w czasie \(\displaystyle{ poly \left( \overline{x}+\overline{y}\right)}\) i wielomian \(\displaystyle{ p \left( z \right) \in Z \left[ z\right]}\) takie, że
\(\displaystyle{ \overline{x} \in L \Leftarrow}\) proporcja zbioru\(\displaystyle{ \left\{ y \in \left( \overline{x}, \overline{y}\right) \right\}}\) w zbiorze \(\displaystyle{ \left\{ \overline{y} : \left| y \right| \right\ < p\left( \left| \overline{x} \right| \right) }}\) jest większa niż \(\displaystyle{ 1- \epsilon.}\)

\(\displaystyle{ \overline{x}\not \in L \Leftarrow}\) proporcja zbioru \(\displaystyle{ \left\{ y \in \left( \overline{x}, \overline{y}\right) \right\}}\) w zbiorze \(\displaystyle{ \left\{ \overline{y} : \left| y \right| \right\ < p\left( \left| \overline{x} \right| \right) }}\) jest większa niż \(\displaystyle{ \epsilon.}\)