Кіріспе
Шешім қабылдау мәселелерін зерттеуге қолданылатын абстрактілі машина. Oracle Corporation компаниясы сататын есептеу жабдықтары.
computing equipment sold by Oracle Corporation
Күрделілік теориясы мен есептеу теориясында оракул машинасы – шешім қабылдау мәселелерін зерттеуге арналған абстрактілі машина. Оны бір операцияда белгілі бір мәселелерді шеше алатын "оракул" деп аталатын қара қораппен жабдықталған Тьюринг машинасы ретінде көруге болады. Мәселе кез келген күрделілік класына жатуы мүмкін. Тіпті шешілмейтін мәселелер, мысалы, тоқтау мәселесі де қолданылуы мүмкін.
Оракулдар
Оракул машинасы оракулға қосылған Тьюринг машинасы ретінде қарастырылуы мүмкін. Оракул, осы контексте, кейбір мәселені шеше алатын бірлік, мысалы, шешім қабылдау мәселесі немесе функциялық мәселе болуы мүмкін. Мәселе міндетті түрде есептелуге жарамды болуы керек емес; оракул Тьюринг машинасы немесе компьютерлік бағдарлама деп есептелмейді. Оракул – бұл белгілі бір есептеу мәселесінің кез келген мысалы үшін шешім бере алатын "қара жәшік": Шешім қабылдау мәселесі A табиғи сандар (немесе жолдар) жиыны ретінде ұсынылады. Мәселенің мысалы – кез келген табиғи сан (немесе жол). Егер сан (жол) жиынтықта болса, мысалға жауап "ИӘ", әйтпесе "ЖОҚ". Функциялық мәселе f функциясы арқылы табиғи сандардан (немесе жолдардан) табиғи сандарға (немесе жолдарға) бейнеленеді. Мәселенің мысалы – f үшін x кіріс. Шешім – f(x) мәні. Оракул машинасы Тьюринг машинасының барлық стандартты операцияларын орындай алады, сонымен қатар оракулдан осы оракул үшін есептеу мәселесінің кез келген мысалының шешімін алу үшін сұрау жіберуге болады. Мысалы, егер мәселе A табиғи сандар жиыны үшін шешім қабылдау мәселесі болса, оракул машинасы оракулға табиғи санды жібереді, ал оракул сол сан A жиынының мүшесі екенін көрсететін "иә" немесе "жоқ" деп жауап береді.
A decision problem is represented as a set A of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise. A function problem is represented by a function f from natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input x for f. The solution is the value f(x). An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if the problem is a decision problem for a set A of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of A.
Баламалы анықтамалар
Жоғарыда келтірілген анықтамаға көптеген балама анықтамалар бар. Олардың көпшілігі оракул шешімдік есепті шешетін жағдайға арналған. Бұл жағдайда: Кейбір анықтамалар оракул таспасына жауап жазудың орнына, ASK күйіне қосымша екі арнайы күй – ИӘ және ЖОҚ күйлерін қосады. Оракулға жүгінген кезде, егер оракул таспасының мазмұны оракул жиынында болса, келесі күй ИӘ деп таңдалады, ал мазмұны оракул жиынында болмаса, ЖОҚ деп таңдалады. Кейбір анықтамаларда жеке оракул таспасын пайдаланудан аулақ тұру ұсынылады. Оракул күйіне кіргенде, таспа символы көрсетіледі. Оракул жұмыс таспасында осы таспа символы неше рет кездесетінін анықтау арқылы сұралады. Егер бұл сан оракул жиынында болса, келесі күй ИӘ күйі болады; әйтпесе, келесі күй ЖОҚ күйі болады. Тағы бір балама анықтама оракул таспасын тек оқуға арналған етіп белгілейді және ASK және ЖАУАП күйлерін толығымен жояды. Машинаны іске қосу алдында, оракул жиынының индикаторлық функциясы 0 және 1 символдары арқылы оракул таспасына жазылады. Содан кейін машина оракул таспасындағы тиісті жаққа қарап, ондағы мәнді оқып оракулға сұрақ қоя алады. Бұл анықтамалар Тьюрингтік есептеу тұрғысынан эквивалентті: функция, егер ол олардың кез келгенінде оракулмен есептелсе, осы анықтамалар бойынша берілген оракулдан оракулмен есептелуі мүмкін. Алайда, анықтамалар есептеу күрделілігі тұрғысынан эквивалентті емес. Ван Мелкебектің анықтамасындай, өзінің әліпбиі болуы мүмкін оракул таспасын пайдалану, әдетте қажет.
Some definitions, instead of writing the answer to the oracle tape, have two special states YES and NO in addition to the ASK state. When the oracle is consulted, the next state is chosen to be YES if the contents of the oracle tape are in the oracle set, and chosen to the NO if the contents are not in the oracle set. Some definitions eschew the separate oracle tape. When the oracle state is entered, a tape symbol is specified. The oracle is queried with the number of times that this tape symbol appears on the work tape. If that number is in the oracle set, the next state is the YES state; if it is not, the next state is the NO state. Another alternative definition makes the oracle tape read only, and eliminates the ASK and RESPONSE states entirely. Before the machine is started, the indicator function of the oracle set is written on the oracle tape using symbols 0 and 1. The machine is then able to query the oracle by scanning to the correct square on the oracle tape and reading the value located there. These definitions are equivalent from the point of view of Turing computability: a function is oracle computable from a given oracle under all of these definitions if it is oracle computable under any of them. The definitions are not equivalent, however, from the point of view of computational complexity. A definition such as the one by van Melkebeek, using an oracle tape which may have its own alphabet, is required in general.
Оракул машиналарының күрделілік сыныптары
L тілі үшін оракулмен A класындағы алгоритммен шешілетін шешімдік проблемалардың күрделілік класы AL деп аталады. Мысалы, PSAT – Бульдік қанағаттандыру проблемасы үшін оракулмен детерминистік Тьюринг машинасымен полиномиалдық уақытта шешілетін проблемалар класы. AB белгісін келесі анықтаманы қолдану арқылы B тілдерінің жиынтығына (немесе B күрделілік класына) кеңейтуге болады: Егер L тілі B класы үшін толық болса, онда AL=AB, егер A класындағы машиналар B класының толықтығының анықтамасында қолданылатын қысқартуларды орындай алса. Атап айтқанда, SAT полиномиалдық уақыт қысқартуларына қатысты NP толық болғандықтан, PSAT=PNP. Алайда, егер A = DLOGTIME болса, онда ASAT, ANP-ге тең болмауы мүмкін. (Жоғарыда берілген анықтама толыққанды стандартты емес. Кейбір жағдайларда, мысалы, уақыт және кеңістік иерархиясы теоремаларын дәлелдеуде, абстрактілі машинаны анықтайтын класс тек бір тіл үшін бір оракулға қол жеткізе алады деп қарастыру пайдалы. Бұл жағдайда, егер B класы толыққанды анықталмаған болса, оған қолжетімді қысқартулар бойынша толық проблемалар болмайды. NP ⊆ PNP деп түсініледі, бірақ NPNP, PNP, NP және P теңдігі туралы мәселе ең жақсы жағдайда күмәнді болып қалады. Олардың әртүрлі екеніне сеніледі, және бұл полиномиалдық иерархияның анықтамасына әкеледі. Оракул машиналары А оракулы үшін PA және NPA арасындағы қатынасты қарастыра отырып, күрделілік классстары P және NP арасындағы қатынасты зерттеу үшін пайдалы. Атап айтқанда, PA=NPA және PB≠NPB сияқты A және B тілдері бар екені көрсетілді. P = NP сұрағының екі жаққа да салыстырмалы түрде қарастырылуы бұл сұраққа жауап беру қиын екендігінің дәлелі ретінде қарастырылады, өйткені салыстырмалы түрде қарастырылатын дәлелдеу әдісі (яғни оракулдың қосылуынан әсер етпейтін) P = NP сұрағына жауап бермейді. Дәлелдеудің көп бөлігі салыстырмалы түрде жасалады. Оракулдың барлық мүмкін оракулдардың (шексіз жиынтық) арасынан кездейсоқ таңдалуын қарастыруға болады. Бұл жағдайда, 1 ықтималдығымен PA≠NPA екені көрсетілді. Егер сұрақ барлық оракулдар үшін дұрыс болса, онда ол кездейсоқ оракул үшін де дұрыс деп айтылады. Мұндай терминологияны таңдау кездейсоқ оракулдардың тек 0 немесе 1 ықтималдығымен мәлімдемені қолдауымен негізделген. (Бұл Колмогоровтың нөлден бірге дейінгі заңынан туындайды.) Бұл P≠NP үшін тек әлсіз дәлел, өйткені мәлімдеме кездейсоқ оракул үшін дұрыс, бірақ қарапайым Тьюринг машиналары үшін жалған болуы мүмкін; мысалы, кездейсоқ оракул A үшін IPA≠PSPACEA, бірақ IP = PSPACE.
When a language L is complete for some class B, then AL=AB provided that machines in A can execute reductions used in the completeness definition of class B. In particular, since SAT is NP complete with respect to polynomial time reductions, PSAT=PNP. However, if A = DLOGTIME, then ASAT may not equal ANP. (The definition of given above is not completely standard. In some contexts, such as the proof of the time and space hierarchy theorems, it is more useful to assume that the abstract machine defining class only has access to a single oracle for one language. In this context, is not defined if the complexity class does not have any complete problems with respect to the reductions available to .) It is understood that NP ⊆ PNP, but the question of whether NPNP, PNP, NP, and P are equal remains tentative at best. It is believed they are different, and this leads to the definition of the polynomial hierarchy. Oracle machines are useful for investigating the relationship between complexity classes P and NP, by considering the relationship between PA and NPA for an oracle A. In particular, it has been shown there exist languages A and B such that PA=NPA and PB≠NPB. The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because a proof technique that relativizes (i. e., unaffected by the addition of an oracle) will not answer the P = NP question. Most proof techniques relativize. One may consider the case where an oracle is chosen randomly from among all possible oracles (an infinite set). It has been shown in this case, that with probability 1, PA≠NPA. When a question is true for almost all oracles, it is said to be true for a random oracle. This choice of terminology is justified by the fact that random oracles support a statement with probability 0 or 1 only. (This follows from Kolmogorov's zero–one law.) This is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines; for example, IPA≠PSPACEA for a random oracle A but IP = PSPACE.
Оракулдар мен тоқтату проблемалары
Тоқтату мәселесіне оракул бар машина нақты Тьюринг машиналарының нақты кірістерде тоқтатылуын анықтай алады, бірақ ол, жалпы алғанда, өзімен эквивалентті машиналардың тоқтатылуын анықтай алмайды. Бұл машиналардың иерархиясын құрайды, олардың әрқайсысы күштірек тоқтату оракулымен және одан да қиын тоқтату мәселесімен жабдықталған. Осы машиналардың иерархиясын арифметикалық иерархияны анықтау үшін пайдалануға болады.
Криптографияға қолдану
Криптографияда оракулдар шифрлау протоколдарының қауіпсіздігін дәлелдеу үшін қолданылады, әсіресе хэш-функция қолданылған жағдайларда. Протоколдың қауіпсіздігін төмендету мына жағдайда беріледі: хэш-функцияның орнына кездейсоқ оракул әр сұрауға кездейсоқ, бірақ тұрақты түрде жауап береді. Оракул, хэш-функция сияқты, барлық тараптарға, соның ішінде шабуылшыға қолжетімді деп есептеледі. Мұндай дәлел шабуылшы қауіпсіздікті төмендетудің негізгі қиын мәселесін шеше алмаса, протоколды бұзу үшін хэш-функцияның белгілі бір қасиеттерін пайдалануға мәжбүр болатынын көрсетеді; олар хэш-функцияны қара жәшік ретінде (яғни, кездейсоқ оракул ретінде) қарастыра алмайды.