Recentemente, tem circulado a notícia de que foi provado como P != NP. A notícia foi predominantemente recebida com indiferença ou confusão – com aquele sentimento de que você já ouviu falar disso e soa importante, mas não tem a menor ideia sobre o que se trata. Se esta foi sua reação, este post é para você.
P, NP e baldes de LEGO
Um problema P é um que conseguimos resolver em tempo razoável. Ou seja, é um para o qual um algoritmo capaz de gerar soluções é conhecido, e tal algoritmo executa em tempo polinomial.
Já um problema NP é um onde podemos rapidamente validar se uma solução é correta; porém não conseguimos gerar soluções de forma tão rápida. Considere, por exemplo, a tarefa de construir um avião usando blocos de LEGO.
Acho que podemos concordar que, dado um objeto qualquer, é trivial checar se ele é ou não o avião de LEGO que esperamos. Em outras palavras, o algoritmo para validar soluções deste problema é conhecido, e executa em tempo polinomial.
Entretanto, dado um amontoado de peças de LEGO, não é fácil conseguir montar este avião, mesmo tendo em mãos a foto do resultado esperado. Ou seja, apesar da trivialidade em validar soluções, não é conhecido um algoritmo capaz de resolver este problema em tempo polinomial.
Esta é a natureza de um problema NP e, quando paramos para pensar, conseguimos observar esta dualidade de verificação fácil mas solução não-trivial em muitas situações:
passei dias adiando a publicação deste artigo enquanto pensava em exemplos bobos para esta parte, e no final ficou ruim assim mesmo.
| é trivial verificar se… |
mas não é trivial… |
| uma pessoa próxima está irritada com você |
entender a irritação ou não irritar pessoas próximas |
| um projeto foi bem sucedido |
criar projetos bem sucedidos |
| alguém gostou do presente que deu |
escolher presentes |
| a Apple ganha muito dinheiro |
montar uma empresa que ganhe tanto quanto a Apple |
| a solução de um problema de cálculo está correta |
montar a solução passo a passo |
| uma lista de itens está ordenada |
ordenar uma lista de itens |
| seu programa está produzindo um erro |
identificar e resolver erros |
| seu foguete espacial não explodiu |
criar foguetes que não explodam |
Agora que entendemos melhor P e NP, o questionamento é o seguinte: de fato existem problemas para os quais encontrar soluções sempre será mais trabalhoso que validá-las (P != NP) ou para todo problema onde validar soluções é trivial, também é trivial encontrar soluções (P == NP) e a gente só é idiota mesmo por não conseguir?
Se P != NP
Nos já acreditamos que P != NP apesar de não termos uma prova formal sobre; simplesmente pois é o que observamos intuitivamente na realidade. Além disso, muita gente tem escrito algoritmos no último século e tentando abordar vários dos milhares problemas NP, então os conhecemos relativamente bem – o sentimento geral é que se P == NP, a gente já teria descoberto um tempo atrás.
Uma prova de que P != NP não causaria nenhuma grande revolução, mas ainda seria um grande progresso ter esta questão oficialmente fechada e nossas opiniões e crenças vigentes validadas. possivelmente esta “viralizou” pelo quão vagamente atraente mas inverificável a notícia soa para “nerds”, não pelos méritos da prova.
regra geral: se uma notícia soa clickbaity, possivelmente realmente é e não espere que o autor passou um minuto sequer checando se ela fazia ou não sentido.
Aliás, este é um bom momento para dizer que a prova que recentemente circulou por aí é falha. Isto é uma questão bastante técnica e eu nunca serei capaz de explicar ou sequer entender perfeitamente a situação, mas o consenso geral da comunidade sobre claramente indica que não há meritos na prova.
Se P == NP
Agora, uma prova de que P == NP mudaria completamente nossa percepção da realidade, e seria a descoberta mais chocante e transformadora dos últimos tempos. Afinal, ela provaria que uma grande quantidade de problemas complexos (tanto do nosso dia-a-dia quanto científicos) na verdade são muito simples.
Acho que este seria o maior “facepalm” da história, pois ilustraria que este tempo todos estivemos olhando estes problemas sob uma perspectiva fundamentalmente errônea. Seria aquele tipo de descoberta frustrante pois, apesar de expandir seus horizontes, abalaria completamente suas crenças e ilustraria o quão tolo e ignorante você é.
Esta prova possivelmente resolveria alguns problemas NP imediatamente; e para os demais, ela nos daria a certeza de que existem soluções eficientes possíveis. Creio que isso causaria uma espécie de nova Revolução Indutrial; com uma grande quantidade de descobertas científicas rapidamente se tornando novos produtos e serviços e estes trazendo consideráveis mudanças em nossas vidas. Especificamente, os impactos em medicina, engenharia de materiais e inteligência artificial seriam imensos.
Então na próxima vez que ver uma notícia sobre P != NP, não precisa se animar muito – isso não é novidade.
afirmar que a existência de baterias decentes depende de P == NP me deixa muito triste, mas claramente é nossa última esperança.
Agora, se a notícia falar que P == NP, é quase certo que todo mundo envolvido está terrivelmente enganado… ou não. Se for verdade mesmo, finalmente teremos os carros voadores, hologramas, milagres médicos e baterias de smartphone que duram mais de um dia que nos foram prometidos.