Màquina oracle

En teoria de la complexitat, una màquina oracle és màquina abstracta utilitzada per estudiar els problemes de decisió. Es pot veure com una màquina de Turing amb una caixa negra, anomenat oracle, que és capaç de solucionar certs problemes de decisió amb una sola operació. El problema pot ser de qualsevol classe de complexitat. Inclús es poden fer servir problemes que no son decidibles, com el problema de la parada.^[1]

Oracles

Una màquina oracle es pot veure com una màquina de Turing connectada a un oracle. L'oracle, en aquest context, és una entitat capaç de solucionar alguns problemes, com poden ser problemes de decisió o problemes de funció. El problema no ha de ser necessàriament computable perquè l'oracle no és necessàriament una màquina de Turing o un programa d'ordinador. L'oracle simplement és una caixa negra que pot proporcionar una solució per qualsevol instància d'un problema donat:

Un problema de decisió es representa com un conjunt A de nombres naturals (o cadenes). Una instància del problema és un nombre natural arbitrari (o cadena). La solució de la instància es SI si el nombre (cadena) és al conjunt A, i NO en cas contrari.
Un problema de funció es representa per una funció f de nombres naturals (o cadenes) cap a nombres naturals (o cadenes). Una instància del problema és una entrada x de f. La solució és el valor f(x).

Una màquina oracle pot realitzar totes les operacions habituals d'una màquina de Turing i també pot preguntar a l'oracle per obtenir la solució de qualsevol instància del problema de l'oracle. Per exemple, si el problema és un problema de decisió per un conjunt A de nombres naturals, la màquina oracle pot proporcionar un nombre natural a l'oracle i aquest respondrà amb SI o NO segons si el nombre pertany a A o no.

Definicions

Hi ha força definicions equivalents per màquines de Turing amb oracle. La que es presenta aquí ve de Melkebeek.^[2]^[3]

Una màquina oracle, com una màquina de Turing inclou:

una cinta de treball: una seqüència de cel·les sense inici ni final, on cadascuna conté una B (per blanc) o un símbol de l'alfabet de la cinta.
un capçal de lectura i escriptura que es posa sobre una cel·la i pot llegir el símbol que hi ha, escriure'n un i moure's una posició per la cinta en qualsevol dels dos sentits.
un mecanisme de control, que pot estar en un dels estats finits possibles, i que realitza diferents operacions (llegir o escriure una dada, moure el capçal i canviar l'estat) depenent de l'estat actual i la dada llegida.

Afegit a això, una màquina oracle també te:

una cinta oracle, una cinta semi-infinita separada de la cinta de treball. L'alfabet d'aquesta cinta pot ser diferent al de la cinta de treball.
un capçal de l'oracle, que actua igual que el capçal principal però per la cinta de l'oracle.
dos estats especials: PREGUNTA i RESPOSTA

De tant en tant, la màquina oracle pot entrar a l'estat PREGUNTA. Quan això passa, es realitzen les següents accions en un sol pas de computació:

el contingut de la cinta oracle es vist com una instància del problema de computació per l'oracle
es consulta l'oracle i el contingut de la cinta oracle es reemplaça per la solució d'aquella instància del problema
el capçal de l'oracle es mou a la primera posició de la cinta oracle
la màquina oracle canvia el seu estat a RESPOSTA.

Per tant, el fet de moure's a l'estat PREGUNTA fa que es rebi en un sol pas la solució a la instància del problema que hi havia escrita a la cinta de l'oracle.

Classes de complexitat de les màquines oracle

La classe de complexitat dels problemes de decisió que es poden solucionar per un algorisme a la classe A amb un oracle per un llenguatge L s'anomena A^L.

Per exemple, P^SAT és la classe de complexitat dels problemes que poden ser resolts en un temps polinòmic per una màquina de Turing determinsta amb un oracle pel problema de satisfacibilitat booleana.

La notació A^B es pot estendre a un conjunt de llenguatges B (o classe de complexitat B) fent servir la següent definició:

A^{B}=\bigcup _{L\in B}A^{L}

Quan un llenguatge és complet per una classe B, llavors A^L = A^B donada una màquina a A que pot executar reduccions en la definició de complet de la classe B. Per exemple, donat que SAP és NP-Complet respecte a la reducció en temps polinòmic, es te que P^SAT=P^NP.

Màquines oracle i el problema de la parada

Una màquina amb un oracle pel problema de la parada pot determinar si una màquina de Turing s'aturarà donada una entrada determinada, però no pot determinar, en general, si una màquina equivalent a ella mateixa s'aturarà. Això crea una jerarquia de màquines, cadascuna amb un oracle més potent que l'anterior. Aquesta jerarquia es fa servir per definir la jerarquia aritmètica.^[4]

Vegeu també

Referències

↑ Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.
↑ van., Melkebeek, Dieter. Randomness and completeness in computational complexity. Berlín: Springer-Verlag, 2000. ISBN 9783540445456.
↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
↑ 1946-, Börger, E. (Egon),. Computability, complexity, logic. Amsterdam: North-Holland, 1989. ISBN 9780444874061.

[1] Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.

[2] van., Melkebeek, Dieter. Randomness and completeness in computational complexity. Berlín: Springer-Verlag, 2000. ISBN 9783540445456.

[3] Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.

[4] 1946-, Börger, E. (Egon),. Computability, complexity, logic. Amsterdam: North-Holland, 1989. ISBN 9780444874061.

[1]

[2]

[3]

[4]