Oracle (Turing maskine)

I teorien om kompleksitet eller beregningsevne er Turing-maskiner med orakler en variant af Turing-maskiner med en sort boks, et oracle, der er i stand til at løse et beslutningsproblem i en enkelt elementær operation. Især kan oraklet løse i konstant tid en uafgørligt problem sådan som standsning problem . Turing-maskiner med orakler anvendes især til at definere polynomhierarkiet eller det aritmetiske hierarki .

Intuitiv tilgang

En Turing-maskine med et orakel hjælpes af et orakel. Oraklet kan ses som en gud (det er bedre ikke at tænke på ham som en maskine), der er i stand til at løse et bestemt beslutningsproblem i konstant tid. Med andre ord giver vi et eksempel på dette problem input til oraklet, og det giver svaret i en konstant tid uafhængig af spørgsmålets størrelse. Dette problem kan være i enhver kompleksitetsklasse. Vi kan endda forestille os et orakel, der løser problemer, som ingen Turing-maskiner kan løse, det vil sige et ubeslutsomt problem som problemet med at stoppe .

Orakler er rent teoretiske værktøjer, da denne model omhyggeligt undgår at rejse spørgsmålet om deres funktion.

Definition

Lad L være et sprog. En Turing-maskine med oracle L er en Turing-maskine, hvor flere bånd med et bånd normalt fungerer, men også med et specielt bånd, tape-oraklet og tre specifikke tilstande , og . For at konsultere oraklet skriver maskinen et ord på dette bånd og går derefter ind i staten . Oraklet beslutter derefter i et beregningstrin, om følgende tilstand er eller afhængigt af om dette ord er en del af L-sproget eller ej. q?{\ displaystyle q_ {?}}qy{\ displaystyle q_ {y}}qikke{\ displaystyle q_ {n}}q?{\ displaystyle q_ {?}}qy{\ displaystyle q_ {y}}qikke{\ displaystyle q_ {n}}

Maskinen kan konsultere oraklet flere gange. Bemærk, at den samme maskine kan arbejde med forskellige orakler; det anerkendte sprog vil derefter på forhånd være anderledes.

Kompleksitetsklasser med orakler

Notationer

Vi bemærker, hvor A er en kompleksitetsklasse og L et sprog, klassen af ​​sprog, der genkendes af en klasse A-algoritme med sproget L som orakel. For eksempel, hvis P er den klasse af problemer, der er bestemt af en deterministisk Turing-maskine i polynom tid, og SAT er det sæt af propositionelle logiske formler, der er tilfredsstillende (se SAT-problem ), så er klassen af ​​polynomiske tidsopløselige problemer ved hjælp af et orakel, der løser SAT-problemet i konstant tid. PÅL{\ displaystyle A ^ {L}}PSPÅT{\ displaystyle P ^ {SAT}}

Vi bemærker også , hvor A og C er to kompleksitetsklasser, den klasse af sprog, der genkendes af en klasse A-algoritme med et orakel, hvis besluttede sprog hører til klasse C. Det er bevist, at hvis L er et komplet sprog i klasse C , derefter . Da SAT er NP-komplet . PÅVS{\ displaystyle A ^ {C}}PÅL=PÅVS{\ displaystyle A ^ {L} = A ^ {C}}PSPÅT=PIKKEP{\ displaystyle P ^ {SAT} = P ^ {NP}}

P og NP

Med hensyn til de klassiske kompleksitetsklasser har vi :, da vi kan omdanne en polynomial Turing-maskine med et polynomial orakel til en polynomial maskine uden et orakel. For at gøre dette skal du blot udskifte oracle-båndet med den maskine, der svarer til oracle-sproget. Vi ved det også , men spørgsmålet om lighed er åbent (se artiklen polynomisk hierarki ). PP=P{\ displaystyle P ^ {P} = P}IKKEP⊆PIKKEP{\ displaystyle NP \ subseteq P ^ {NP}}

Orakler blev brugt til at undersøge spørgsmålet om P = NP  :

Sætning (Baker, Gill, Solovay, 1975): der findes et sprog A sådan, at og der findes et sprog B sådan, at . PPÅ=IKKEPPÅ{\ displaystyle P ^ {A} = NP ^ {A}}PB≠IKKEPB{\ displaystyle P ^ {B} \ neq NP ^ {B}}

Eksistensen af ​​sprog A er ret let at fastslå: det er tilstrækkeligt at tage et orakel, der er kraftigt nok til, at forskellen i computerkraft mellem P og NP slettes. Faktisk er ethvert PSPACE-komplet sprog egnet. På den anden side er eksistensen af ​​B-sproget bemærkelsesværdig. Det tillader os imidlertid ikke at afgøre, om P = NP: man kan forestille sig, at beregningsmodellerne for den deterministiske og ikke-deterministiske Turing-maskine har den samme effekt på polynomisk tid, men at man drager bedre fordel af l 'oracle B end den anden.

Det er også muligt at finde et sprog , så ejendommen er ubeslutsom . jeg{\ displaystyle I}Pjeg=IKKEPjeg{\ displaystyle P ^ {I} = NP ^ {I}}

Andre resultater

Valiant og Vazirani demonstrerede, at hvor USAT er SAT-problemet, hvor vi lover, at den boolske inputformel højst har en løsning. Oracle hos USAT fungerer som følger: det reagerer positivt på formler, der har nøjagtigt en løsning, det reagerer negativt på formler uden en løsning, og det reagerer vilkårligt på andre formler. IKKEP⊆RPUSPÅT{\ displaystyle NP \ subseteq RP ^ {USAT}}

Den Toda sætning bruger også begrebet orakel.

Noter og referencer

1. Se øvelse 3.4.9 s. 68 i Computational Complexity af C. Papadimitriou.
2. LG Valiant og VV Vazirani , “  NP er lige så let som at opdage unikke løsninger  ”, Theoretical Computer Science , vol.  47,1 st januar 1986, s.  85–93 ( ISSN  0304-3975 , DOI  10.1016 / 0304-3975 (86) 90135-0 , læst online , adgang til 11. juli 2019 )

Bibliografi

• (en) Christos Papadimitriou , Computational Complexity , Addison-Wesley ,1993( ISBN  978-0-201-53082-7 )Afsnit 14.3: “  Orakler  ”, s.  339 - 343.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">