NP (complexidade)

Na teoria da complexidade computacional, NP é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) que denota o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística. Uma definição equivalente é o conjunto de problemas de decisão que podem ter seu certificado verificado em tempo polinomial por uma máquina de Turing determinística.

Introdução e aplicações

A importância desta classe de problemas de decisão é que contém muitos problemas de busca e de otimização para onde se deseja saber se existe uma solução. Nesta classe está o problema do caixeiro-viajante (também chamado de problema do agente de vendas ou problema do vendedor viajante) onde se quer saber se existe um caminho ótimo que passe por todas as interpolações de um certo grafo e o Problema de satisfatibilidade booleana aonde se deseja saber se uma certa fórmula lógica proposicional pode ser verdadeira para algum conjunto de valores boleanos para as variáveis.

Como um simples exemplo, considere o problema da determinação se um número n é um número composto. Para grandes números, isto se constitui um programa muito difícil para resolver de forma eficiente, a abordagem mais simples requer tempo exponencial de log n, o número de bit da entrada. Por outro lado, uma vez encontrada uma fator candidato de n a seguinte função pode rapidamente nos dizer se ele é ou não realmente um fator

 logico eFatorNãoTrivial (n, d)
     Se n é divisivel por d e
        d ≠ 1 e d ≠ n
         retorna verdadeiro
     Senão
         retorna falso

Se n é composto, então esta função ira retornar verdadeiro para alguma entrada d. Se n é primo, esta função ira sempre retornar falso, qualquer que seja d. Todos os problemas NP tem uma função determinística parecida com esta, a qual recebe como entrada um valor e uma prova a ser testada. Nós devemos ser capazes de verificar se a prova é correta em tempo polinomial. Dizemos que uma maquina como esta é o verificador para o problema.

Se temos uma maquina não determinística, testar um número para determinar sua composição é fácil. Ele pode ser repartido em n caminhos diferentes em O(log n) passos (veja a notação O); então, cada um destes pode chamar eFatorNãoTrivial (n, d) para cada um d. Se qualquer um for bem sucedido, o número é composto; caso contrario; ele é primo.

Portando, a transformação de problemas NP é eficiente para descobrir a resposta, tendo-se uma forma (tempo-polinomial) de verificá-lo para um item. Esta transformação foi resolvida (veja Teste de primalidade AKS) para testes de composição somente em 2002; Ainda não há uma forma (tempo-polinomial) conhecida para um problema mais geral a fatoração, ou seja, determinar se um número entre ' e m divide n.

Exemplos

• O problema do isomorfismo de grafos: determinar se dois grafos podem ser desenhados de forma idêntica.
• O problema do caixeiro viajante, onde queremos saber se existe uma rota de qualquer comprimento que passe através de todos os nodos de uma certa rede.
• O Problema de Roteamento de Veículos, onde queremos alocar uma frota veicular para o atendimento de um conjunto de consumidores. É semelhante ao problema do caixeiro viajante, mas possui mais de um veículo para entregas e coletas de mercadorias.
• O problema da factibilidade lógica, onde nós queremos conhecer se uma certa formula em uma proposição lógica com variáveis lógicas pode ser satisfeita ou não.

Veja NP-completo para uma lista adicional de importantes problemas em NP.

Dificuldades envolvidas NP

Devido ao fato de existirem muitos problemas importantes nesta classe, existe um esforço intensivo para encontrar algoritmos para resolver problema NP em um tempo que seja polinomial em relação ao tamanho da entrada. Contudo, existe um grande número de problemas NP que resiste a tais tentativas, parecendo requerer um tempo super-polinomial. Se estes problemas realmente não podem ser resolvidos em tempo polinomial é um das grandes questões abertas na ciência da computação

Uma importante noção neste contexto é o conjunto de problemas de decisão NP-Completo, o qual é um subconjunto de NP e pode ser informalmente descrito como os mais difíceis problemas em NP. Se existe um algoritmo em tempo polinomial para um deles, então haverá um algoritmo em tempo polinomial para todos os problemas em NP. Devido a isto, e a falha das pesquisas em encontrar um algoritmo polinomial para qualquer problema NP-completo, uma vez que foi provado que um problema pode ser caracterizado como NP-completo este é um sinal largamente aceito que um algoritmo polinomial para este problema não deve existir.

Outra caracterização

Há também uma caracterização lógica mais simples do problema NP; ela está expressa precisamente em uma linguagem baseada em lógica de segunda-ordem restrita pela exclusão da qualificação universal alem de relações, funções, e subconjuntos.

NP podem ser vistos com um tipo muito simples de sistema de prova interativa, onde a prova vem junto com o certificado de prova e a verificação é uma maquina determinística em tempo polinomial que a checa. Ela é completa porque a correta expressão de prova será obtida para ela considerando que ela exista, e isto é legitimo porque a certificação não pode ser aceita se não existir uma aceitável expressão de prova.

Um grande resultado da teoria da complexidade é que problemas NP podem ser caracterizados como os problemas solucionáveis por provas de checagem probabilística onde os verificadores usam O(logn) bit's aleatórios e examinar somente um número constantes de bits da sentença de prova (a classe PCP(log n, 1)). Mais informalmente, isto significa que a verificação NP descrita acima pode ser substituída por uma checagem de poucos lugares na sentença de prova, e usando um número limitado de lançamento de moedas podemos determinar a resposta correta com grande probabilidade. Isso permite vários resultados a cerca da dificuldade de algoritmos aproximados serem provados.

Um trabalho recente de L. Gordeev e E. H. Haeusler demonstrou que NP = CoNP = PSPACE através da compressão de provas em Dedução Natural na Lógica Minimal Implicacional.

Exemplo

A versão de decisão do problema do caixeiro viajante é da ordem NP. Dado uma matriz de distâncias entre n cidades, o problema é determinar se há uma rota que visita todas as cidades com a distância total menor que k. Uma máquina de Turing não determinística pode encontrar esta rota como se segue:

• Para cada cidade visitada ele sugere a próxima cidade a ser visitada, até que se tenha visitado cada vértice. Quando isto é conseguido, o processo é interrompido.
• Ao fim se verifica se a rota que foi obtida tem um custo menor que k com um tempo na ordem O(n).

Pode-se pensar que cada sugestão como uma ramificação, uma nova cópia da maquina de Turing irá seguir cada possível caminho adiante, e se ao menos uma das máquinas encontrar uma rota de distância menor que k, aquela máquina aceitará a entrada. (Equivalentemente, isto pode ser pensado como uma simples máquina de Turing que sempre sugere corretamente).

O que torna isto uma versão de decisão natural deste problema é que, se pudermos solucionar este problema rapidamente, nós poderemos usar a pesquisa binária para resolver a versão otimizada do problema original (encontrar a rota que possua este exato comprimento) muito rapidamente também.

Bibliografia

• Zôo da Complexidade: NP
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp.979–983.

Ver também

• Máquina de Turing