[Teoria złożoności] Maszyna Turinga

[legolas]

Uzupełnij wyrażenie:

Niedeterministyczna maszyna Turinga w stosunku do maszyny deterministycznej dla tego samego problemu praktycznie (w sensie klasy złożoności) wykonuje ………. kroków, a zużywa ………. komórek taśmy

W polu może być: mniej, więcej, tyle samo

[Richard del Ferro]

więcej kroków, a zużywa mniej komórek taśmy

Zauważ, jaka jest różnica między Maszyną Turingą a DAS(Deterministyczny Automat Skończony).
DAS tylko czyta, a Turing może zmienić wartosc w każdym polu.

[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.}\)