Dureza NP

Diagrama de Euler para conjuntos de problemas P, NP, NP-completos e NP-difíceis.
Diagrama de Euler para conjuntos de problemas P , NP , NP-completo e NP-difícil. O lado esquerdo é válido sob a suposição de que P≠NP , enquanto o lado direito é válido sob a suposição de que P=NP (exceto que a linguagem vazia e seu complemento nunca são NP-completos)

Na teoria da complexidade computacional , um problema computacional H é chamado de NP-difícil se, para cada problema L que pode ser resolvido em tempo polinomial não determinístico , há uma redução em tempo polinomial de L para H. Ou seja, assumindo que uma solução para H leva 1 unidade de tempo, a solução de H pode ser usada para resolver L em tempo polinomial. [1] [2] Como consequência, encontrar um algoritmo de tempo polinomial para resolver um único problema NP-difícil daria algoritmos de tempo polinomial para todos os problemas na classe de complexidade NP . Como se suspeita que P≠NP , é improvável que tal algoritmo exista. [3] Suspeita-se que não existam algoritmos de tempo polinomial para problemas NP-difíceis, mas isso não foi comprovado. [4] Um exemplo simples de problema NP-difícil é o problema da soma de subconjuntos .

Informalmente, se H for NP-difícil, então será pelo menos tão difícil de resolver quanto os problemas em NP . No entanto, a direção oposta não é verdadeira: alguns problemas são indecidíveis e, portanto, ainda mais difíceis de resolver do que todos os problemas em NP, mas provavelmente não são NP-difíceis (a menos que P=NP). [5]

Definição

Um problema de decisão H é NP-difícil quando para cada problema L em NP, há uma redução de muitos-um em tempo polinomial de L para H . [1] : 80 

Outra definição é exigir que haja uma redução em tempo polinomial de um problema NP -completo G para H. [1] : 91  Como qualquer problema L em NP se reduz em tempo polinomial a G , L se reduz por sua vez a H em tempo polinomial, portanto esta nova definição implica a anterior. Não restringe a classe NP-difícil a problemas de decisão, e também inclui problemas de busca ou problemas de otimização .

Consequências

Se P ≠ NP, então problemas NP-difíceis não poderiam ser resolvidos em tempo polinomial.

Alguns problemas de otimização NP-hard podem ser aproximados em tempo polinomial até alguma razão de aproximação constante (em particular, aqueles em APX ) ou mesmo até qualquer razão de aproximação (aqueles em PTAS ou FPTAS ). Existem muitas classes de aproximabilidade, cada uma permitindo a aproximação até um nível diferente. [6]

Exemplos

Todos os problemas NP-completos também são NP-difíceis (ver Lista de problemas NP-completos ). Por exemplo, o problema de otimização de encontrar a rota cíclica de menor custo através de todos os nós de um grafo ponderado – comumente conhecido como problema do caixeiro viajante – é NP-difícil. [7] O problema da soma do subconjunto é outro exemplo: dado um conjunto de inteiros, algum subconjunto não vazio deles soma zero? Esse é um problema de decisão e é NP-completo.

Existem problemas de decisão que são NP-difíceis, mas não NP-completos, como o problema da parada . Esse é o problema que pergunta "dado um programa e sua entrada, ele funcionará para sempre?" Essa é uma pergunta sim / não e também um problema de decisão. É fácil provar que o problema da parada é NP-difícil, mas não NP-completo. Por exemplo, o problema da satisfatibilidade booleana pode ser reduzido ao problema da parada, transformando-o na descrição de uma máquina de Turing que tenta todas as atribuições de valores de verdade e quando encontra uma que satisfaça a fórmula, ela para e, caso contrário, entra em um loop infinito. Também é fácil ver que o problema da parada não está em NP já que todos os problemas em NP são decidíveis em um número finito de operações, mas o problema da parada, em geral, é indecidível . Existem também problemas NP-difíceis que não são NP-completos nem indecidíveis . Por exemplo, a linguagem das fórmulas booleanas quantificadas verdadeiras é decidível em espaço polinomial , mas não em tempo polinomial não determinístico (a menos que NP = PSPACE ). [8]

Convenção de nomenclatura NP

Problemas NP-difíceis não precisam ser elementos da classe de complexidade NP. Como o NP desempenha um papel central na complexidade computacional , ele é utilizado como base de diversas classes:

NP
Classe de problemas de decisão computacional para os quais qualquer solução sim pode ser verificada como uma solução em tempo polinomial por uma máquina de Turing determinística (ou solucionável por uma máquina de Turing não determinística em tempo polinomial).
NP-difícil
Classe de problemas que são pelo menos tão difíceis quanto os problemas mais difíceis do NP. Problemas NP-difíceis não precisam ser elementos de NP; na verdade, eles podem nem ser decidíveis.
NP-completo
Classe de problemas de decisão que contém os problemas mais difíceis em NP. Cada problema NP-completo deve estar em NP.
NP-fácil
No máximo tão difícil quanto NP, mas não necessariamente em NP.
NP-equivalente
Problemas de decisão que são NP-difíceis e NP-fáceis, mas não necessariamente em NP.
NP-intermediário
Se P e NP forem diferentes, então existem problemas de decisão na região de NP que ficam entre P e os problemas NP-completos. (Se P e NP são da mesma classe, então problemas NP-intermediários não existem porque neste caso todo problema NP-completo cairia em P, e por definição, todo problema em NP pode ser reduzido a um problema NP-completo. )

Áreas de aplicação

Problemas NP-difíceis são frequentemente resolvidos com linguagens baseadas em regras em áreas que incluem:

Veja também

Referências

  1. ^ abc Leeuwen, van de janeiro , ed. (1998). Manual de Ciência da Computação Teórica . Vol. A, Algoritmos e complexidade. Amsterdã: Elsevier. ISBN 0262720140. OCLC247934368  .
  2. ^ Knuth, Donald (1974). "Pós-escrito sobre problemas NP-difíceis". Notícias ACM SIGACT . 6 (2): 15–16. doi :10.1145/1008304.1008305. S2CID46480926  .
  3. ^ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Introdução à Teoria da Complexidade . Salão Prentice. pág. 69. ISBN 0-13-915380-2.
  4. ^ "Shtetl-Optimized» Arquivo de blog »O caso científico para P≠NP" . www.scottaaronson.com . Recuperado em 25/09/2016 .
  5. ^ "É indecidível (complemento de R) um subconjunto de NP-difícil?". Troca de pilha de ciência da computação . Recuperado em 09/02/2024 .
  6. ^ Escoffier, B.; Paschos, B.Th. (2010). “Um levantamento sobre a estrutura das classes de aproximação”. Revisão de Ciência da Computação . 4 (1): 19–40.
  7. ^ Lawler, EL ; Lenstra, JK ; Rinnooy Kan, AHG; Shmoys, DB (1985), O problema do caixeiro viajante: um tour guiado pela otimização combinatória , John Wiley & Sons, ISBN 0-471-90413-9.
  8. ^ Mais precisamente, esta linguagem é PSPACE completa ; ver, por exemplo, Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 189, ISBN 9783540210450.
Obtido em "https://en.wikipedia.org/w/index.php?title=NP-hardness&oldid=1209224352"