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. 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. 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.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.
View More On Wikipedia.org
