En la teoría de complejidad de cómputo, el NP-equivalente de la clase de la complejidad es el sistema de los problemas de la función que son el NP-fácil y el NP-duro. NP-equivalente es el análogo NP-completo para los problemas de la función

Por ejemplo, el problema FIND-SUBSET-SUM está en NP-equivalente. Se da un sistema de los números enteros FIND-SUBSET-SUM el problema de encontrar un cierto subconjunto no vacío de los números enteros que agregue para arriba a cero (o a volver el sistema vacío si no hay tal subconjunto). Este problema de la optimización es similar al SUBSET-SUM del problema de decisión . Dado un sistema de números enteros, SUBSET-SUM es el problema de encontrar si existe un subconjunto que suma a cero. SUBSET-SUM es NP-completo.

Para demostrar que FIND-SUBSET-SUM es NP-equivalente, debemos demostrar que es NP-duro y NP-fácil.

Es claramente NP-duro. Si tuviéramos una caja negra que solucionó FIND-SUBSET-SUM en tiempo de unidad, después sería fácil solucionar SUBSET-SUM. Pedir simplemente la caja negra para encontrar el subconjunto que suma a cero, después el cheque si volvió un sistema no vacío.

Es también NP-fácil. Si teníamos una caja negra que solucionó SUBSET-SUM en tiempo de unidad, después podríamos utilizarlo para solucionar FIND-SUBSET-SUM. Si vuelve el falso, volvemos inmediatamente el sistema vacío. Si no, visitamos cada elemento en orden y lo quitamos a condición de que SUBSET-SUM todavía volvería el verdadero después de que lo quitemos. Una vez que hemos visitado cada elemento, podremos no más quitar cualquier elemento sin el cambio de la respuesta del verdadero al falso; a este punto el subconjunto restante de los elementos originales debe sumar a cero. Esto nos requiere observar que retiros posteriores de elementos no alteren el hecho de que el retiro de un elemento anterior cambió la respuesta del verdadero al falso. En pseudocode:

función FIND-SUBSET-SUM ( determinado S) del si no (SUBSET-SUM) de de vuelta {} para cada de x en S si SUBSET-SUM (S - {x}) S: = S - {x} de vuelta S

Otro problema NP-equivalente bien conocido es el problema de vendedor que viaja .