Tempo pseudo-polinomial - Pseudo-polynomial time

Na teoria da complexidade computacional , um algoritmo numérico é executado em tempo pseudo-polinomial se seu tempo de execução for um polinômio no valor numérico da entrada (o maior inteiro presente na entrada) - mas não necessariamente no comprimento da entrada (o número de bits necessários para representá-lo), que é o caso dos algoritmos de tempo polinomial .

Em geral, o valor numérico da entrada é exponencial no comprimento de entrada, razão pela qual um algoritmo de tempo pseudo-polinomial não é necessariamente executado em tempo polinomial em relação ao comprimento de entrada.

Um problema NP-completo com algoritmos de tempo pseudo-polinomiais conhecidos é chamado de NP-completo fraco . Um problema NP-completo é denominado fortemente NP-completo se for provado que não pode ser resolvido por um algoritmo de tempo pseudo-polinomial a menos que P = NP . Os tipos forte / fraco de dureza NP são definidos analogamente.

Exemplos

Teste de Primalidade

Considere o problema de testar se um número n é primo , verificando ingenuamente se nenhum número se divide igualmente. Essa abordagem pode levar a divisões, que são sublineares no valor de n, mas exponenciais no comprimento de n (que é cerca de ). Por exemplo, um número n ligeiramente inferior a 10.000.000.000 exigiria até aproximadamente 100.000 divisões, embora o comprimento de n seja de apenas 11 dígitos. Além disso, pode-se facilmente escrever uma entrada (digamos, um número de 300 dígitos) para a qual esse algoritmo é impraticável. Uma vez que a complexidade computacional mede a dificuldade em relação ao comprimento da entrada (codificada), esse algoritmo ingênuo é na verdade exponencial. Ele é , no entanto, o tempo pseudo-polinomial. ${\ displaystyle \ {2,3, \ dots, {\ sqrt {n}} \}}$ ${\ displaystyle n}$ ${\ displaystyle {\ sqrt {n}} - 1}$ ${\ displaystyle \ log (n)}$

Compare este algoritmo com um algoritmo numérico polinomial verdadeiro - digamos, o algoritmo direto para adição: adicionar dois números de 9 dígitos leva cerca de 9 etapas simples e, em geral, o algoritmo é verdadeiramente linear no comprimento da entrada. Comparado com os números reais que estão sendo adicionados (na casa dos bilhões), o algoritmo poderia ser chamado de "tempo pseudo-logarítmico", embora tal termo não seja padrão. Portanto, adicionar números de 300 dígitos não é impraticável. Da mesma forma, a divisão longa é quadrática: um número de m dígitos pode ser dividido por um número de n dígitos em etapas (consulte a notação Big O ). ${\ displaystyle O (mn)}$

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

Problema de mochila

No problema da mochila , recebemos itens com peso e valor , juntamente com a capacidade máxima de peso de uma mochila . O objetivo é resolver o seguinte problema de otimização; informalmente, qual é a melhor maneira de colocar os itens na mochila para maximizar o valor? ${\ displaystyle n}$ ${\ displaystyle w_ {i}}$ ${\ displaystyle v_ {i}}$ ${\ displaystyle W}$

maximizar

{\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

sujeito a e .

{\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}

{\ displaystyle x_ {i} \ in \ {0,1 \}}

Resolver este problema é NP-difícil , então um algoritmo de tempo polinomial é impossível a menos que P = NP . No entanto, um algoritmo de tempo é possível usando a programação dinâmica ; como o número precisa apenas de bits para ser descrito, esse algoritmo é executado em tempo pseudo-polinomial. ${\ displaystyle O (nW)}$ ${\ displaystyle W}$ ${\ displaystyle \ log W}$

Generalização para problemas não numéricos

Embora a noção de tempo pseudo-polinomial seja usada quase exclusivamente para problemas numéricos, o conceito pode ser generalizado: A função m é pseudo-polinomial se m ( n ) não for maior que uma função polinomial do tamanho do problema ne uma propriedade adicional da entrada, k ( n ). (Presumivelmente, k é escolhido para ser algo relevante para o problema.) Isso torna os problemas polinomiais numéricos um caso especial, considerando k como o valor numérico da entrada.

A distinção entre o valor de um número e seu comprimento é de codificação: se as entradas numéricas são sempre codificadas em unário , então o pseudo-polinômio coincidiria com o polinômio .

Dureza NP forte e fraca vs. algoritmos de tempo polinomial forte e fraco

Assumindo P! = NP, o seguinte é verdadeiro para problemas computacionais em números inteiros:

Se um problema é NP-difícil fracamente , então ele não tem um algoritmo de tempo fracamente polinomial (polinomial no número de inteiros e o número de bits no maior inteiro), mas pode ter um algoritmo de tempo pseudopolinomial (polinomial no número de inteiros e a magnitude do maior inteiro). Um exemplo é o problema de partição . Tanto a dureza NP fraca quanto o tempo polinomial fraco correspondem à codificação dos agentes de entrada na codificação binária .

Se um problema for fortemente NP-difícil , ele nem mesmo terá um algoritmo de tempo pseudo-polinomial . Ele também não tem um esquema de aproximação de tempo totalmente polinomial . Um exemplo é o problema de 3 partições . Tanto a dureza NP forte quanto o tempo pseudo-polinomial correspondem à codificação dos agentes de entrada na codificação unária .

Veja também

Referências

^ Michael R. Garey e David S. Johnson . Computadores e intratabilidade: um guia para a teoria da NP-completude . WH Freeman and Company, 1979.
^ Demaine, Erik. "Limites Algorítmicos Inferiores: Diversão com Provas de Dureza, Aula 2" .

[1] Michael R. Garey e David S. Johnson . Computadores e intratabilidade: um guia para a teoria da NP-completude . WH Freeman and Company, 1979.

[2] Demaine, Erik. "Limites Algorítmicos Inferiores: Diversão com Provas de Dureza, Aula 2" .

Languages

In other projects