Tempo pseudopolinomial

Na teoria da complexidade computacional, um algoritmo numérico é executado em tempo pseudopolinomial se o seu tempo de execução é polinomial no valor numérico da entrada, mas é exponencial no comprimento da entrada – o número de bits necessários para representá-lo.

Um problema NP-completo com algoritmos tempo pseudopolinomial conhecidos é chamado fracamente NP-completo. Um problema NP-completo é chamado de fortemente NP-completo se for comprovado que ele não pode ser resolvido por um algoritmo de tempo pseudopolinomial, a menos que P=NP. Os tipos fortes/fracos de NP-difículdade são definidos de forma análoga.

Exemplo

Considere o problema de testar se um número n é primo, verificando ingenuamente se nenhum número em $\{2,3,\dots ,{\sqrt {n}}\}$ divide $n$ uniformemente. Esta abordagem pode levar até ${\sqrt {n}}-1$ divisões, o que é sub-linear no valor de n, mas exponencial no comprimento de n (que é, aproximadamente, $\log(n)$). Por exemplo, um número n ligeiramente menor do que 10,000,000,000 necessitaria de até, aproximadamente, 100.000 divisões, mesmo o comprimento de n tendo apenas 10 dígitos. Além disso, pode-se facilmente escrever uma entrada (digamos, um número com 300 dígitos) para o qual este algoritmo é impraticável. Já que a complexidade computacional mede dificuldade em relação ao tamanho da entrada (codificada), este algoritmo ingênuo é, na verdade, exponencial. Ele é, no entanto, de tempo pseudopolinomial.

Compare este algoritmo com um verdadeiro algoritmo polinomial — digamos, o simples algoritmo da adição: Somar dois números de 9 digitos leva em torno de 9 passos simples e, em geral, o algoritmo é verdadeiramente linear no comprimento da entrada. Em comparação com os números a serem somados (em bilhões), o algoritmo poderia ser chamado de "tempo pseudologarítmico", embora tal termo não seja padrão. Assim, somar números de 300 dígitos não é impraticável. Da mesma forma, a divisão é quadrática: um número com m dígitos pode ser dividido por um número com n dígitos em $O(mn)$ etapas (ver notação Big O).

No caso da primalidade, acontece que existe um algoritmo diferente para testar se n é primo (descoberto em 2002), que é executado em tempo $O((\log {n})^{6})$.

Outro exemplo de um problema que, geralmente, só pode ser resolvido em tempo pseudopolinomial é o problema da Mochila – a menos que P=NP.

Generalizando para problemas não-numéricos

Embora a noção do tempo pseudopolinomial seja usada quase exclusivamente para problemas numéricos, o conceito pode ser generalizado: A função m é pseudopolinomial se m(n) não é maior do que uma função polinomial do problema de tamanho n e uma propriedade adicional da entrada, k(n). (Presumidamente, k é escolhido para ser algo relevante para o problema). Isso faz dos problemas polinomiais um caso especial, tomando k como o valor numérico de entrada.

A distinção entre o valor de um número e o seu comprimento é a seguinte codificação: se entradas numéricas são sempre codificados em unário, então, pseudopolinomial coincidiria com polinomial.

Veja também

• Fortemente NP-completo
• Tempo quasi-polinomial

Referências

• M. R. Garey e D. S. Johnson. Computadores e Intratabilidade: Um Guia para a Teoria da NP-Completude. W. H. Freeman and Company, 1979.