O que é tempo pseudopolinomial? Como ele difere do tempo polinomial?

O que é tempo pseudopolinomial ? Como ele difere do tempo polinomial? Alguns algoritmos que são executados em tempo pseudopolinomial têm tempos de execução como O (nW) (para o problema da mochila 0/1 ) ou O (√n) (para a divisão experimental ); por que isso não conta como tempo polinomial?

Para entender a diferença entre o tempo polinomial e o tempo pseudopolinomial, precisamos começar formalizando o que significa "tempo polinomial".

A intuição comum para o tempo polinomial é "tempo O (n ^k ) para algum k". Por exemplo, a classificação por seleção é executada no tempo O (n ² ), que é o tempo polinomial, enquanto a resolução de força bruta TSP leva tempo O (n · n!), Que não é o tempo polinomial.

Todos esses tempos de execução se referem a alguma variável n que rastreia o tamanho da entrada. Por exemplo, na classificação por seleção, n se refere ao número de elementos na matriz, enquanto no TSP n se refere ao número de nós no gráfico. A fim de padronizar a definição do que "n" realmente significa neste contexto, a definição formal de complexidade de tempo define o "tamanho" de um problema da seguinte forma:

O tamanho da entrada para um problema é o número de bits necessários para escrever essa entrada.

Por exemplo, se a entrada para um algoritmo de classificação for uma matriz de inteiros de 32 bits, o tamanho da entrada seria 32n, onde n é o número de entradas na matriz. Em um grafo com n nós em arestas, a entrada pode ser especificada como uma lista de todos os nós seguida por uma lista de todas as arestas, o que exigiria Ω (n + m) bits.

Dada esta definição, a definição formal de tempo polinomial é a seguinte:

Um algoritmo roda em tempo polinomial se seu tempo de execução for O (x ^k ) para alguma constante k, onde x denota o número de bits de entrada dados ao algoritmo.

Ao trabalhar com algoritmos que processam gráficos, listas, árvores, etc., esta definição está mais ou menos de acordo com a definição convencional. Por exemplo, suponha que você tenha um algoritmo de classificação que classifica arrays de inteiros de 32 bits. Se você usar algo como classificação de seleção para fazer isso, o tempo de execução, como uma função do número de elementos de entrada no array, será O (n ² ). Mas como n, o número de elementos na matriz de entrada, corresponde ao número de bits de entrada? Conforme mencionado anteriormente, o número de bits de entrada será x = 32n. Portanto, se expressarmos o tempo de execução do algoritmo em termos de x em vez de n, obtemos que o tempo de execução é O (x ² ) e, portanto, o algoritmo é executado em tempo polinomial.

Da mesma forma, suponha que você faça uma pesquisa em profundidade em um gráfico, o que leva tempo O (m + n), onde m é o número de arestas no gráfico en é o número de nós. Como isso se relaciona com o número de bits de entrada fornecidos? Bem, se assumirmos que a entrada é especificada como uma lista de adjacências (uma lista de todos os nós e arestas), então, como mencionado anteriormente, o número de bits de entrada será x = Ω (m + n). Portanto, o tempo de execução será O (x), então o algoritmo é executado em tempo polinomial.

As coisas desmoronam, entretanto, quando começamos a falar sobre algoritmos que operam em números. Vamos considerar o problema de testar se um número é primo ou não. Dado um número n, você pode testar se n é primo usando o seguinte algoritmo:

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

Então, qual é a complexidade de tempo desse código? Bem, esse loop interno é executado O (n) vezes e, a cada vez, realiza algum trabalho para calcular n mod i (como um limite superior realmente conservador, isso pode certamente ser feito no tempo O (n ³ )). Portanto, esse algoritmo geral é executado no tempo O (n ⁴ ) e possivelmente muito mais rápido.

Em 2004, três cientistas da computação publicaram um artigo chamado PRIMES is in P, fornecendo um algoritmo de tempo polinomial para testar se um número é primo. Foi considerado um resultado marcante. Qual é o problema? Já não temos um algoritmo de tempo polinomial para isso, a saber, o acima?

Infelizmente, não. Lembre-se de que a definição formal de complexidade de tempo fala sobre a complexidade do algoritmo em função do número de bits de entrada. Nosso algoritmo é executado no tempo O (n ⁴ ), mas o que é isso em função do número de bits de entrada? Bem, escrever o número n leva O (log n) bits. Portanto, se deixarmos que x seja o número de bits necessários para escrever a entrada n, o tempo de execução desse algoritmo é na verdade O (2 ^4x ), que não é um polinômio em x.

Este é o cerne da distinção entre tempo polinomial e tempo pseudopolinomial. Por um lado, nosso algoritmo é O (n ⁴ ), que se parece com um polinômio, mas por outro lado, sob a definição formal de tempo polinomial, não é tempo polinomial.

Para ter uma intuição de por que o algoritmo não é um algoritmo de tempo polinomial, pense no seguinte. Suponha que eu queira que o algoritmo tenha muito trabalho. Se eu escrever uma entrada como esta:

10001010101011

então, na pior das hipóteses, levará algum tempo, digamos T, para ser concluído. Se eu agora adicionar um único bit ao final do número, assim:

100010101010111

O tempo de execução agora (no pior caso) será 2T. Posso dobrar a quantidade de trabalho que o algoritmo realiza apenas adicionando mais um bit!

Um algoritmo é executado em tempo pseudopolinomial se o tempo de execução for algum polinômio no valor numérico da entrada , e não no número de bits necessários para representá-lo. Nosso algoritmo de teste principal é um algoritmo de tempo pseudopolinomial, uma vez que é executado no tempo O (n ⁴ ), mas não é um algoritmo de tempo polinomial porque como uma função do número de bits x necessários para escrever a entrada, o tempo de execução é O (2 ^4x ). A razão pela qual o papel "PRIMES está em P" foi tão significativo foi que seu tempo de execução foi (aproximadamente) O (log ¹² n), que em função do número de bits é O (x ¹² ).

Então, por que isso importa? Bem, nós temos muitos algoritmos de tempo pseudopolinomial para fatorar inteiros. No entanto, esses algoritmos são, tecnicamente falando, algoritmos de tempo exponencial. Isso é muito útil para criptografia: se você deseja usar a criptografia RSA, precisa ter certeza de que não podemos fatorar números facilmente. Ao aumentar o número de bits nos números para um valor enorme (digamos, 1024 bits), você pode fazer com que a quantidade de tempo que o algoritmo de fatoração de tempo pseudopolinomial deve levar fique tão grande que seria completa e totalmente inviável fatorar o números. Se, por outro lado, podemos encontrar um polinômio algoritmo de fatoração de tempo , esse não é necessariamente o caso. Adicionar mais bits pode fazer com que o trabalho cresça muito, mas o crescimento será apenas um crescimento polinomial, não um crescimento exponencial.

Dito isso, em muitos casos, algoritmos de tempo pseudopolinomial são perfeitamente bons porque o tamanho dos números não será muito grande. Por exemplo, a classificação por contagem tem tempo de execução O (n + U), onde U é o maior número na matriz. Este é o tempo pseudopolinomial (porque o valor numérico de U requer bits O (log U) para escrever, então o tempo de execução é exponencial no tamanho da entrada). Se restringirmos U artificialmente para que U não seja muito grande (digamos, se deixarmos U ser 2), então o tempo de execução será O (n), que na verdade é o tempo polinomial. É assim que a ordenação de raiz funciona: ao processar os números um bit por vez, o tempo de execução de cada rodada é O (n), então o tempo de execução geral é O (n log U). Isso realmente é tempo polinomial, porque escrever n números para classificar usa Ω (n) bits e o valor de log U é diretamente proporcional ao número de bits necessários para escrever o valor máximo no array.

Espero que isto ajude!

A complexidade de tempo pseudo-polinomial significa polinômio no valor / magnitude da entrada, mas exponencial no tamanho da entrada.

Por tamanho, queremos dizer o número de bits necessários para escrever a entrada.

A partir do pseudocódigo da mochila, podemos determinar que a complexidade do tempo é O (nW).

// Input:
// Values (stored in array v) 
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W) 
for w from 0 to W 
    do   m[0, w] := 0 
end for  
for i from 1 to n do  
        for j from 0 to W do
               if j >= w[i] then 
                      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 
              else 
                      m[i, j] := m[i-1, j]
              end if
       end for 
end for

Aqui, W não é polinomial no comprimento da entrada, o que o torna pseudo-polinomial.

Seja s o número de bits necessários para representar W

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W  (because  2^(log(x)) = x)

Agora, running time of knapsack= O (nW) = O (n * 2 ^ s) que não é polinomial.