NP-equivalente

Em complexidade computacional, a classe de complexidade NP-equivalente é a classe de problemas que são tanto NP-fácil quanto NP-difícil. .

Por exemplo, o problema ACHAR-SUBCONJUNTO-SOMA está em NP-equivalente. Dado um conjunto de números inteiros, ACHAR-SUBCONJUNTO-SOMA é o problema que consiste em encontrar algum subconjunto dos inteiros que somam zero (caso não exista tão subconjunto, o conjunto vazio deve ser retornado). Esse problema de otimização é parecido com o problema de decisão SUBCONJUNTO-SOMA. Dado uma lista de inteiros, SUBCONJUNTO-SOMA é o problema que consiste em decidir se existe algum subconjunto cujos integrantes somem zero (ou seja, esse problema retorna apenas uma de duas possíveis respostas: sim ou não. O problema ACHAR-SUBCONJUNTO-SOMA retorna um conjunto). SUBSCONJUNTO-SOMA é NP-completo.

Para mostrar que ACHAR-SUBCONJUNTO-SOMA é NP-equivalente, temos que mostrar que ele é NP-difícil e NP-fácil.

Claramentente vemos que esse problema é NP-difícil. Se nós tivéssemos uma caixa preta que resolvesse ACHAR-SUBCONJUNTO-SOMA em uma unidade de tempo, então seria fácil resolver SUBCONJUNTO-SOMA. Bastaria pedir a caixa preta para achar o subconjunto que soma zero e depois conferir se ela retornou um conjunto não-vazio.

Esse probelma também é NP-fácil. Se nós tivéssemos uma caixa preta que resolvesse SUBCONJUNTO-SOMA em uma unidade de tempo, então nós poderíamos usá-la para resolver ACHAR-SUBCONJUNTO-SOMA. Se a caixa retornasse falso, nós retornaríamos de imediato o conjunto vazio. Caso contrário, nós visitaríamos cada elemento de modo ordenado e checaríamos se SUBCONJUNTO-SOMA ainda poderia retornar Verdadeiro após a remoção do elemento escolhido. Depois de visitar todos os elmentos, não seria possível remover qualquer elemento sem mudar a resposta da caixa preta de verdadeiro para falso. Nesse ponto o subconjunto restante deve somar zero. Em pseudocódigo:

função ACHAR-SUBCONJUNTO-SOMA(conjuntoo S)
    se negação(SUBCONJUNTO-SOMA(S))
        retorne {}
    para cada x em S
        se SUBCONJUNTO-SOMA(S - {x})
            S := S - {x}
    retorne S

Outro problema NP-equivalente bastante conhecido é o Problema do caixeiro viajante.

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.