Por que o problema da mochila é pseudo-polinomial?

87

Eu sei que Knapsacké NP-completo, embora possa ser resolvido por DP. Eles dizem que a solução DP é pseudo-polynomial, uma vez que é exponencial no "comprimento da entrada" (ou seja, o número de bits necessários para codificar a entrada). Infelizmente eu não entendi. Alguém pode me explicar isso pseudo-polynomialdevagar?

Michael
fonte

Respostas:

89

O tempo de execução é O (NW) para um problema de mochila ilimitada com N itens e mochila de tamanho W. Porém, W não é polinomial no comprimento da entrada, o que o torna pseudo- polinomial.

Considere W = 1.000.000.000.000. Leva apenas 40 bits para representar esse número, então o tamanho da entrada = 40, mas o tempo de execução computacional usa o fator 1.000.000.000.000, que é O (2 40 ).

Portanto, o tempo de execução é mais precisamente considerado O (N.2 bits em W ), que é exponencial.

Veja também:

Moinudin
fonte
1
O link # 3 referindo-se a "Complexidade da programação dinâmica para o problema da mochila 0-1" está morto.
dev_nut
1
Desculpe, não entendi. Digamos que se temos um algoritmo com complexidade de tempo O (N), então temos O (2 ^ (bits em N)), que é exponencial? Obrigado ~
Lusha Li
3
@LushaLi Isso me ajudou: youtube.com/watch?v=9oI7fg-MIpE . Se N for uma matriz em que cada elemento tem uma entrada de tamanho máximo fixo (digamos que cada elemento na matriz não tenha mais do que 32 bits) e você executar um loop for nesta matriz uma vez, será um algoritmo de tempo polinomial na entrada tamanho N da matriz. No entanto, se N for um inteiro e você executar um loop sobre N, então N é ilimitado e cresce exponencialmente no número de bits necessários para representá-lo. Portanto, um simples loop for em N é, na verdade, exponencial. Observe que, no caso do array, o tamanho de cada elemento do array tem um limite superior.
max_max_mir
Eu não estava convencido. Existem muitos algoritmos com as mesmas propriedades que não são “pseudo-polinomiais”. Diga, qual é a complexidade do Sieve de Eratóstenes (ou qualquer outro localizador de números primos)?
Ofir A.
31

Na maioria dos nossos problemas, estamos lidando com grandes listas de números que se encaixam confortavelmente dentro dos tipos de dados int / float padrão. Por causa da forma como a maioria dos processadores são construídos para lidar com números de 4 a 8 bytes por vez, sem custo adicional (em relação aos números que cabem em, digamos, 1 byte), raramente encontramos uma mudança no tempo de execução de aumentar nossos números ou dentro das faixas que encontramos em problemas reais - então o fator dominante permanece apenas a quantidade absoluta de pontos de dados, os n ou m fatores aos quais estamos acostumados.

(Você pode imaginar que a notação Big-O está escondendo um fator constante que divide 32 ou 64 bits por dado, deixando apenas o número de pontos de dados sempre que cada um de nossos números caber em tantos bits ou menos )

Mas tente retrabalhar com outros algoritmos para agir em conjuntos de dados envolvendo grandes ints - números que exigem mais de 8 bytes para representar - e veja o que isso faz com o tempo de execução. A magnitude dos números envolvidos sempre faz diferença, mesmo em outros algoritmos como classificação binária, uma vez que você expanda além do buffer de segurança, os processadores convencionais nos dão "de graça" tratando de lotes de 4-8 bytes.

O truque com o algoritmo Knapsack que discutimos é que ele é incomumente sensível (em relação a outros algoritmos) à magnitude de um parâmetro específico, W. Adicione um bit a W e você dobra o tempo de execução do algoritmo. Não vimos esse tipo de resposta dramática às mudanças de valor em outros algoritmos antes deste, e é por isso que pode parecer que estamos tratando a mochila de maneira diferente - mas essa é uma análise genuína de como ela responde de uma forma não polinomial às mudanças no tamanho da entrada.

shaunak1111
fonte
8

O tempo de execução do algoritmo da mochila está limitado não apenas ao tamanho da entrada (n - o número de itens), mas também à magnitude da entrada (W - a capacidade da mochila) O (nW) que é exponencial em como é representado em computador em binário (2 ^ n). A complexidade computacional (ou seja, como o processamento é feito dentro de um computador por meio de bits) está preocupada apenas com o tamanho das entradas, não com suas magnitudes / valores .

Desconsidere a lista de valor / peso por um momento. Digamos que temos uma instância com capacidade de mochila 2. W levaria dois bits nos dados de entrada. Agora vamos aumentar a capacidade da mochila para 4, mantendo o resto da entrada. Nossa entrada cresceu apenas um bit, mas a complexidade computacional dobrou. Se aumentarmos a capacidade para 1024, teríamos apenas 10 bits de entrada para W em vez de 2, mas a complexidade aumentou por um fator de 512. A complexidade do tempo cresce exponencialmente no tamanho de W na representação binária (ou decimal) .

Outro exemplo simples que me ajudou a entender o conceito de pseudo-polinômio é o algoritmo de teste de primalidade ingênuo. Para um determinado número n, estamos verificando se ele é dividido igualmente por cada número inteiro no intervalo 2..√n, então o algoritmo executa √ (n − 1) etapas. Mas aqui, n é a magnitude da entrada, não seu tamanho.

                     Now The regular O(n) case

Por outro lado, a pesquisa de um determinado elemento em uma matriz é executada em tempo polinomial: O (n). Leva no máximo n passos e aqui n é o tamanho da entrada (o comprimento da matriz).

[ Veja aqui ]

Calculando os bits necessários para armazenar o número decimal

shaunak1111
fonte
3
Então, para seu último exemplo de pesquisa, por que não considerar n como binário também? se n = 1024, também leva apenas 10 bits, então não deveria ser pseudo-polinomial?
user1024
7

A maneira como eu entendo isso é que a capacidade seria O (W) se a entrada de capacidade fosse uma matriz de [1,2, ..., W] , que tem um tamanho de W. Mas a entrada de capacidade não é uma matriz de números, em vez disso, é um único inteiro. A complexidade do tempo diz respeito à relação com o tamanho da entrada. O tamanho de um inteiro NÃO é o valor do inteiro, mas o número de bits que o representam. Posteriormente, convertemos esse inteiro W em um array [1,2, ..., W] no algoritmo, levando as pessoas a pensarem erroneamente que W é o tamanho, mas esse array não é a entrada, o próprio inteiro é.

Pense na entrada como "uma matriz de coisas" e o tamanho como "quantas coisas na matriz". A entrada do item é, na verdade, uma matriz de n itens na matriz, portanto, tamanho = n. A entrada de capacidade NÃO é uma matriz de números W nela, mas um único inteiro , representado por uma matriz de bits de log (W). Aumente o tamanho dele em 1 (adicionando 1 bit significativo), W dobra, então o tempo de execução dobra, daí a complexidade de tempo exponencial.

lineil
fonte