Técnicas para provar que uma sentença é relativizada

8

Estou interessado em como alguém prova que uma sentença é relativizada. Evidentemente, provar que uma sentença não se relativiza é simples, como visto no resultado de Baker-Gill-Solovay; mas como provar que uma sentença é relativizada, isto é, verdadeira em relação a qualquer oráculo? Existem técnicas conhecidas para conseguir isso em sentenças arbitrárias?

Se você conhece alguma referência que aborda essa questão, eu gostaria de ouvi-la. Obrigado.

Philip White
fonte
não basta ter uma prova da sentença que funciona em relação a todos os oráculos? Um exemplo típico será de teoremas de hierarquia.
Sasho Nikolov
Não tenho certeza. E se você não tiver certeza se a frase é verdadeira, mas gostaria de saber se a frase seria relativizada se fosse verdadeira?
Philip White
Qual é a definição de "sentença relativiza"? O que você quer dizer com "técnicas para conseguir isso para sentenças arbitrárias"?
Kaveh
1
Bem, acho que provar que é relativo a qualquer oráculo ainda é uma técnica :) Estou me perguntando se conhecemos algum exemplo de uma proposição sobre TMs que não foi comprovada, mas é conhecida como verdadeira ou falsa em relação a qualquer oráculo (é isso que você ? direito média como disse Kaveh, alguns formalização ajudaria)
Sasho Nikolov
1
@ Kaveh, quero dizer uma afirmação matemática que (presumivelmente) faz referência a máquinas de Turing. A afirmação "relativiza" se, no caso de adicionarmos um oráculo para uma máquina de Turing, a afirmação permanece verdadeira ou falsa.
Philip White

Respostas:

12

Normalmente, a maneira como as pessoas provam que um teorema da complexidade é relativizado está usando o seguinte procedimento de duas etapas:

  1. Prove o teorema.

  2. Observe que sua prova relativiza! Em outras palavras, nada na prova muda se todas as máquinas mencionadas na prova obtiverem acesso ao mesmo oráculo A.

Sim, é realmente tão simples assim. Para torná-lo rigoroso, você deve reescrever toda a prova adicionando sobrescritos de "A" em todo o lugar. Na prática, no entanto, se as pessoas perceberem esse problema, geralmente adicionarão um comentário como "esse resultado é facilmente relativizado".

Se as pessoas parecem arrogantes sobre isso, é porque elas aprenderam, por experiência própria, que apenas certas técnicas (como a aritmetização) podem causar uma prova para não relativizar. Portanto, se sua prova não usar essas técnicas, será relativizada.

(Uma analogia próxima: suponha que você prove um teorema sobre números reais, mas sua prova nunca usa nada sobre os reais, exceto o fato de serem um campo. Então basta observar esse fato, para mostrar que um teorema análogo deve ser mantido. para números complexos, p-adics, etc. Não há necessidade de refazer a prova.)

A única situação em que é necessária mais discussão é onde nem é óbvio o que significa relativizar seu teorema. (Por exemplo, qual é o mecanismo de acesso ao oráculo?) Como Kaveh apontou acima, não há operação matemática bem definida de "relativizar" um teorema da complexidade, assim como não há operação matemática bem definida de "complexificar" um teorema sobre números reais. Observe que, no último caso, não é suficiente substituir todas as ocorrências de R por C: você provavelmente também precisará substituir x 2 por | x | 2 (em alguns lugares, não em outros!) E faça outras alterações que são "óbvias" para um matemático, mas difíceis de listar formalmente. Da mesma forma, na teoria da complexidade, geralmente éóbvio o que significa "relativizar" um teorema (ou seja, quem deve ter acesso a A e o que significa para eles acessá-lo?), mas em alguns casos pode ser bastante sutil. Veja aqui para mais informações sobre esse problema.

Invertendo sua pergunta, pode-se perguntar:

Existe algum exemplo de um teorema da complexidade relativizante, para o qual é significativamente mais difícil provar que o teorema relativiza do que se o teorema é verdadeiro?

Curiosamente, eu não posso inventar um único exemplo indiscutível (embora talvez alguém possa)! Aqui está o melhor que posso fazer:

  1. Trabalhos recentes sobre computação quântica cega e autenticada (por Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani e outros) podem levar a exemplos. Nesses casos, a situação é que nós não sabemos se os teoremas relativizar ou não --- mas se eles fazem relativizar, então, certamente, uma ideia nova serão necessários para além do que é nas provas existentes.

  2. Indiscutivelmente, outro exemplo pode ser a auto-redutibilidade aleatória do #P. Se você perguntasse à maioria dos teóricos da complexidade por que isso era verdade, eles provavelmente diriam que é porque a permanente é # P-completa e auto-redutível aleatória. Isso é verdade, mas não responde à questão de saber se #P é rsr em relação a qualquer oráculo. Bem, acontece que #P é rsr em relação a qualquer oráculo, e nem é difícil provar isso - mas você precisa fornecer um argumento direto usando polinômios, em vez de apelar para propriedades da permanente.

  3. Na Seção 8 do meu artigo de algebrização e de Avi Wigderson , mostramos que o teorema GMW (que NP tem provas computacionais de zero conhecimento) é algebrizante. E que realmente se tomar novas idéias: não "dramaticamente" nova, mas certamente longe de ser encontrado nas provas habituais do teorema GMW. Obviamente, isso é para algebrização e não para relativização.

Adendo: em resposta a uma pergunta adicional do OP, não conheço nenhuma técnica para mostrar que, se você pudesse provar uma certa conjectura de complexidade (que ainda não o fez), sua prova seria necessariamente relativizada. Sim, desde que você restrinja sua "busca por uma prova" apenas a técnicas de relativização, você pode ter certeza de que, se conseguir encontrar uma prova, sua prova será necessariamente relativizada. E, na prática, é muitas vezes o que as pessoas fazem (por exemplo, porque elas têm certas idéias sobre como seria uma prova e essas idéias são relativizadas). Mas não sei como garantir, a priori , que, ampliando sua pesquisa para incluir técnicas não relativizantes, você não conseguiu encontrar uma prova que o tivesse escapado antes.

Scott Aaronson
fonte
Examinei a seção 8 do seu artigo e estou perplexo na parte inferior da página 40. Como o provador fornece provas de zero conhecimento para as partes (1) a (4)? Até "as cláusulas padrão são satisfeitas" envolve o oráculo para verificar a validade das anulações. Embora a recursão possa ser pretendida, está longe de ser claro para mim que a recursão seria capaz de alcançar um conjunto pequeno e suficiente de casos base.
(Agora, para uma questão tangente menor.) Você sabe se os resultados positivos deste artigo são ou não no modelo de bits ocultos (e uma versão modificada), como resumi no parágrafo de 6 linhas no meio desta resposta , algebrize ? Ao contrário do SAT, não vejo nenhuma maneira de relativizar ou algebrizar o ciclo de Ham direcionado.
Os comentários do @RickyDemer não são indexados pelos recursos de pesquisa e não são incentivados a longas discussões ou novas perguntas e respostas. Pode valer a pena criar uma pergunta separada (com um link para esta resposta) aqui ou no CS.SE com base nos seus comentários e, em seguida, Scott ou outros usuários podem resolvê-los em um assunto mais alinhado com a mecânica do site.
Artem Kaznatcheev