NP-fácil

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. 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 FP^NP ou para FΔ₂P.

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.

Referências

• 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.