Eu estou familiarizado com uma série de resultados que usam o teorema PCP (principalmente na aproximação de algoritmos), mas eu nunca me deparei com uma explicação clara do teorema PCP (ou seja, que ).NP=PCP(O(log(n)),O(1))NP=PCP(O(log⁡(n)),O(1))
Quais são os bons papéis / livros para ler para isso?
Ambos livro complexidade do Goldreich e de Arora e Barak livro complexidade tem capítulos dedicados a explicar a prova do teorema PCP (com fotos!).
Também vale a pena ler o artigo de Dinur , se você ainda não tentou abordá-lo. É pelo menos mais acessível (na minha opinião) do que a prova original, e você pode ter uma boa intuição de como a prova funciona deslizando apenas as primeiras 12 páginas (e se aprofundar nas provas técnicas contidas posteriormente no último pedaço do artigo) , se você preferir).
Na verdade, eu prefiro muito o artigo de Dinur à discussão em Arora / Barak.
Em 2008, Irit Dinur e eu ministramos um curso sobre PCP em Weizmann, incluindo as provas algébricas e combinatórias. Notas de aula escritas à mão estão disponíveis para a maioria das aulas: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html
Neste semestre, estou ministrando um curso PCP no MIT que contém o material do curso antigo, tratamento mais abrangente da repetição paralela e a conjectura de jogos únicos, além de resultados recentes (de 2008 a 2009), como baixa composição de erros e otimização de Programação Semidefinida para problemas de satisfação de restrições assumindo a Conjectura de Jogos Exclusivos. Também dedico tempo ao ensino de códigos de correção de erros, expansores, teoria da informação e análise de Fourier.
Este é o site do curso: http://stellar.mit.edu/S/course/6/fa10/6.895/
As notas estão disponíveis aqui: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html
Legal, essas são algumas notas excelentes. Estou realmente feliz por finalmente ver um autor anexado a "Uma História Ilustrada do Teorema do PCP". Eu já vi vários lugares antes, mas nunca com uma fonte citada!
O artigo de Dinur (linkado na resposta de Daniel Apon) está bem escrito e vale a pena ler. Também foi publicada uma discussão extensa sobre este artigo e a prova, que é útil ao ler o artigo em si: Jaikumar Radhakrishnan e Madhu Sudan, Sobre a Prova de Dinur do Teorema do PCP , Bull. Amer. Matemática. Soc. 44 (2007), 19-61 ( pré-impressão ).
Achei as anotações das aulas do curso Guruswami & O'Donnell (UW, 2005) muito úteis.
— Hung Q. Ngo
Para uma visualização de alto nível, gostei muito do post de Tim Gower de alguns dias atrás:
Realmente me ajudou a "obter" a conexão com os códigos de correção de erros e a falta de aproximação.
Houve um bom tutorial sobre o teorema do PCP e aplicações há um ano. Suas anotações de aula devem ser úteis: Limites de algoritmos de aproximação: PCPs e jogos exclusivos (Notas da palestra do tutorial DIMACS)
Para a prova original (e longa) do teorema do PCP, recomendo as anotações do Sudão como uma recapitulação e as anotações da aula de Feige, que explicam a prova em detalhes.
Veja também a publicação de Fortnow para outros materiais e discussões úteis.
Eu sugeriria examinar as notas da aula de Eli-Ben Sasson . Além disso, as notas de aula de Prahladh Harsha contêm e exposição de ambas as provas do Teorema do PCP. O link para o curso de Prahladh pode ser encontrado em sua página TIFR (U Chicago Fall 2007). As notas do curso de Venkat Guruswami e Ryan O'Donnell (como sugerido por Hung Q. Ngo) também são muito boas.
— Sarvagya Upadhyay
Existem 2 fontes que me parecem particularmente boas. Um, como alguém acima sugeriu, são as anotações de Venkat e Ryan.
A outra fonte útil são essas notas de aula de Luca Trevisan.
Atualmente, este curso está sendo oferecido na Georgia Tech por Prasad Raghvendra. Infelizmente a página ainda não está aberta.
Isso me leva a outra fonte de Subhash Khot. Pesquise no Google. Você deve conseguir encontrá-los.
(Pessoalmente, eu também não procurei as anotações de Khot, mas lembrei-me de que ele também ministrou este curso na GaTech)
para cientistas da computação novatos:
1- Provas e códigos verificáveis ​​probabilisticamente por Irit Dinur
2- Provas probabilisticamente verificáveis de Madhu Sudan
3- Capítulo 9 do livro de Goldreich: complexidade computacional, uma perspectiva conceitual
Para cientistas profissionais da computação:
1- O Teorema do PCP por Gap Amplification por Irit Dinur
2- Sobre a prova de Dinur do teorema do PCP, por jaikumar Radhakrishnan e Madhu Sudan
3- Capítulo 22 do livro Arora e barak: COMPLEXIDADE COMPUTACIONAL Uma Abordagem Moderna
4- PCPs robustos de proximidade e PCPs mais curtos de Prahladh Harsha (que abrange a primeira prova do theremem de PCP)
Para a prova "clássica" (ou seja, pré-Dinur) do teorema do PCP, achei a tese de Prahladh Harsha o melhor recurso.