Recursos para aprender sobre o problema P vs. NP

Recentemente, fui lembrado sobre o problema vs. N P, conforme explicado por Stephen A. Cook no Clay Mathematics Institute.$\mathsf{P}$$\mathsf{NP}$

Isso despertou meu interesse e eu gostaria de aprender mais sobre isso. O primeiro passo seria obter uma compreensão mais profunda do problema e uma compreensão da área em geral.

Você pode recomendar livros ou outros recursos em que eu possa aprender mais sobre o problema?

É bom ver um colega de graduação perseguindo esse grande problema, com tanto entusiasmo. Permita-me lhe oferecer um conselho de minhas próprias experiências.

é um problema muito interessante. As implicações da resposta são imensas, especialmente no caso de as duas classes serem iguais. A recompensa é grande em muitos níveis, do científico altruísta ao prêmio em dinheiro materialista. Isso leva muitos jovens que encontram o problema na tentativa de resolvê-lo, com pouco ou nenhum conhecimento sobre o assunto.$P \neq NP$

Talvez a maioria dos estudantes de teoria passe por essa fase. Você terá uma idéia e pensará que está certo, mas é quase certo que você está errado. Algumas pessoas nunca passam por essa fase e se envergonham por serem muito teimosas para admitir seus erros.

No FOCS 2010, Rahul Santhanam comparou a pergunta a um monstro mítico. Seria necessário muitos sacrifícios e coragem para tentar derrotar esse monstro. Afinal, pode ser o problema mais difícil de todos os tempos. Para ter uma chance de lutar, você terá que estudar muito sobre esse problema e a complexidade em geral. Você nunca saberá qual será a "fraqueza do monstro".$P \neq NP$

Portanto, meu conselho é o seguinte: não se apresse em conhecer o problema. Toda vez que você descobrir uma solução, assuma que você está errado de alguma forma e tente encontrar o problema com ela. Dessa forma, você aprenderá muito.

Quanto às referências, eu recomendaria o livro de Sipser também. Depois de terminar, eu recomendaria "Complexidade Computacional: Uma Abordagem Moderna", de Arora e Barak, um livro mais voltado para a complexidade, que requer uma boa compreensão do conceito de computação.

Eu sugiro fortemente "Introdução à Teoria da Computação", de Sipser, particularmente porque cobre pelo menos uma das principais barreiras para resolver P vs. NP, a relativização. Ele contém uma prova muito clara do resultado da Baker-Gill-Solovay. Não tenho certeza se ele contém alguma coisa sobre os resultados de Razborov-Rudich, mas é um recurso introdutório fantástico, muito claro e fácil de ler para aprender não apenas sobre P vs. NP, mas também para muitos outros tópicos relacionados na teoria da complexidade. ..que é significativo porque, se seu interesse é tentar resolver o problema, você deve ter alguma experiência no campo e idéias para começar.

Provavelmente a melhor coleção de links em um só lugar é a seção Leitura adicional do wiki que foi colocado em conjunto para ajudar a avaliar a prova reivindicou do Deolalikar que .$P \neq NP$

Boa sorte. O problema parece ser difícil. :-)

$P$$NP$

A referência clássica para a completude do NP é o livro de Garey e Johnson (http://tinyurl.com/2w5yofs). É instrutivo e completo.

Pessoalmente, aprendi com Kleinberg Tardos (http://tinyurl.com/37dtyyl), porque minha universidade o usou.

Eu também sugeriria tomar uma instância do problema e tentar resolvê-la. É uma boa prática experimentar problemas em aberto. Por experimento, quero dizer, você pode escrever programas ou implementar algoritmos conhecidos por outros e entender como eles funcionam, onde eles falham, etc. Além disso, você pode descobrir várias técnicas de prova. Lembre-se, eles não o prenderão se você estudar e trabalhar muito nisso e não conseguir encontrar nenhuma solução. Pelo contrário, seu nível de competência é garantido para aumentar.

Na maioria dos casos, esses problemas em geral são difíceis de resolver do que suas instâncias específicas . Leia sobre a NFL para ter uma idéia.

No meu caso, logo fui enterrado sob um conjunto de idéias e conceitos relacionados. Existem ajustes de programação / codificação e manobras teóricas. Por exemplo, se você deseja resolver qualquer instância de problema usando conceitos de algoritmo genético, em breve descobrirá que o GA sozinho é um mundo vasto para descobrir! Recentemente, conheci o Linkage Learning no GA / EA. Não sei muito sobre isso embora.

Além disso, ao tentar codificar as coisas, você encontrará algumas ferramentas / linguagens de programação melhores / mais fáceis do que outras. Eu estava perdido na discussão de por que Alex Stepenov acha que OOP é matematicamente incorreto e qual é a vantagem da programação funcional. Não tenho a trilha, mas lembro-me claramente que, no início, estudava um problema NP-Complete / Hard.

Sejam bem-vindos, pois a jornada é aventureira!

P, NP e NP-Completeness: The Basics of Complexity Theory, de Oded Goldreich, seria outro bom livro introdutório.

Após o conteúdo introdutório, eu também gostaria de recomendar The P = NP Question e Gödel's Lost Letter, de Richard J. Lipton.

Eu recomendo o excelente artigo de revisão de Lance Fortnow, "O status do problema P versus NP" , que discute algumas novas abordagens para o problema.

$P=?NP$$\mathcal{P}$$\mathcal{NP}$

Lance Fortnow recentemente expandiu e publicou sua coluna já abrangente do CACM (mencionada na outra resposta da MA) em um livro completo de nível de ciência popular, The Golden Ticket: P, NP, e the Search for the Impossible . foi revisado no New Yorker, "Um problema de matemática mais profundo" , de Nazaryan. ( página dos editores , Princeton University Press)