Em seu artigo (p. 503), Garey e Johnson comentam:
... pode haver um problema de NP-completo que não é nem NP-completo no sentido forte nem solucionável por um algoritmo de tempo pseudo-polinomial ...
Alguém conhece alguns problemas de candidatos com as propriedades mencionadas acima?
Penso que a possível resposta a essa pergunta pode ser uma lista de problemas NP-completos no sentido comum, de modo que nenhum algoritmo pseudopolinomial seja conhecido por eles.
ds.algorithms
np-hardness
np
Oleksandr Bondarenko
fonte
fonte
Respostas:
Não sei se você está interessado em ouvir mais detalhes do meu comentário sobre sua pergunta, mas aqui estão mais detalhes de qualquer maneira.
Se P = NP, todo problema em NP pode ser resolvido no tempo polinomial e, portanto, no tempo pseudo-polinomial, o que significa que nenhum problema satisfaz sua exigência, como Magnus observou em sua resposta. Portanto, assuma P ≠ NP no restante desta resposta.
Como P ≠ NP, existe uma linguagem L ∈NP ∖ P que não é NP completa (teorema de Ladner). Considere o seguinte problema:
Produto direto da Partição e da
Instância L : m inteiros positivos a 1 ,…, a m e k inteiros b 1 ,…, b k ∈ {0,1}.
Pergunta : Os dois itens a seguir são retidos?
(1) Os m inteiros um 1 , ..., um m formar um sim-exemplo do problema de partição.
(2) O k cadeia bit b 1 ... b k pertencente a L .
Seguindo o artigo de Garey e Johnson, defina a função Comprimento como m + ⌈log max i a i ⌉ + k e a função Max como max i a i .
É uma rotina verificar (i) que é NP-completo no sentido fraco, (ii) que não possui um algoritmo de tempo pseudo-polinomial e (iii) que não é NP-completo no ponto forte sentido.
(Dicas: (i) A associação ao NP decorre do fato de que tanto o problema da Partição quanto o L estão no NP. Para dureza do NP, reduza a Partição para esse problema. (Ii) Construa uma transformação pseudo-polinomial de L para esse problema. (iii) Construa uma transformação pseudo-polinomial desse problema em L usando o fato de que a Partição possui um algoritmo de tempo pseudo-polinomial.)
Não há nada de especial no problema da Partição nesta construção: você pode usar o seu problema favorito de NP completo com um algoritmo de tempo pseudo-polinomial.
fonte
Eu diria que a resposta é claramente não (isto é, ninguém sabe), porque ninguém sabe se os problemas completos de NP podem ser resolvidos no tempo polinomial , quanto mais no tempo pseudo- polinomial. (Todo algoritmo polinomial é, é claro, pseudopolinomial.) Se você encontrar um problema no NPC que não possa ser resolvido no tempo pseudopolinomial, você acabou de provar que P ≠ NP, então acho que é seguro dizer que nenhum exemplo será produzido tão cedo.
fonte