Explicado: P vs. NP

O problema mais notório da Ciência da Computação Teórica permanece em aberto, mas as tentativas de resolvê-lo levaram a profundas percepções.

Os jornalistas de ciência e tecnologia se orgulham da capacidade de explicar ideias complicadas de maneiras acessíveis, mas existem alguns princípios técnicos que encontramos com tanta frequência em nossos relatórios que parafraseando-os ou escrevendo em torno deles começam a sentir falta de uma grande parte da história. Assim, em uma nova série de artigos chamada "Explained", a equipe do MIT News Office irá explicar algumas das ideias centrais nas áreas que eles cobrem, como pontos de referência para futuros relatórios sobre a pesquisa do MIT.

No episódio de Halloween de Os Simpsons de 1995, Homer Simpson encontra um portal para a misteriosa Terceira Dimensão, atrás de uma estante de livros, e desesperado para escapar de suas cunhadas, ele mergulha. Ele se encontra vagando por uma superfície escura gravada com linhas de grade verdes e repleta de formas geométricas, acima das quais pairam equações estranhas. Uma delas é a afirmação ilusoriamente simples de que P = NP.

De fato, em uma pesquisa de 2002, 61 matemáticos e cientistas da computação disseram que pensavam que P provavelmente não era igual a NP, a apenas nove que pensavam que sim —e desses nove, vários disseram ao pesquisador que eles tomaram a posição apenas para ser contrário. Mas até agora, ninguém foi capaz de responder de forma decisiva à questão de uma forma ou de outra. Frequentemente chamada de questão pendente mais importante na Ciência da Computação Teórica, a equivalência de P e NP é um dos sete problemas que o Clay Mathematics Institute lhe dará um milhão de dólares para provar —ou refutar. Grosso modo, P é um conjunto de problemas relativamente fáceis, e NP é um conjunto que inclui o que parecem ser problemas muito, muito difíceis, então P = NP implicaria que os problemas aparentemente difíceis realmente têm soluções relativamente fáceis. Mas os detalhes são mais complicados.

A ciência da computação está amplamente preocupada com uma única questão: quanto tempo leva para executar um determinado algoritmo? Mas os cientistas da computação não dão a resposta em minutos ou milissegundos; eles dão em relação ao número de elementos que o algoritmo tem que manipular.

Imagine, por exemplo, que você tenha uma lista não ordenada de números e queira escrever um algoritmo para encontrar o maior deles. O algoritmo precisa analisar todos os números da lista: não há como evitar isso. Mas se simplesmente mantiver um registro do maior número que já foi visto até o momento, ele terá que analisar cada entrada apenas uma vez. O tempo de execução do algoritmo é, portanto, diretamente proporcional ao número de elementos que está manipulando —o que cientistas da computação designam N. Naturalmente, a maioria dos algoritmos é mais complicada e, portanto, menos eficiente do que a de encontrar o maior número em uma lista; mas muitos algoritmos comuns têm tempos de execução proporcionais a N², ou N vezes o logaritmo de N, ou algo parecido. 

Uma expressão matemática que envolve N's, N²s e N's elevados a outras potências é chamada de polinômio, e é isso que o "P" em "P = NP" representa. P é o conjunto de problemas cujos tempos de solução são proporcionais a polinômios envolvendo N's. 
Obviamente, um algoritmo cujo tempo de execução é proporcional a N³ é mais lento do que aquele cujo tempo de execução é proporcional a N. Mas essas diferenças diminuem para a insignificância em comparação com outra distinção, entre expressões polinomiais —onde N é o número aumentado para uma potência— e expressões onde um número é elevado à enésima potência, digamos, 2^N.

Se um algoritmo cujo tempo de execução é proporcional a N levar um segundo para realizar um cálculo envolvendo 100 elementos, um algoritmo cujo tempo de execução seja proporcional a N³ leva quase três horas. Mas um algoritmo cujo tempo de execução é proporcional a 2^N leva 300 quintilhões de anos. E essa discrepância fica muito, muito pior quanto maior o N cresce. 
NP (que significa tempo polinomial não determinístico) é o conjunto de problemas cujas soluções podem ser verificadas em tempo polinomial. Mas, tanto quanto qualquer um pode dizer, muitos desses problemas levam tempo exponencial para serem resolvidos. Talvez o mais famoso problema de tempo exponencial em NP, por exemplo, seja encontrar fatores primos de um grande número. Verificar uma solução requer apenas multiplicação, mas a solução do problema parece exigir sistematicamente a experimentação de muitos candidatos. 
Então a pergunta “P igual a NP?” Significa “Se a solução de um problema pode ser verificada em tempo polinomial, pode ser encontrada em tempo polinomial?” Parte do fascínio da questão é que a grande maioria dos problemas de NP cujas soluções parecem exigir tempo exponencial é o que se chama NP-completo, o que significa que uma solução de tempo polinomial para uma pode ser adaptada para resolver todas as outras. E na vida real, problemas NP-completos são bastante comuns, especialmente em grandes tarefas de agendamento. O mais famoso problema NP-completo, por exemplo, é o chamado problema do vendedor ambulante: dadas as N cidades e as distâncias entre elas, você pode encontrar uma rota que atinja todas elas, mas é menor do que ... qualquer limite que você escolha conjunto? 
Dado que P provavelmente não é igual a NP, no entanto —que soluções eficientes para problemas de NP provavelmente nunca serão encontradas— o que é todo esse alarido? Michael Sipser, chefe do Departamento de Matemática do MIT e membro do Grupo de Teoria de Computação (TOC) do Laboratório de Ciência da Computação e Inteligência Artificial, diz que o problema P-versus-NP é importante para aprofundar nossa compreensão da complexidade computacional. 
“Uma grande aplicação está na área de criptografia”, diz Sipser, onde a segurança dos códigos criptográficos é frequentemente assegurada pela complexidade de uma tarefa computacional. O esquema criptográfico da RSA, que é comumente usado para transações seguras na Internet —e foi inventado no MIT— "é realmente uma consequência do estudo da complexidade de se fazer certas computações teóricas de números", diz Sipser. 
 Da mesma forma, diz Sipser, “a empolgação em torno da computação quântica realmente transbordou quando Peter Shor” —outro membro do TOC— “descobriu um método para fatorar números em um computador quântico. A descoberta de Peter inspirou uma enorme quantidade de pesquisas tanto na comunidade de Ciência da Computação quanto na Física. ”De fato, por um tempo, a descoberta de Shor despertou a esperança de que os computadores quânticos, que exploram as propriedades contra-intuitivas de partículas extremamente pequenas de matéria, pudessem resolver Problemas NP-completos em tempo polinomial. Mas isso agora parece improvável: o problema de fatoração é, na verdade, um dos poucos problemas NP difíceis que não são conhecidos como NP-completos.
Sipser também diz que "o problema P-versus-NP tornou-se amplamente reconhecido na comunidade matemática como uma questão matemática que é fundamental, importante e bela. Eu acho que ajudou a unir as comunidades de matemática e ciência da computação". 
Mas se, como diz Sipser, "a complexidade acrescenta uma nova ruga a problemas antigos" na matemática, isso muda as questões que a ciência da computação exige. “Quando você se depara com um novo problema computacional”, diz Sipser, “o que a teoria da NP-completeness lhe oferece é, em vez de gastar todo o seu tempo procurando um algoritmo rápido, você pode gastar metade do seu tempo procurando um algoritmo rápido e a outra metade do seu tempo procurando uma prova de NP-completude.”
Sipser aponta que alguns algoritmos para problemas NP-completos exibem complexidade exponencial apenas no pior cenário e que, no caso médio, eles podem ser mais eficientes que algoritmos de tempo polinomial. Mas mesmo lá, NP-completeness "diz algo muito específico", diz Sipser. "Isso indica que, se você procurar um algoritmo que funcione em todos os casos e oferecer a melhor solução, estará condenado: nem tente. Essa é uma informação útil.

tradução de: Explained: P vs. NP