Máquina Oracle - Oracle machine

Sistemas de caixa preta
Sistema
Caixa preta  · Máquina Oracle
Métodos e técnicas
Teste de caixa-preta  · Blackboxing
Técnicas relacionadas
Feed Forward  · Obfuscation  · Reconhecimento de padrões  · Caixa branca  · teste de caixa branca  · Identificação do sistema
Fundamentos
A priori informação  · Os sistemas de controle  · Os sistemas abertos  · operações de pesquisa  · sistemas termodinâmicos
v t e

Na teoria da complexidade e na teoria da computabilidade , uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão . Pode ser visualizado como uma máquina de Turing com uma caixa preta , chamada oráculo , que é capaz de resolver certos problemas em uma única operação. O problema pode ser de qualquer classe de complexidade . Mesmo problemas indecidíveis , como o problema da parada , podem ser usados.

Oráculos

Uma máquina oráculo pode ser concebida como uma máquina de Turing conectada a um oráculo . O oráculo, neste contexto, é uma entidade capaz de resolver algum problema, que por exemplo pode ser um problema de decisão ou um problema de função . O problema não precisa ser computável; o oráculo não é considerado uma máquina de Turing ou programa de computador. O oráculo é simplesmente uma " caixa preta " que é capaz de produzir uma solução para qualquer instância de um determinado problema computacional:

• Um problema de decisão é representado como um conjunto A de números naturais (ou strings). Uma instância do problema é um número natural arbitrário (ou string). A solução para a instância é "SIM" se o número (string) estiver no conjunto e "NÃO" caso contrário.
• Um problema de função é representado por uma função f de números naturais (ou strings) para números naturais (ou strings). Uma instância do problema é uma entrada x para f . A solução é o valor f ( x ).

Uma máquina oráculo pode realizar todas as operações usuais de uma máquina de Turing e também pode consultar o oráculo para obter uma solução para qualquer instância do problema computacional para aquele oráculo. Por exemplo, se o problema é um problema de decisão para um conjunto A de números naturais, a máquina do oráculo fornece ao oráculo um número natural, e o oráculo responde com "sim" ou "não", informando se esse número é um elemento de A .

Definições

Existem muitas definições equivalentes de máquinas de Turing do oráculo, conforme discutido abaixo. O apresentado aqui é de van Melkebeek (2000: 43).

Uma máquina oráculo, como uma máquina de Turing, inclui:

• uma fita de trabalho : uma seqüência de células sem começo ou fim, cada uma das quais pode conter um B (para espaço em branco) ou um símbolo do alfabeto da fita;
• um cabeçote de leitura / gravação , que fica em uma única célula da fita de trabalho e pode ler os dados lá, gravar novos dados e aumentar ou diminuir sua posição ao longo da fita;
• um mecanismo de controle , que pode estar em um de um número finito de estados , e que executará diferentes ações (leitura de dados, gravação de dados, movimentação do mecanismo de controle e alteração de estados) dependendo do estado atual e dos dados que estão sendo lidos.

Além desses componentes, uma máquina oracle também inclui:

• uma fita de oráculo , que é uma fita semi-infinita separada da fita de trabalho. O alfabeto da fita do oráculo pode ser diferente do alfabeto da fita de trabalho.
• uma cabeça de oráculo que, como a cabeça de leitura / gravação, pode se mover para a esquerda ou direita ao longo da fita do oráculo lendo e escrevendo símbolos;
• dois estados especiais: o estado ASK e o estado RESPONSE.

De vez em quando, a máquina oracle pode entrar no estado ASK. Quando isso acontece, as seguintes ações são realizadas em uma única etapa computacional:

• o conteúdo da fita do oráculo é visto como uma instância do problema computacional do oráculo;
• o oráculo é consultado e o conteúdo da fita do oráculo é substituído pela solução para aquela instância do problema;
• a cabeça do oráculo é movida para o primeiro quadrado na fita do oráculo;
• o estado da máquina oracle é alterado para RESPONSE.

O efeito da mudança para o estado ASK é, portanto, receber, em uma única etapa, uma solução para a instância do problema que está gravada na fita do oracle.

Definições alternativas

Existem muitas definições alternativas à apresentada acima. Muitos deles são especializados para o caso em que o oráculo resolve um problema de decisão. Nesse caso:

• Algumas definições, em vez de escrever a resposta na fita do oráculo, têm dois estados especiais SIM e NÃO, além do estado ASK. Quando o oráculo é consultado, o próximo estado é escolhido como SIM se o conteúdo da fita do oráculo estiver no conjunto do oráculo e como NÃO se o conteúdo não estiver no conjunto do oráculo (Adachi 1990: 111).
• Algumas definições evitam a fita do oráculo separada. Quando o estado oracle é inserido, um símbolo de fita é especificado. O oráculo é consultado com o número de vezes que este símbolo de fita aparece na fita de trabalho. Se esse número estiver no conjunto do oráculo, o próximo estado é o estado SIM; se não for, o próximo estado é o estado NÃO (Rogers 1967: 129).
• Outra definição alternativa torna a fita do oracle somente leitura e elimina os estados ASK e RESPONSE inteiramente. Antes da máquina ser iniciada, a função do indicador do conjunto oráculo é escrita na fita do oráculo usando os símbolos 0 e 1. A máquina é então capaz de consultar o oráculo escaneando para o quadrado correto na fita do oráculo e lendo o valor localizado lá (Soare 1987: 47, Rogers 1967: 130).

Essas definições são equivalentes do ponto de vista da computabilidade de Turing: uma função é computável por oráculo a partir de um determinado oráculo sob todas essas definições se for computável por oráculo sob qualquer uma delas. As definições não são equivalentes, entretanto, do ponto de vista da complexidade computacional. Uma definição como a de van Melkebeek, usando uma fita de oráculo que pode ter seu próprio alfabeto, é exigida em geral.

Classes de complexidade de máquinas oracle

A classe de complexidade de problemas de decisão que podem ser resolvidos por um algoritmo na classe A com um oráculo para uma linguagem L é chamado de ^L . Por exemplo, P ^SAT é a classe de problemas solucionáveis ​​em tempo polinomial por uma máquina de Turing determinística com um oráculo para o problema de satisfatibilidade booleana . A notação A ^B pode ser estendida a um conjunto de linguagens B (ou uma classe de complexidade B), usando a seguinte definição:

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

Quando uma linguagem L está completa para alguma classe B, então A ^L = A ^B, desde que as máquinas em A possam executar reduções usadas na definição de completude da classe B. Em particular, uma vez que SAT é NP-completo com respeito às reduções de tempo polinomial, P ^SAT = P ^NP . No entanto, se A = DLOGTIME , então A ^SAT pode não ser igual a A ^NP . (Observe que a definição de dado acima não é completamente padrão. Em alguns contextos, como a prova dos teoremas da hierarquia de tempo e espaço , é mais útil assumir que a máquina abstrata que define a classe só tem acesso a um único oráculo para um idioma. Neste contexto, não é definido se a classe de complexidade não apresenta problemas completos no que diz respeito às reduções disponíveis para .) ${\ displaystyle A ^ {B}}$${\ displaystyle A}$${\ displaystyle A ^ {B}}$${\ displaystyle B}$${\ displaystyle A}$

Entende-se que NP ⊆ P ^NP , mas a questão de saber se NP ^NP , P ^NP , NP e P são iguais permanece, na melhor das hipóteses, provisória. Acredita-se que sejam diferentes, o que leva à definição da hierarquia polinomial .

As máquinas Oracle são úteis para investigar a relação entre as classes de complexidade P e NP , considerando a relação entre P ^A e NP ^A para um oráculo A. Em particular, foi demonstrado que existem linguagens A e B tais que P ^A = NP ^A e P ^B ≠ NP ^B (Baker, Gill e Solovay 1975). O fato de a questão P = NP relativizar nos dois sentidos é tomado como evidência de que responder a essa questão é difícil, porque uma técnica de prova que relativiza (isto é, não afetada pela adição de um oráculo) não responderá à questão P = NP. A maioria das técnicas de prova relativiza.

Pode-se considerar o caso em que um oráculo é escolhido aleatoriamente entre todos os oráculos possíveis (um conjunto infinito). Foi demonstrado, neste caso, que com probabilidade 1, P ^A ≠ NP ^A (Bennett e Gill 1981). Quando uma pergunta é verdadeira para quase todos os oráculos, diz-se que é verdadeira para um oráculo aleatório . Essa escolha de terminologia é justificada pelo fato de que oráculos aleatórios apóiam uma afirmação com probabilidade 0 ou 1 apenas. (Isso segue da lei zero um de Kolmogorov .) Essa é apenas uma evidência fraca de que P ≠ NP, uma vez que uma afirmação pode ser verdadeira para um oráculo aleatório, mas falsa para máquinas de Turing comuns; por exemplo, IP ^A ≠ PSPACE ^A para um oráculo aleatório A mas IP = PSPACE (Chang et al., 1994).

Oráculos e problemas de parada

Uma máquina com um oráculo para o problema da parada pode determinar se máquinas de Turing particulares irão parar em determinadas entradas, mas não pode determinar, em geral, se máquinas equivalentes a ela irão parar. Isso cria uma hierarquia de máquinas, cada uma com um oráculo de parada mais poderoso e um problema de parada ainda mais difícil. Essa hierarquia de máquinas pode ser usada para definir a hierarquia aritmética (Börger 1989).

Aplicações para criptografia

Na criptografia , os oráculos são usados ​​para fazer argumentos para a segurança de protocolos criptográficos onde uma função hash é usada. Uma redução de segurança para o protocolo é dada no caso em que, em vez de uma função hash, um oráculo aleatório responde a cada consulta aleatoriamente, mas de forma consistente; presume-se que o oráculo esteja disponível para todas as partes, incluindo o invasor, como está a função hash. Tal prova mostra que, a menos que o invasor resolva o problema difícil no centro da redução da segurança, ele deve fazer uso de alguma propriedade interessante da função hash para quebrar o protocolo; eles não podem tratar a função hash como uma caixa preta (ou seja, como um oráculo aleatório).

Veja também

• Grupo caixa preta
• Redução de Turing
• Sistema de prova interativo
• Oráculo de matróide

Referências

• Akeo Adachi, Foundations of computation theory , Ohmsha, 1990.
• TP Baker, J. Gill, R. Solovay . Relativizações do P =? NP Question . SIAM Journal on Computing , 4 (4): 431-442 (1975)
• CH Bennett, J. Gill. Em relação a um Oracle A aleatório, P ^A  ! = NP ^A  ! = Co-NP ^A com Probabilidade 1 . SIAM Journal on Computing, 10 (1): 96-113 (1981)
• Egon Börger. "Computabilidade, complexidade, lógica". North-Holland, 1989.
• Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis , Johan Hastad, Desh Ranjan, Pankaj Rohatgi. A hipótese do Oracle Random é falsa. Journal of Computer and System Sciences , volume 49, edição 1, pp. 24-39. Agosto de 1994. ISSN  0022-0000 . http://citeseer.ist.psu.edu/282397.html
• Martin Davis , editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions , Raven Press, New York, 1965. O artigo de Turing encontra-se neste volume. Os artigos incluem os de Gödel, Church, Rosser, Kleene e Post.
• Christos Papadimitriou . Complexidade computacional . Addison-Wesley, 1994. Seção 14.3: Oráculos, pp. 339-343.
• Hartley Rogers, Jr. , Teoria de Funções Recursivas e Computabilidade Efetiva , McGraw-Hill, 1967.
• Michael Sipser . Introdução à Teoria da Computação . PWS Publishing, 1997. ISBN  0-534-94728-X . Seção 9.2: Relativização, pp. 318-321.
• Robert I. Soare , Recursively Enumerable Sets and Degrees , Perspectives in Mathematical Logic, Springer, 1987.
• Alan Turing , Systems of logic based on ordinals , Proc. Matemática de Londres. soc., 45 , 1939
• Dieter van Melkebeek, Randomness and Completeness in Computational Complexity , Lecture Notes in Computer Science 1950, Springer, 2000.