NP-fácil

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em complexidade computacional, a classe de complexidade NP-fácil é a classe de problemas que são solúveis em tempo polinomial por uma máquina de Turing determinística com um oráculo para algum problema de decisão em NP.

Em outras palavras, um problema X é NP-fácil se e somente se existe algum problema Y em NP tal que X é redutível em tempo polinomial a Y.[1] Isso significa que dado um oráculo para Y, existe um algoritmo que resolve X em tempo polinomial (possivelmente através do uso repetitivo dese oráculo).

NP-fácil é um outro nome para FPNP ou para FΔ2P.

Um exemplo de um problema NP-fácil é o problema de ordenação de uma lista de strings. O problema de decisão "a string A é maior que a string B" está em NP. Existem algoritmos como o Quicksort que podem ordenar a lista usando apenas um número polinomial de chamadas à função de comparação, além de uma quantidade polinomial de trabalhos adicionais. Portanto, ordenação é NP-fácil.

Também existem problemas mais difíceis que são NP-fácil. Veja NP-equivalente para um exemplo.

A definição de NP-fácil usa a redução em tempo polinomial e não a redução muitos-para-um porque as respostas do problema Y são apenas VERDADEIRO ou FALSO, mas as respostas do problema X podem ser mais abrangentes. Portanto, não existe um modo geral de traduzir uma instância de X para uma instância de Y com a mesma resposta.

Notes[editar | editar código-fonte]

  1. Garey & Johnson (1979), p. 117, 120.

Referências[editar | editar código-fonte]

  • Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.