Fortemente NP-completo
Em Complexidade computacional, NP-completude forte é uma propriedade computacional de problemas que é um caso especial de NP-completude. Um problema computacional geral pode ter parâmetros numéricos. Por exemplo, a entrada para o problema de empacotamento de caixas é uma lista de objetos de tamanhos específicos e um tamanho para a caixa que deve conter os objetos — estes tamanhos de objetos e tamanhos de caixas são parâmetros numéricos.
Um problema é dito ser fortemente NP-completo, se ele permanece NP-completo mesmo quando todos os seus parâmetros numéricos são delimitados por um polinômio no comprimento da entrada.[1] Um problema é dito ser fortemente NP-difícil se um problema fortemente NP-completo tem uma redução polinomial para ele; em otimização combinatória, particularmente, a frase “fortemente NP-difícil” é reservada a problemas que não se sabe ter uma redução polinomial a outro problema fortemente NP-difícil. Normalmente parâmetros numéricos para um problema são dados em um Sistema de numeração binário, então um problema de entrada tamanho n pode conter parâmetros cujo tamanho seja exponencial em n. Se nós redefinirmos o problema para ter os parâmetros dados em notação unária, então os parâmetros dever estar delimitados pelo tamanho da entrada. Assim, NP-completude forte ou NP-dificuldade podem também ser definidas como a NP-completude ou NP-dificuldade desta versão unária do problema.
Por exemplo, o problema do empacotamento de caixas é fortemente NP-completo enquanto o Problema da mochila é apenas fracamente NP-completo. Assim, a versão do problema de empacotamento de caixas onde o tamanho do objeto e o tamanho da caixa são inteiros delimitados por um polinômio continua NP-completo, enquanto a versão correspondente do problema da mochila pode ser resolvido em tempo pseudo-polinomial por Programação dinâmica.
Enquanto problemas fracamente NP-completos possam admitir soluções eficientes na pratica com tanto que suas entradas sejam de magnitude relativamente pequena, problemas fortemente Np-completos não admitem soluções eficientes nestes casos. De uma perspectiva teórica, qualquer problema fortemente NP-dificil com uma função objetiva polinomialmente delimitada não pode ter um esquema de aproximação total em tempo polinomial a menos que P=NP.[2] Entretanto, o inverso não ocorre: e.g se P não for igual a NP, o problema da mochila com duas restrições não é fortemente NP-difícil, mas não tem um esquema de aproximação total em tempo polinomial mesmo quando o objetivo ótimo é polinomialmente delimitado.[3]
Alguns problemas fortemente NP-completos podem ser fáceis de resolver na média, mas é mais provável que dificuldades serão encontradas na prática. A menos que P = NP (P versus NP) não existe esquema de aproximação total em tempo polinomial para os problemas fortemente NP-completos.
Veja também[editar | editar código-fonte]
Referências[editar | editar código-fonte]
- ↑ Garey, M. (julho de 1978). «'Strong' NP-Completeness Results: Motivation, Examples, and Implications». New York, NY: ACM. Journal of the ACM. 25 (3): 499–508. ISSN 0004-5411. MR 478747. doi:10.1145/322077.322090
- ↑ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8. MR 1851303
- ↑ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. [S.l.]: Springer