Proročka mašina

U teoriji kompleksnosti i teoriji izračunljivosti, proročka mašina (engl. Oracle machine) je apstraktna mašina koja se koristi za proučavanje problema odlučivanja. Ova mašina može da se zamisli kao Tjuringova mašina sa crnom kutijom koji se naziva proročište, koji je u stanju da reši određene probleme u samo jednom koraku. Problem može biti bilo koje klase kompleksnosti. Čak i neodlučivi problemi, poput halting problema dolaze u obzir.

Definicija

Proročka mašina je Tjuringova mašina povezana sa proročištem. Tjuringova mašina može da piše po svojoj traci, i da daje ulaz proročištu, kao i da mu naredi izvršavanje. Proročište u jednom koraku računa svoju funkciju, briše ulaz, i zapisuje izlaz na traku. Nekad se Tjuringova mašina opisuje sa dve trake, jedna koja je rezervisana za ulaz proročišta, a druga koja je rezervisana za njegov izlaz.

Klase kompleksnosti i proročke mašine

Klasa kompleksnosti problema odlučivanja rešivih algoritmom iz klase A sa proročkom mašinom za problem u klasi B se zapisuje A^B. Na primer, klasa problema rešivih u polinomijalnom vremenu determinističkom Tjuringovom mašinom sa proročkom mašinom za problem u klasi NP je P^NP.

Jasno je da je NP ⊆ P^NP, ali je još uvek otvoreno pitanje da li su NP^NP, P^NP, NP, i P jednaki.

Notacija A^B takođe označava klasu problema rešivih algoritmom klase A sa proročkom mašinom za jezik B. Na primer, P^SAT je klasa problema rešivih u polinomijalnom vremenu determinističkom Tjuringovom mašinom sa proročištem za Bulovski problem zadovoljivosti. Kada je jezik B kompletan za neku klasu C, tada A^B=A^C. Specijalno, pošto je SAT -{NP-kompletan, P^SAT=P^NP.

Proročke mašine su korisne za izučavanje odnosa između klasa kompleksnosti P i NP, razmatranjem odnosa između P^A i NP^A za proročku mašinu A. Specijalno, pokazano je da postoje jezici A i B, takvi da P^A=NP^A i P^B≠NP^B.

Interesantno je posmatrati slučaj kada kada se proročka mašina bira slučajno iz skupa svih mogućih proročkih mašina. Pokazano je da ako je proročište A izabrajno slučajno, tada sa verovatnoćom 1, P^A≠NP^A. Kada je pitanje tačno za skoro svaku proročku mašinu, kaže se da je tačno za slučajno proročište. Ovo se ponekad uzima kao dokaz da P≠NP. Nažalost, iskaz može biti tačan za slučajnu proročku mašinu, a istovremeno netačan za običnu Tjuringovu mašinu.

Proročka mašina i halting problemi

Moguće je uzeti proročku mašinu koja računa neizračunljivu funkciju, i daje odgovor na halting problem ili neki ekvivalentan problem. Mašina sa ovakvim proročištem je hiperračunar.

Interesantno je primetiti da halting paradoks i dalje važi na ove mašine; to jest, iako ove mašine mogu da odrede da li pojedinačna Tjuringova mašina staje za pojedinačan ulaz, ne mogu da odrede da li mašine sa ekvivalentnim halting proročištima i same staju. Ova činjenica daje hijerarhiju mašina, koja se naziva aritmetička hijerarhija, sa sve moćnijim halting proročištem i sve težim halting problemom.

Primene u kriptografiji

Jedna od uobičajenih primena proročkih mašina u modernom računarstvu je u kriptografskim protokolima. Ako pretpostavimo postojanje slučajnog proročišta koje daje slučajnu (ali konzistentnu) nisku kao odgovor na bilo koje pitanje, onda se radi o super-sigurnoj jednosmernoj funkciji. To jest, ako je dat izlaz iz proročke mašine, nemoguće je napisati program koji će naći ulaz koji proizvodi taj izlaz, izuzev ispitivanjem mnogo ulaza. Ovo vodi do vrlo snažnih protokola, ali za implementiranje ovih protokola u praksi se proročke mašine obično zamenjuju generatorom pseudoslučajnih brojeva. Ovo međutim u opštem slučaju nije toliko sigurno.

Literatura

• Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 - 343.
• T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
• C. H. Bennett, J. Gill. Relative to a Random Oracle A, P^A!= NP^A!= co-NP^Awith Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6.  Section 9.2: Relativization, pp. 318 - 321.
• Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.