Teorema PCP - PCP theorem

Não deve ser confundido com o problema de correspondência do Post .

Na teoria da complexidade computacional , o teorema PCP (também conhecido como teorema de caracterização PCP ) afirma que todo problema de decisão na classe de complexidade NP tem provas verificáveis ​​probabilisticamente ( provas que podem ser verificadas por um algoritmo aleatório ) de complexidade de consulta constante e complexidade de aleatoriedade logarítmica (usa um número logarítmico de bits aleatórios).

O teorema PCP diz que para alguma constante universal K , para cada n , qualquer prova matemática de comprimento n pode ser reescrita como uma prova diferente de comprimento poly ( n ) que é formalmente verificável com 99% de precisão por um algoritmo aleatório que inspeciona apenas K cartas dessa prova.

O teorema PCP é a pedra angular da teoria da dureza computacional de aproximação , que investiga a dificuldade inerente em projetar algoritmos de aproximação eficientes para vários problemas de otimização . Foi descrito por Ingo Wegener como "o resultado mais importante na teoria da complexidade desde o teorema de Cook " e por Oded Goldreich como "o culminar de uma sequência de obras impressionantes [...] ricas em ideias inovadoras".

Declaração formal

O teorema PCP afirma que

NP = PCP [O (log n ), O (1)].

PCP e dureza de aproximação

Uma formulação alternativa do teorema PCP afirma que a fração máxima de restrições satisfatórias de um problema de satisfação de restrição é NP-difícil de aproximar dentro de algum fator constante.

Formalmente, para algumas constantes K e α <1, o seguinte problema de promessa ( L sim , L não ) é um problema de decisão NP-difícil:

  • L sim = {Φ: todas as restrições em Φ são simultaneamente satisfatórias}
  • L no = {Φ: cada atribuição satisfaz menos do que uma fração α das restrições de Φ},

onde Φ é um problema de satisfação de restrição sobre o alfabeto booleano com no máximo K variáveis ​​por restrição.

Como consequência desse teorema, pode-se mostrar que as soluções para muitos problemas de otimização natural, incluindo a máxima satisfatibilidade da fórmula booleana , o conjunto máximo independente em gráficos e o problema do vetor mais curto para reticulados não podem ser aproximadas de forma eficiente, a menos que P = NP . Esses resultados às vezes também são chamados de teoremas PCP porque podem ser vistos como provas verificáveis ​​probabilisticamente para NP com alguma estrutura adicional.

Prova

Uma prova de um resultado mais fraco, NP = PCP [n 3 , 1] é dada em uma das aulas de Dexter Kozen.

História

O teorema PCP é o culminar de uma longa linha de trabalho em provas interativas e provas verificáveis ​​probabilisticamente. O primeiro teorema relacionando provas padrão e provas verificáveis ​​probabilisticamente é a afirmação de que NEXP ⊆ PCP [poli ( n ), poli ( n )], provado por Babai, Fortnow & Lund (1990) .

Etimologia do nome "teorema PCP"

A notação PCP c ( n ),  s ( n ) [ r ( n ),  q ( n )] é explicada em Prova verificável probabilisticamente . A notação é de uma função que retorna uma certa classe de complexidade. Veja a explicação mencionada acima.

O nome deste teorema (o "teorema PCP") provavelmente vem de "PCP", que significa " prova verificável probabilisticamente ", ou da notação mencionada acima (ou ambos).

História após o primeiro teorema [em 1990]

Posteriormente, os métodos usados ​​neste trabalho foram estendidos por Babai, Lance Fortnow , Levin e Szegedy em 1991 ( Babai et al. 1991 ), Feige, Goldwasser, Lund, Safra e Szegedy (1991) e Arora e Safra em 1992 ( Arora & Safra 1992 ) para produzir uma prova do teorema PCP por Arora, Lund, Motwani, Sudan e Szegedy em 1998 ( Arora et al. 1998 ).

O Prêmio Gödel de 2001 foi concedido a Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Carsten Lund , László Lovász , Rajeev Motwani , Shmuel Safra , Madhu Sudan e Mario Szegedy pelo trabalho no teorema PCP e sua conexão com a dureza da aproximação.

Em 2005, Irit Dinur descobriu uma prova significativamente mais simples do teorema PCP, usando gráficos de expansão . Ela recebeu o Prêmio Gödel 2019 por isso.

Análogo quântico do teorema PCP

Em 2012, Thomas Vidick e Tsuyoshi Ito publicaram um resultado que mostrou uma "forte limitação na capacidade de provadores emaranhados de conspirar em um jogo multiplayer." Isso poderia ser um passo para provar o análogo quântico do teorema PCP, já que quando o resultado foi divulgado na mídia, a professora Dorit Aharonov o chamou de "o análogo quântico de um artigo anterior sobre provas interativas multiprover" que "basicamente levou ao PCP teorema".

Em 2018, Thomas Vidick e Anand Natarajan provaram uma variante de jogos do teorema quântico PCP sob redução aleatória. Afirma que QMA ⊆ MIP * [log ( n ), 1,1 / 2], onde MIP * [f (n), c, s] é uma classe de complexidade de sistemas de provas interativas quânticas multi-provador com f ( n ) -bit comunicações clássicas, e a completude é ce a solidez é s. Eles também mostraram que a versão hamiltoniana de uma conjectura quântica PCP, ou seja, um problema hamiltoniano local com lacuna de promessa constante c  -  s é QMA -hard, implica o teorema quântico PCP dos jogos.

Notas

Referências