W polu może być: mniej, więcej, tyle samoNiedeterministyczna 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
[Teoria złożoności] Maszyna Turinga
-
- Użytkownik
- Posty: 320
- Rejestracja: 7 cze 2016, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 146 razy
- Pomógł: 3 razy
[Teoria złożoności] Maszyna Turinga
Uzupełnij wyrażenie:
Ostatnio zmieniony 13 sty 2018, o 19:21 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Richard del Ferro
- Użytkownik
- Posty: 190
- Rejestracja: 13 mar 2016, o 22:48
- Płeć: Mężczyzna
- Podziękował: 9 razy
- Pomógł: 16 razy
[Teoria złożoności] Maszyna Turinga
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.
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.
Maszyny niedeterministyczne
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.}\)
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.}\)