A ciência da computação aparentemente percorre uma curva de progresso imparável. Poucas décadas nos levaram dos tubos de vácuo aos microchips, da conexão discada à Web de alta velocidade e ao Workplace Assistant Clippy para Bate-papoGPT. No entanto, milhares de problemas diários na ciência e na indústria permanecem tão insolúveis como sempre foram para a frota atual de supercomputadores alimentados por IA.
Esses problemas “NP-completos” notoriamente difíceis prometem um prêmio de um milhão de dólaresconcedido pela organização sem fins lucrativos Clay Arithmetic Institute, por encontrar sua solução rápida ou provar que não existe nenhuma. Uma visão surpreendente da década de 1970 torna este desafio ainda mais tentador: esses mais de mil problemas são, num sentido profundo, um e o mesmo. Se você resolver um, você resolverá todos eles. Este conceito, hoje elementary no campo da ciência da computação teórica, mostra que certos grupos de problemas computacionais formam uma teia unificada. Descubra um algoritmo rápido que resolve Quebra-cabeças de sudoku de qualquer tamanho, e agora você pode quebrar os esquemas de criptografia que protegem a nossa economia digital. Revele um atalho para agendar um passeio aéreo dentro do orçamento e você poderá usá-lo para resolver praticamente qualquer problema em aberto famoso. problema de matemática.
Encontrar algoritmos rápidos para esses problemas NP-completos (ou provar que tais algoritmos não existem) resolveria o “P versus NP”Pergunta, que é o mistério mais importante da ciência da computação. P refere-se ao conjunto de problemas computacionais que os computadores podem resolver com eficiência. NP, por sua vez, representa os problemas cujas soluções podem ser verificado eficientemente. Mas esses problemas não podem necessariamente ser resolvidos rapidamente. NP inclui tudo em P (porque encontrar uma solução é uma maneira perfeitamente boa de verificá-la), mas também problemas mais difíceis para os quais não conhecemos métodos eficientes de encontrar soluções. Só podemos verificá-los quando forem resolvidos. A questão P versus NP questiona se esta aparente assimetria entre encontrar uma solução e verificá-la é actual ou ilusória. Talvez P = NP e se refiram ao mesmo conjunto de problemas. Em outras palavras, talvez os problemas NP que não sabemos resolver de forma eficiente apenas aparecer difícil em relação aos problemas P porque ainda não encontramos os insights corretos.
Sobre apoiar o jornalismo científico
Se você está gostando deste artigo, considere apoiar nosso jornalismo premiado, assinando. Ao adquirir uma assinatura, você está ajudando a garantir o futuro de histórias impactantes sobre as descobertas e ideias que moldam nosso mundo hoje.
Por exemplo, existe um algoritmo (uma receita de instruções simples) que, dada uma grande lista de cidades, os voos que as ligam e um orçamento, decidiria de forma eficiente se é possível visitá-las todas respeitando o orçamento? Nós não sabemos. Nós conhecemos um ineficiente algoritmo: verifique todas as sequências possíveis de voos que visitam todas as cidades, some o custo de cada uma e examine os totais com o orçamento. Mas à medida que o número de cidades na lista cresce, o número de rotas a verificar explode exponencialmente, tornando-se rapidamente inviáveis mesmo para os computadores mais rápidos. Pode ou não haver algum atalho inteligente que contorne essa busca exaustiva, mas os cientistas da computação ainda não o encontraram. Dado um soluçãoContudo, neste caso, uma lista proposta de voos, seria possível verificar, num período de tempo razoável, se uma rota chega a todas as cidades e permanece abaixo do orçamento. Se P for igual a NP, isso implica que o cenário de voo (um exemplo do que é chamado de problema do caixeiro viajante) tem uma solução rápida. Nós simplesmente não sabemos ainda.
Muitos problemas computacionais naturais juntam-se ao problema do caixeiro viajante no conjunto NP. Isto inclui desafios de logística (como embalar caixas em caminhões), redes sociais (encontrar grupos de amigos em comum), biologia (prevendo como as proteínas se dobrarão) e jogos como Sudoku, Pokémon e Esmagamento de doces. Podemos até considerar a própria matemática um problema NP porque suas provas podem ser verificadas de forma eficiente. Pode parecer estranho classificá-los como problemas “difíceis” quando as pessoas colocam caixas em caminhões e resolvem Sudokus todos os dias. Mas consideramos que um algoritmo resolveu um problema de forma eficiente apenas se resolver todo exemplo de forma eficiente, incluindo os muito grandes. É claro que um computador pode resolver um Sudoku 9×9 mais rápido do que um milhão x milhão de Sudoku, portanto a definição rigorosa de “eficiente” apela à forma como o tempo necessário para resolver um problema aumenta com o tamanho da entrada.
A questão P versus NP diz respeito a uma variedade de problemas computacionais e como eles se relacionam entre si, por isso pode parecer que uma resolução exigiria a investigação de cada um desses problemas individualmente. Digamos que você descobrisse um algoritmo eficiente para o problema do caixeiro viajante. Isso seria um avanço heróico, mas diria algo sobre sua capacidade de resolver enormes Sudokus ou qualquer outro problema NP desafiador? Surpreendentemente, seu algoritmo para esse único problema resolveria totalmente P versus NP. Em 1972, o cientista da computação Richard Karp publicou um papel seminal demonstrando que 21 problemas NP clássicos têm uma propriedade notável: um algoritmo eficiente para resolver qualquer um deles poderia ser usado não apenas para resolver os outros 20, mas também para resolver todo problema em NP. Ele chamou esses 21 problemas de NP-completos. Nos anos seguintes, essa lista cresceu à medida que os pesquisadores descobriram que muitos outros problemas de NP compartilham essa propriedade mágica (incluindo o do caixeiro-viajante).
Podemos ver a completude do NP com otimismo ou pessimismo. Do lado optimista, uma fortaleza de problemas monstruosamente difíceis que se interpõe entre nós e promessas tecnológicas incalculáveis parece agora mais um castelo de cartas. Puxe alguém para o reino da viabilidade e todo o edifício do NP desmorona, e uma revolução científica surge dos escombros, repleta de viagens eficientes e sem esforço, rápidas descoberta de medicamentos através do dobramento de proteínas e uma nova period da matemática. Do lado pessimista, a NP-completude sugere que esses problemas não possuem algoritmos eficientes; se tudo o que é preciso para provar o contrário equivale a resolver um único problema, então por que ninguém ainda conseguiu? A maioria dos especialistas incline-se para a última interpretação e suspeitamos que problemas NP-completos não possuem algoritmos rápidos.
Quer seja visto como um copo meio cheio ou meio vazio, o conceito de problemas completos mudou a forma como os pesquisadores veem a computação. Karp mostrou que poderia usar um algoritmo para um problema NP-completo para resolver outro, primeiro demonstrando que é possível traduzir problemas aparentemente não relacionados para a linguagem um do outro usando um processo chamado redução. Isso funciona mostrando como pegar qualquer instância de um problema (como aquele que envolve uma lista de cidades, voos entre elas e um orçamento) e convertê-lo em outro problema (como um grande quebra-cabeça de Sudoku) de forma que o Sudoku só tenha solução válida se for possível visitar todas as cidades dentro do orçamento (e não tenha solução válida caso contrário). Dessa forma, se você descobrir um algoritmo eficiente para o Sudoku, poderá usá-lo também para resolver o problema do caixeiro viajante, convertendo instâncias deste último em quebra-cabeças de Sudoku. (Confira o last desta história para ver um exemplo interessante de redução em todos os detalhes.)
Essa capacidade de codificar um problema usando a linguagem de outro não é apenas uma peculiaridade deste exemplo, mas também uma característica da própria computação. Uma teia de reduções une todos os problemas NP-completos. Resolva qualquer um deles e você poderá resolver qualquer outro problema NP. As implicações confundem a mente. Lembre-se de que podemos enquadrar a prova de teoremas matemáticos como um problema NP-completo. Escolha qualquer questão matemática não resolvida famosa. A teoria da NP-completude então nos diz que existe algum nível de Esmagamento de doces isso codifica perfeitamente sua questão de matemática. Se uma determinada pontuação for alcançável em um determinado número de movimentos naquele nível do Sweet Crush, então seu problema de matemática terá uma prova de certa extensão; caso contrário, isso não acontece. A completude NP também nos garante que certos avanços no dobramento de proteínas (ou empacotamento de caixas ou resolução de Sudoku) destruiriam a economia digital. Isso ocorre porque a criptografia que protege nossos dados confidenciais funciona guardando-os atrás de problemas computacionais considerados intratáveis. (Vale a pena notar que, embora a solução de um problema NP-completo permita quebrar a criptografia, o inverso não é verdadeiro; os problemas intratáveis subjacentes à maioria dos esquemas de criptografia não são exatamente NP-completos.)
Com tudo isso baseado em problemas NP-completos, um milhão de dólares pode parecer uma pechincha pela solução deles. E pode oferecer um pouco de motivação adicional na próxima vez que você tiver dificuldade para agendar sua viagem de férias ou resolver um quebra-cabeça de Sudoku.
Como funciona a redução?
Para quem deseja se aprofundar em como funciona a redução, vamos reduzir outro tipo de problema NP-completo, o “problema do mapa de três cores”, ao “problema da clique”. O problema de três cores do mapa pergunta: Dado um mapa, você pode atribuir uma das três cores a cada região para que nenhuma região vizinha repita uma cor? O problema do clique pergunta: dada uma rede social, ela contém um grupo de um número desejado de pessoas que são todas amigas em comum? Ambos os problemas são NP-completos, o que significa que não conhecemos nenhum algoritmo eficiente para nenhum deles. Superficialmente, eles têm pouco em comum. Mas mostraremos que, dado um mapa, podemos transformá-lo numa rede social de tal forma que a resposta ao problema da rede social nos dará a resposta ao problema do mapa.
Think about um mapa dos EUA. Para construir uma rede social a partir disso, designaremos três “pessoas” para cada estado, uma para cada uma das três cores: azul, verde e vermelho. Faremos então duas pessoas amigas a menos que:
Eles representam o mesmo estado. (O representante verde de Wisconsin não será amigo do representante azul de Wisconsin.)
Eles têm a mesma cor e representam estados vizinhos. (Dakota do Norte e Dakota do Sul compartilham uma fronteira, então seus representantes vermelhos não serão amigos, mas Dakota do Norte e Flórida não, então seus representantes vermelhos serão amigos.)
Afirmo que esta rede social de 150 pessoas conterá um grupo de 50 amigos em comum apenas se o mapa dos EUA tiver três cores válidas. Se encontrarmos 50 amigos em comum na rede, todos eles deverão representar estados diferentes porque, por definição, não tornamos amigos quando representavam o mesmo estado. Além disso, a coloração que corresponde ao clique nunca atribuiria a mesma cor aos estados vizinhos – proibimos explicitamente tais ligações na rede. Portanto, um grupo de 50 pessoas corresponderia a uma tricolor válida. Da mesma forma, se não existirem 50 cliques na rede, então não existirão três cores para o mapa.
Nós apenas reduzido do problema das três cores do mapa ao problema da clique. Isso significa que se alguém descobrisse um algoritmo rápido para o problema da clique, poderia usá-lo para resolver qualquer instância do problema das três cores do mapa. Fundamentalmente, o primeiro passo – transformar o mapa numa rede – é rápido. Criar as pessoas na rede e as relações de amizade apropriadas não requer qualquer pesquisa exaustiva ou outra sobrecarga computacional inviável. As reduções mostram que mesmo que os nossos problemas pareçam únicos, podem ser mais universais do que parecem.
Este é um artigo de opinião e análise, e as opiniões expressas pelo autor ou autores não são necessariamente as de Científico Americano.
