En la teoría de la complejidad computacional , la clase de complejidad NP-equivalente es el conjunto de problemas de función que son tanto NP-fáciles como NP-difíciles . [1] NP-equivalente es el análogo de NP-completo para problemas de función .
Por ejemplo, el problema FIND-SUBSET-SUM es NP-equivalente. Dado un conjunto de números enteros , FIND-SUBSET-SUM es el problema de encontrar un subconjunto no vacío de los números enteros que sumen cero (o devolver el conjunto vacío si no existe dicho subconjunto). Este problema de optimización es similar al problema de decisión SUBSET-SUM . Dado un conjunto de números enteros, SUBSET-SUM es el problema de encontrar si existe un subconjunto que sume cero. SUBSET-SUM es NP-completo.
Para demostrar que FIND-SUBSET-SUM es NP-equivalente, debemos demostrar que es tanto NP-difícil como NP-fácil.
Está claro que es NP-hard. Si tuviéramos una caja negra que resolviera FIND-SUBSET-SUM en tiempo unitario, entonces sería fácil resolver SUBSET-SUM. Simplemente pídale a la caja negra que encuentre el subconjunto que sume cero y luego verifique si devolvió un conjunto no vacío.
También es NP-easy. Si tuviéramos una caja negra que resolviera SUBSET-SUM en tiempo unitario, entonces podríamos usarla para resolver FIND-SUBSET-SUM. Si devuelve false , devolvemos inmediatamente el conjunto vacío. De lo contrario, visitamos cada elemento en orden y lo eliminamos siempre que SUBSET-SUM siga devolviendo true después de eliminarlo. Una vez que hayamos visitado todos los elementos, ya no podremos eliminar ningún elemento sin cambiar la respuesta de true a false ; en este punto, el subconjunto restante de los elementos originales debe sumar cero. Esto requiere que tengamos en cuenta que las eliminaciones posteriores de elementos no alteran el hecho de que la eliminación de un elemento anterior cambió la respuesta de true a false . En pseudocódigo:
función ENCONTRAR-SUBCONJUNTO-SUMA( conjunto S) si no (SUBCONJUNTO-SUMA(S)) devuelve {} para cada x en S si SUBCONJUNTO-SUMA(S – {x}) S := S – {x} volver SOtro problema NP-equivalente bien conocido es el problema del viajante de comercio .
En este contexto, NP significa tiempo polinomial no determinista .
También existen clases de equivalencia NP de funciones booleanas , donde NP significa negación y permutación . [2]