Intuição por trás da relativização

10

Eu faço curso de Complexidade Computacional. Meu problema é que eu não entendo o método de relativização . Tentei encontrar um pouco de intuição em muitos livros didáticos, infelizmente, até agora sem sucesso. Apreciaria se alguém pudesse esclarecer esse assunto para que eu possa continuar sozinho. Poucas frases a seguir são perguntas e meus pensamentos sobre relativização, eles ajudarão a navegar na discussão.

Muitas vezes, a relativização é comparada à diagonalização, que é um método que ajuda a distinguir entre conjunto contável e conjunto incontável. De alguma forma, vem da relativização que a questão versus não pode ser resolvida pela diagonalização. Realmente não vejo a idéia de por que a relativização mostra o inútil da diagonalização e, se é inútil, por que é realmente inútil.N PPNP

A ideia por trás da máquina de Turing Oracle é muito clara. No entanto, quando se trata de e a intuição desaparece. O Oracle é uma caixa preta projetada para linguagem especial e responde à pergunta se a string na entrada do oráculo está no idioma no tempo 1. Como eu entendi a MT que contém um oráculo, basta fazer algumas operações auxiliares e perguntar ao oráculo. Portanto, o núcleo da TM é o oráculo, todo o resto é menos importante. Qual é a diferença entre e , até o pensamento oráculo em ambos funciona no tempo 1. N P A P A P A N P AMANPAPAPANPA

A última coisa é a provar a existência de um oráculo tal que . Encontrei a prova em vários livros didáticos e em todos eles a prova parece muito vaga. Tentei usar "Introdução à complexidade", de Sipser, capítulo 9. Intratabilidade e não teve a ideia de construir uma lista de todas as TMs oracle tempo polinomial .P BN P B M iBPBNPBMi

Isso é mais ou menos tudo o que sei sobre relativização. Apreciaria se alguém decidisse compartilhar seus pensamentos sobre o assunto.

Adendo : em um dos livros, encontrei um exemplo da linguagem (Complexidade Computacional: Uma Abordagem Moderna de Boaz Barak Sanjeev Arora. Teorema 3.7. Página 74). é uma linguagem unária. Eu acredito que (1,11,111,1111, ...) estão todos em . O autor afirma que essa linguagem está em que é que não consigo entender por que, portanto, o oracle para B pode resolver tudo no tempo 1. Por que precisamos da MT não determinística com o oracle. Se não for bom exemplo de favor coloque o seu tal que aprovar a existência de .L B = { 1 n : s o m e s t r i n g o f l e n g t h n i s i n B } L B N P B N P B N P BNPBUB={1n:some string of length n is in B}UBNPBNPBNPB

com
fonte
2
N P A APUMA e são classes de linguagem, não são máquinas de Turing. Você diz que o oráculo é o "núcleo" da MT, mas isso não é necessariamente verdade. Por exemplo, e se for o idioma vazio? NPUMAUMA
Yuval Filmus
é um tópico muito complicado, geralmente não muito para os estudantes de graduação. um aspecto é que os oráculos dependem um pouco do modelo. ou seja, aparentemente não há uma maneira estritamente consistente de conceber oráculos. a intuição básica é que é uma máquina com capacidade de sub-rotina "mágica" (dada pelo oráculo), de modo que a máquina + oráculo sempre seja pelo menos tão poderosa quanto a máquina original, mas às vezes não seja significativamente mais poderosa ...
vzn
11
pergunta relacionada: cs.stackexchange.com/questions/1271/… , com uma ótima resposta de Tsuyoshi Ito
A.Schulz
Não tenho certeza do que você está perguntando. Você parece estar confuso sobre a prova da BGS e também faz várias outras perguntas. Faça uma única pergunta focada. Observe que este não é um fórum ou fórum de discussão, é um site de perguntas e respostas.
Kaveh
Você está pedindo uma explicação da prova de BGS para a existência de um oráculo que separa P e NP? Você está pedindo uma explicação sobre a relação de relativização e diagonalização? (em caso afirmativo, se a resposta de Tsuyoshi na questão alinhada responder à sua pergunta se não explique por que não?).
Kaveh

Respostas:

7

Você realmente não pediu qualquer pergunta, mas parece que você não sabe o que meio e que meio de uma linguagem . A classe é simplesmente todos os idiomas que são decidíveis no "tempo NP", dada uma máquina de turing com como oráculo. Isso significa uma máquina de turing não determinística com acesso a que é executada em tempo polinomial. O é a versão determinística.N P A A N P A AA P APUMANPUMAUMANPUMAUMAUMAPUMA

Pål GD
fonte
11
Muito obrigado pela resposta, você poderia dar um exemplo de como o poder do NTM com a Oracle nos ajuda a reconhecer mais linguagem do que o DTM com a Oracle? A prova do BGS mostra esse idioma, mas não recebi a prova.
com
Às vezes, em vez de uma linguagem , encontro alguma classe de complexidade, por exemplo , o que isso significa neste caso? Que escolhemos para ser um NP-completo? (de modo mais geral, que escolhemos um idioma completo para a classe )? UMAPNPUMAUMA
Fawzy Hegab
Sim, é realmente com um problema NP-completo como um oráculo. PNPP
GD