Пророчка машина

У теорији комплексности и теорији израчунљивости, пророчка машина (енгл. Oracle machine) је апстрактна машина која се користи за проучавање проблема одлучивања. Ова машина може да се замисли као Тјурингова машина са црном кутијом који се назива пророчиште, који је у стању да реши одређене проблеме у само једном кораку. Проблем може бити било које класе комплексности. Чак и неодлучиви проблеми, попут халтинг проблема долазе у обзир.

Дефиниција

Пророчка машина је Тјурингова машина повезана са пророчиштем. Тјурингова машина може да пише по својој траци, и да даје улаз пророчишту, као и да му нареди извршавање. Пророчиште у једном кораку рачуна своју функцију, брише улаз, и записује излаз на траку. Некад се Тјурингова машина описује са две траке, једна која је резервисана за улаз пророчишта, а друга која је резервисана за његов излаз.

Класе комплексности и пророчке машине

Класа комплексности проблема одлучивања решивих алгоритмом из класе A са пророчком машином за проблем у класи B се записује A^B. На пример, класа проблема решивих у полиномијалном времену детерминистичком Тјуринговом машином са пророчком машином за проблем у класи NP је P^NP.

Јасно је да је NP ⊆ P^NP, али је још увек отворено питање да ли су NP^NP, P^NP, NP, и P једнаки.

Нотација A^B такође означава класу проблема решивих алгоритмом класе A са пророчком машином за језик B. На пример, P^SAT је класа проблема решивих у полиномијалном времену детерминистичком Тјуринговом машином са пророчиштем за Буловски проблем задовољивости. Када је језик B комплетан за неку класу C, тада A^B=A^C. Специјално, пошто је SAT -{NP-комплетан, P^SAT=P^NP.

Пророчке машине су корисне за изучавање односа између класа комплексности P и NP, разматрањем односа између P^A и NP^A за пророчку машину A. Специјално, показано је да постоје језици A и B, такви да P^A=NP^A и P^B≠NP^B.

Интересантно је посматрати случај када када се пророчка машина бира случајно из скупа свих могућих пророчких машина. Показано је да ако је пророчиште A изабрајно случајно, тада са вероватноћом 1, P^A≠NP^A. Када је питање тачно за скоро сваку пророчку машину, каже се да је тачно за случајно пророчиште. Ово се понекад узима као доказ да P≠NP. Нажалост, исказ може бити тачан за случајну пророчку машину, а истовремено нетачан за обичну Тјурингову машину.

Пророчка машина и халтинг проблеми

Могуће је узети пророчку машину која рачуна неизрачунљиву функцију, и даје одговор на халтинг проблем или неки еквивалентан проблем. Машина са оваквим пророчиштем је хиперрачунар.

Интересантно је приметити да халтинг парадокс и даље важи на ове машине; то јест, иако ове машине могу да одреде да ли појединачна Тјурингова машина стаје за појединачан улаз, не могу да одреде да ли машине са еквивалентним халтинг пророчиштима и саме стају. Ова чињеница даје хијерархију машина, која се назива аритметичка хијерархија, са све моћнијим халтинг пророчиштем и све тежим халтинг проблемом.

Примене у криптографији

Једна од уобичајених примена пророчких машина у модерном рачунарству је у криптографским протоколима. Ако претпоставимо постојање случајног пророчишта које даје случајну (али конзистентну) ниску као одговор на било које питање, онда се ради о супер-сигурној једносмерној функцији. То јест, ако је дат излаз из пророчке машине, немогуће је написати програм који ће наћи улаз који производи тај излаз, изузев испитивањем много улаза. Ово води до врло снажних протокола, али за имплементирање ових протокола у пракси се пророчке машине обично замењују генератором псеудослучајних бројева. Ово међутим у општем случају није толико сигурно.

Литература

• 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.