Explicar o problema de P = NP para 10 anos de idade

54

É 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.

Mohsin Hijazee
fonte
11
Minha inclinação é encerrar isso como não sendo ciência da computação teórica em nível de pesquisa .
Dave Clarke
11
@ Dave: Deve ser respondido por pesquisadores, então talvez seja adequado perguntar ao local para onde os pesquisadores pesquisam?
Jeremy
11
Eu acho que isso é razoável. Existe um artigo famoso chamado "Como explicar protocolos de conhecimento zero para seus filhos", que eu acho que seria considerado em nível de pesquisa. É verdade que pode ser difícil selecionar uma "melhor resposta", mas esse geralmente é o caso de perguntas simples. Além disso, essa pergunta pode acabar sendo uma boa publicidade para o site se surgirem respostas suficientemente interessantes ... muitas pessoas podem criar um link para a resposta dada aqui quando solicitadas uma explicação sobre P vs. NP.
Philip White
7
mas realmente deve ser CW.
Suresh Venkat 27/02
5
Eu perguntei a motivação porque o texto da pergunta me deu a impressão de que você não está muito interessado nas respostas para sua própria pergunta (parecia uma maneira de iniciar uma conversa em vez de uma pergunta real), não porque a pergunta é tola . De acordo com a sua resposta, você parece ter feito essa pergunta com o objetivo de fazer uma pergunta, e, portanto, não estou interessado em responder, porque isso não ajudará. Temos uma cultura diferente do Stack Overflow, mas isso não é relevante agora.
Tsuyoshi Ito 01/03

Respostas:

33

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:

Embalagem bin A embalagem do escaninho está NP completa 1 A embalagem do compartimento está NP completa 2

Geoffrey De Smet
fonte
Muito fácil de entender.
toto 28/02
4
Eu acho que "nenhuma maneira fácil" necessidade de ser expandida em incluindo escala como o número de blocos se torna maior
Ian Ringrose
3
Um exemplo muito bom, mas não é chamado de problema de embalagem retangular na literatura?
Mohammad Al-Turkistany
11
@ user54609 NP-complete não significa que podemos verificar se o empanque é ideal em tempo polinomial. NP-completo significa que podemos verificar se uma solução é viável em tempo polinomial (e não a encontramos consistentemente em tempo polinomial (a menos que P == NP)).
Geoffrey De Smet
11
Ah, então o problema da decisão é "existe uma solução viável". Eu vejo.
Ithisa
21

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.

ClassCheckFindExamplePEasyEasyMultiply numbersNPEasyHard8 queens

P é um conjunto de problemas nos quais o computador pode "encontrar" a solução facilmente.

NP é um conjunto de problemas para os quais o computador não pode "encontrar" a solução facilmente, mas pode "verificar" a solução facilmente.

Se podemos "verificar" uma solução tão facilmente, por que não podemos "encontrá-la" facilmente?

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

ClassCheckFindPEasyEasyNPEasyEasy
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 .PN PNPPNP

Pratik Deoghare
fonte
3
Talvez você possa resumir a essência da explicação de Scott.
Dave Clarke
2
Eu sempre fiquei curioso sobre o que é o alarido de P = NP, agora sim!
Lee Kowalkowski
Desde P ∈ NP, talvez esclareça que você está falando sobre a parte não-P do NP aqui.
David
+1 Muitas ótimas respostas neste tópico, mas esta é a única que tenta definir o que P e NP significam!
Mark E. Haase
"Se podemos" verificar "uma solução tão facilmente, por que não podemos" encontrá-la "facilmente? --- esta pergunta ainda não foi respondida! Caso contrário, é a melhor resposta para mim.
19

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.

Aaron Sterling
fonte
4
Um bom. Provavelmente não importa que o fatoração seja um exemplo ruim (ou é?).
Raphael
4
Factoring foi o exemplo que Mike Sipser usou em seu vídeo "explique P / NP ao público" para o Clay Mathematics Institute. I figura se é bom o suficiente para ele .....
Aaron Sterling
3
O problema da soma de subconjuntos pode ser explicado aos alunos que ainda não estudaram multiplicação!
Tegiri Nenashi
16

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:

Se você tem um quebra-cabeça de Sudoku que não foi finalizado e deseja finalizá-lo, isso pode ser realmente difícil de fazer. Por outro lado, se seu amigo terminar o problema e você for bom em aritmética, não é muito difícil verificar se a solução do seu amigo para o quebra-cabeça está correta.

A pergunta P = NP pergunta se existe ou não um processo passo a passo muito rápido para resolver um quebra-cabeça de Sudoku que ainda não foi concluído. O processo passo a passo deve ser tão claro e fácil de entender que até um computador pode entendê-lo e usá-lo para resolver quebra-cabeças do Sudoku de forma automática e muito rápida. Se houver um processo passo a passo tão rápido, seria o que os matemáticos chamam de "algoritmo de tempo polinomial" (explicarei o que isso significa quando você for mais velho).

De fato, cientistas da computação e programadores de computadores identificaram muitos outros quebra-cabeças e problemas muito importantes que são tão difíceis de resolver quanto o Sudoku. É realmente importante saber se esses problemas podem ser resolvidos, porque os computadores podem nos ajudar a fazer muitas coisas mais rapidamente, se puderem. Por exemplo, eles poderiam nos ajudar a programar trens com mais eficiência, quebrar códigos secretos e talvez até criar ajuda para construir computadores realmente inteligentes capazes de inteligência artificial.

Haveria muitas coisas muito boas que aconteceriam se as pessoas pudessem resolver P = NP. Obviamente, também haveria alguns problemas, porque seria mais difícil usar códigos secretos para manter as mensagens privadas em segredo.

A maioria dos matemáticos inteligentes pensa que P = NP não é verdade. Em outras palavras, a maioria das pessoas pensa que ninguém será capaz de resolver quebra-cabeças de Sudoku realmente difíceis rapidamente. No entanto, ninguém jamais conseguiu provar que P não era igual a NP antes, portanto, uma organização chamada Clay Mathematics Institute está oferecendo um prêmio de um milhão de dólares pela primeira prova de que P = NP é verdadeira ou pela primeira prova de que é falso.

Como você vê, eu peguei a parte "explique a uma criança de dez anos" um pouco literalmente. :)

Espero que isto ajude.

Philip White
fonte
Uma tentativa muito boa, embora eu não saiba se uma criança de 10 anos saberá o que é um quebra-cabeça sudoku.
28411 chazisop
2
@chazisop Por experiência, posso dizer que versões básicas de quebra-cabeças de sudoku (ou seja, em uma grade de 4x4) foram dadas para crianças nas séries 3 e 4 como exercícios, por isso não é uma suposição irracional.
Bob Fraser
Boa tomada, mas: 1) Solte P e NP da explicação. Eles não têm significado. 2) "muito rápido" cria exatamente a intuição errada. é, por intuição razoável, "muito rápido", mas polinomial. n1000
Raphael
11
@ Ohsin, de nada. @ Rafael, acho que não preciso largar P e NP; uma criança de dez anos pode simplesmente aceitar minha definição do problema sem precisar saber o que P e NP significam, e não sei como explicar o problema sem me referir a ele :). Além disso, eu disse que estava favorecendo a clareza à precisão total ... portanto, não acho injusto usar "muito rápido" e "tempo polinomial" de forma intercambiável.
Philip White
O que quero dizer é que esse uso de "rápido" não cria clareza. Supondo P = NP, talvez o problema "único" seja que estamos procurando algoritmos "rápidos" para problemas que não podem ser resolvidos "rapidamente", mas apenas polinomialmente com altos graus.
Raphael
8

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.

Jeremy
fonte
5

Michael Sipser explica o problema P vs NP de uma maneira altamente intuitiva neste vídeo .

Shitikanth
fonte
1

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.

Antonio Valério Miceli-Barone
fonte
Esta não é uma resposta para a pergunta.
31511 Dave
Por que não? A pergunta era "Como você explicaria o problema de P = NP a uma criança de 10 anos" e minha resposta é que provavelmente não existe uma explicação adequada que não deturpa o problema. Você pode discordar da minha resposta, é claro, mas por que afirma que ela não aborda a questão?
Antonio Valerio Miceli-Barone
3
Na minha opinião, esta é uma resposta possível, embora eu não concorde. É verdade que não podemos identificar P sem pensar em algo como o "conjunto de problemas que podem ser resolvidos com eficiência no mundo real". No entanto, não acho que isso exclua a possibilidade de explicar o problema de P =? NP para uma criança de dez anos de idade em um nível intuitivo. Por exemplo, crianças de dez anos ou mais aprendem a área de um círculo. Qualquer tratamento rigoroso da área requer muito cuidado, mas isso não descarta a possibilidade de ensinar o conceito de área em um nível intuitivo e útil.
Tsuyoshi Ito 28/02
Identificar a classe de complexidade com problemas viáveis ​​é uma simplificação / idealização semelhante à usada em outras ciências como a física, você pode dizer que mesmo a análise assintótica é enganosa, pois as constantes podem ser muito grandes e o algoritmo seria inviável para executar, esse pode ser o caso, mas esses conceitos são uma aproximação suficientemente boa para muitas tarefas e são úteis na prática. A questão está dando uma intuição sobre esses conceitos para não-especialistas, eu não tenho certeza se a primeira explicação introdutória do-los a uma necessidade não-especialista para ser completamente precisos ouP
Kaveh
11
[continuação] entre em detalhes e mencione as deficiências do modelo. É apenas um modelo matemático simplificado abstrato que tenta capturar alguns aspectos de uma noção intuitiva. Segundo os físicos atuais, a física newtoniana é fundamentalmente incorreta e não faz previsões corretas sobre a realidade em alguns domínios, mas funciona muito bem para a maioria das tarefas de engenharia. Qualquer modelo matemático abstrato de um conceito intuitivo / real é apenas um modelo, a tese de Cobham sobre a identificação de algoritmos de decisão viáveis ​​com não é diferente. P
Kaveh
1

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

vzn
fonte
0

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.

Mohsin Hijazee
fonte
Pode valer a pena apertar o texto. Você já tentou ler isso em voz alta?
András Salamon 02/03
Tudo não deve ser apertado como definições matemáticas, eu acho.
Mohsin Hijazee
Se você apertar demais o texto, o peole normal não terá "espaço" suficiente para entender um conceito antes de passar para o próximo conceito.
quer
n×n
Este link é talvez mais claro que o anterior: cstheory.stackexchange.com/questions/6563/…
Juan Bermejo Vega