Pytania otagowane jako oracle-machines

4
Klasy złożoności, w których
Jedną z możliwych motywacji do badania klas złożoności obliczeniowej jest zrozumienie mocy różnych rodzajów zasobów obliczeniowych (losowość, niedeterminizm, efekty kwantowe itp.). Jeśli spojrzymy na to z tej perspektywy, wydaje się, że możemy uzyskać jeden wiarygodny aksjomat dla każdej próby scharakteryzowania, które obliczenia są wykonalne w pewnym modelu: Każde wykonalne obliczenie …
1
Dlaczego ten argument za
Wiem, że to głupie, ale udało mi się pomylić i potrzebuję pomocy w rozwiązaniu tego Załóżmy, że , więc wyraźnie dla każdej wyroczni mamy co zaprzecza faktowi, że istnieje pewna wyrocznia dla której , stądA P A = N P A A P A ≠ N P A P ≠ …
1
Czy są jakieś istniejące problemy, których nie można rozwiązać za pomocą wyroczni zatrzymującej?
Rozumiem, że większość problemów jest trywialna, jeśli dostępna jest wyrocznia zatrzymująca (lub, moim zdaniem, hiper-obliczenia). Jednak zastosowanie argumentu, który pokazuje, że problem zatrzymania jest niemożliwy dla maszyny Turinga, pokazuje również, że wyrocznia Turinga + nie może zdecydować o problemie zatrzymania dla wyroczni Turinga +. Czy istnieją jakieś rzeczywiste, praktyczne przykłady …
2
W jaki sposób korzystanie z maszyn wyroczni Turinga nie prowadzi do sprzeczności?
W jaki sposób możemy zagwarantować, że podczas korzystania z maszyn Turinga Oracle nadal będziemy wydawać prawidłowe i prawidłowe oświadczenia o klasach złożoności? Według mojego zrozumienia (na podstawie definicji podanych we wprowadzających podręcznikach na ten temat) maszyny oracle Turing mogą określić status członkostwa w łańcuchu znaków w odniesieniu do języka Oracle …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.