Oraakkelikone

Wikipediasta
Siirry navigaatioon Siirry hakuun

Oraakkelikone on laskennan vaativuusteoriassa abstrakti kone, jota käytetään päätösongelmien ratkaisun tutkimiseen. Oraakkelikone on Turingin kone, johon on kytketty "oraakkeli", joka pystyy ratkaisemaan päätösongelmia (yleensä rajatusta joukosta) yhdellä operaatiolla. Ongelmat voivat olla mitä tahansa vaativuusluokkaa. Myös ratkeamattomat ongelmat, kuten pysähtymisongelma, ratkeavat oraakkelin avulla. Tällöin on kyse eräästä hyperlaskennan mallista.

Oraakkelikonetta käytetään tutkittaessa eri vaativuusluokkien, kuten P ja NP, suhdetta.

Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.