É a minha primeira pergunta neste site. Estou fazendo um curso de mestrado em teoria da computação. Como você explicaria o problema de P = NP a uma criança de 10 anos e por que ela tem uma recompensa tão monetária?
Sua opinião?
Vou atualizar a pergunta quando minha cabeça ficar clara.
cc.complexity-theory
soft-question
teaching
p-vs-np
Mohsin Hijazee
fonte
fonte
Respostas:
Eu uso esses três slides para mostrar por que é tão difícil (impossível?) Criar um algoritmo rápido para um problema de NP:
fonte
Nesta palestra, Scott Aaronson aborda a questão.
TEDxCaltech - Scott Aaronson - Física no século XXI: labutando na sombra de Feynman
Aviso: Por favor, NÃO mostre essa conversa diretamente para sua avó / 10 anos de idade. porque? assista e você saberá. ;-)
EDIT:
Dê ao garoto 8 rainhas para resolver. Também lhe dê um prazo.
Se ele "encontrar" uma solução, então ele é um garoto inteligente, você pode começar a ensinar-lhe CS imediatamente. :)
Caso contrário, você mostra a solução e pede que ele "verifique" se está correto.
O que você faz no CS é resolver o problema ou provar que ninguém pode.
Se alguém inventar um algoritmo que facilita "encontrar" soluções para problemas de NP, a tabela terá a aparência e . P=NP
E se alguém provar que ninguém pode encontrar um algoritmo para "encontrar" soluções para problemas de , a tabela permanece a mesma e .P ≠ N PNP P≠NP
fonte
Uma das principais coisas pelas quais as pessoas usam computadores é a pesquisa. Programas como o Google são chamados de "mecanismos de pesquisa" e são usados milhões de vezes por dia. Um computador recentemente venceu os humanos no Jeopardy porque conseguiu pesquisar toneladas de dados, super rápido.
Mas algumas coisas são difíceis para os computadores procurarem. Soa estranho, não é? Um exemplo é a multiplicação reversa. Claro que se eu disser "O que é 5 vezes 3?" você pode dizer "15" em nanossegundo, uau! Mas qual é a resposta para "Quais dois números mutilados juntos são 21?" (Aguarde a resposta, 7 x 3.) Certo! Agora, quais dois números multiplicados juntos são 23? (Aguarde a resposta ou frustração.)
Os únicos dois números multiplicados juntos que equivalem a 23 são 1 e 23 em si. Isso levou algum pensamento, não foi? E 23 é um número pequeno. Pense se o número tivesse centenas de dígitos. E o melhor é que os melhores programas do mundo não podem reverter a multiplicação muito melhor do que uma criança de 7 anos de idade pode tentar, apenas testando um número e depois o próximo e depois o próximo. Os computadores podem fazê-lo mais rapidamente , mas não sabemos realmente como instruir um computador para fazê-lo de maneira mais inteligente . As pessoas fazem doutorado nessas coisas e só sabem dizer aos computadores para fazer a multiplicação reversa um pouco mais inteligente.
Então, talvez não haja uma maneira mais inteligente. Mas talvez exista, e ainda não o encontramos. Esse é o problema de P / NP em poucas palavras: se eu reconheço uma resposta imediatamente - 1 vezes 23 é 23, duh - isso me ajuda a procurar a resposta mais rapidamente? As pessoas pensam que é tão importante que quem descobre a resposta, sim ou não, ganhe um milhão de dólares.
fonte
Eu acho que o problema P vs. NP poderia ser explicado muito gentilmente em termos de Sudoku. Estou assumindo que o garoto de dez anos em questão esteja familiarizado com o Sudoku. Vou tentar favorecer a simplicidade ao invés do rigor na minha explicação.
Aqui está minha tentativa de explicar P = NP a uma hipotética criança de dez anos:
Como você vê, eu peguei a parte "explique a uma criança de dez anos" um pouco literalmente. :)
Espero que isto ajude.
fonte
Aqui está como eu expliquei isso para minha mãe, espero que seja útil :)
Existem problemas para os quais é fácil encontrar uma solução (P, mas menos os chamam de "facilmente solucionáveis"), problemas para os quais é fácil verificar se uma determinada solução está correta (NP, mas vamos chamá-los de "facilmente verificáveis" ) e problemas que não são facilmente solucionáveis nem facilmente verificáveis. Para simplificar, suponha que "Fácil" seja formalmente definido e que cada problema tenha uma solução única.
Agora, as pessoas conseguiram provar (usando a matemática) relações interessantes entre essas duas noções de "facilmente solucionável" e "facilmente verificável", de modo que alguns problemas não são facilmente solucionáveis e outros não são facilmente verificáveis. Um exemplo básico desse resultado é que um problema facilmente solucionável também é facilmente verificável: basta encontrar sua solução e compará-la com a solução fornecida.
De maneira tentadora, para muitos problemas práticos (como decidir se há uma possível atribuição de alunos a professores e salas de aula, quando há muito pouca margem), não se sabe se existe uma maneira "fácil" de resolvê-lo, mas sabe-se como verificar facilmente se uma solução está correta ou não. As pessoas tentaram muito e falharam, depois tentaram provar que não era possível e falharam também: elas simplesmente não sabem. Alguns pensam que todos os problemas facilmente verificáveis são facilmente solucionáveis (devemos apenas pensar mais sobre isso), outros pensam o contrário, que não devemos perder nosso tempo tentando encontrar soluções fáceis para esses problemas.
O que descobrimos é como mostrar links entre problemas (por exemplo, se você sabe ir à escola, sabe como ir à padaria que fica logo à frente) e problemas facilmente verificáveis que estão vinculados a todos os outros problemas facilmente verificáveis ( NP-completo, mas vamos chamá-los de "problemas-chave"), de modo que, se alguém, um dia, mostrar que um dos principais problemas é facilmente resolvido, todos os problemas facilmente verificáveis também são facilmente solucionáveis (por exemplo, P = NP). Por outro lado, se alguém mostrar que um dos principais problemas não pode ser facilmente solucionável, nenhum dos outros pode ser facilmente solucionável (por exemplo, P <> NP).
Portanto, a questão é tentadora e relativamente importante na prática (embora alguns argumentem que deveríamos nos concentrar em definições alternativas de "fácil"), e as pessoas estão investindo bastante dinheiro e tempo no debate.
fonte
Michael Sipser explica o problema P vs NP de uma maneira altamente intuitiva neste vídeo .
fonte
Sou um pouco cético em relação à possibilidade de explicar esse problema aos 10 anos de idade, ou mesmo a um leigo, sem incorrer em deturpação dos conceitos-chave.
Todas as explicações formuladas em termos de "facilidade" versus "dureza" de encontrar e verificar soluções assumem a tese de Cobham, que é discutivelmente falsa no caso geral, e pode ser considerada pouco mais que uma regra de ouro.
fonte
estratégias vencedoras para vários jogos clássicos de tabuleiro, por exemplo, encouraçado ou (mais recentemente) videogame, foram comprovadas NP completas e esta é uma excelente maneira / ângulo de apresentar / descrever algumas das teorias fundamentais para iniciantes.
encouraçado como um problema de decisão completo do NP Merlijn Sevenster ICGA journal set 2004
O caça-minas é um FAQ completo de NP do matemático RW Kaye. Edição de primavera de 2000 do Mathematical Intelligencer (volume 22, número 2, páginas 9--15)
Jogar é um trabalho árduo, mas alguém precisa fazê-lo! artigo arxiv de Giovanni Viglietta. analisa a complexidade computacional de Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3 e Starcraft.
Pacman é difícil artigo de extrema tecnologia mag sobre papel acima
fonte
E aqui está minha opinião sobre o problema.
Kido!
Você sabe que enfrentamos muitos problemas em nossa vida. Você pode dizer desafios. Alguns são difíceis, outros são mais fáceis. Por exemplo, você geralmente precisa adicionar dois números. E ontem à noite, estávamos no tabuleiro de xadrez e tivemos que vencer o nosso vizinho. Bem, adicionar dois números é um problema simples e direto, com etapas limitadas envolvidas. Tais problemas são chamados de problemas da classe P, porque existem muitos problemas bastante simples, com etapas discretas que devem ser repetidas várias vezes para obter uma solução.
Por outro lado, ontem à noite no nosso jogo no peito, qual seria a melhor estratégia para vencer o jogo? Poderíamos mover o primeiro peão um passo, ou o segundo peão um passo, ou podemos mover o segundo peão dois passos e o primeiro peão um passo, para que você veja muitas e muitas possibilidades. Mas existe uma maneira para nós ou para um destinatário que nos fornece conjuntos completos de movimentos ordenados que produzem o melhor e para um xeque-mate? Então você vê que é muito difícil, porque existem muitas possibilidades, uma a cada passo. Bilhões e bilhões, como diz Carl Sagan.
Mas querida, e se eu lhe contar todas as posições do conselho e perguntar se é um xeque-mate? Certamente você será capaz de dizer rapidamente, em poucos exames, se ainda restam movimentos legais para o rei.
Portanto, esses problemas são difíceis de resolver, mas se sua solução é facilmente verificável em poucos passos simples, eles são chamados de problemas de NP.
Agora você pergunta o que P = NP significa? Na verdade, essa pergunta significa que existe uma maneira de encontrar uma solução mais simples para encontrar a melhor estratégia ou lista ordenada de movimentos para um jogo de xadrez sem passar por todos os bilhões de possibilidades, como fazemos para uma adição simples? Este quesiton simples ainda não foi respondido. Não temos nenhuma prova da sua verdade ou rejeição, mas, se o fizermos, será um avanço. Se isso for verdade, nossa civilização poderá resolver problemas muito complexos, transformando-os em problemas de classe P. As pessoas poderão quebrar senhas em segundos, as mensagens serão descriptografadas e muito mais e é por isso que esse problema é considerado um dos problemas mais importantes do milênio.
fonte