b'\n_START_ARTICLE_\nNP-equivalente\n_START_PARAGRAPH_\nEn teor\xc3\xada de la complejidad computacional, la clase de complejidad NP-equivalente es el conjunto de problemas de la funci\xc3\xb3n que son NP-f\xc3\xa1cil y NP-duro.\xe2\x80\x8b   NP-equivalente es el an\xc3\xa1logo de NP-completo para problemas de la funci\xc3\xb3n._NEWLINE_Por ejemplo, el problema BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalent.  Dado un conjunto de n\xc3\xbameros enteros, BUSQUEDA-SUBCONJUNTO-SUMA es el problema de encontrar alg\xc3\xban subconjunto no vac\xc3\xado de enteros cuya suma sea cero (o devolver el conjunto vac\xc3\xado si no existe tal subconjunto).  Este problema de optimizaci\xc3\xb3n es similar al problema de decisi\xc3\xb3n SUBCONJUNTO-SUMA.  Dado un conjunto de n\xc3\xbameros enteros, SUBCONJUNTO-SUMA es el problema de saber si existe alg\xc3\xban subconjunto cuya suma sea exactamente cero.  SUBCONJUNTO-SUMA es NP-Completo._NEWLINE_Para demostrar que BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalente,se debe demostrar que es a la vez NP-duro y NP-f\xc3\xa1cil._NEWLINE_Est\xc3\xa1 claro que es NP-duro. Si tuvi\xc3\xa9ramos un caja negra que resuelve BUSQUEDA-SUBCONJUNTO-SUMA en una unidad de tiempo, entonces ser\xc3\xada f\xc3\xa1cil de resolver SUBCONJUNTO-SUMA.  Simplemente se pregunta a la caja negra para que encontre el subconjunto que sume cero, a continuaci\xc3\xb3n, se comprueba si se ha devuelto un conjunto no vac\xc3\xado._NEWLINE_Tambi\xc3\xa9n es NP-f\xc3\xa1cil.  Si tuvi\xc3\xa9ramos un caja negra que resuelve SUBCONJUNTO-SUMA en una unidad de tiempo, entonces podr\xc3\xadamos utilizarlo para resolver BUSQUEDA-SUBCONJUNTO-SUMA. Si devuelve falso, devolvemos inmediatamente el conjunto vac\xc3\xado. De lo contrario, visitamos cada elemento en orden y lo eliminamos con tal de que SUBCONJUNTO-SUMA adquiera regreso verdadero despu\xc3\xa9s de que lo removamos. Una vez que hemos visitado todos los elementos, ya no podremos ser capaces de eliminar cualquier elemento sin cambiar la respuesta de verdadero a falso; en este punto el subconjunto restante de los elementos originales debe sumar cero. Esto nos obliga a se\xc3\xb1alar que las eliminaciones posteriores de elementos no alteran el hecho de que la eliminaci\xc3\xb3n de un elemento anterior cambi\xc3\xb3 la respuesta de verdadero a falso. En pseudoc\xc3\xb3digo:_NEWLINE_funci\xc3\xb3n BUSQUEDA-SUBCONJUNTO-SUMA(conjunto S)_NEWLINE_    si no(SUBCONJUNTO-SUMA(S))_NEWLINE_        retornar {}_NEWLINE_    para cada x en S_NEWLINE_        si SUBCONJUNTO-SUMA(S - {x})_NEWLINE_            S\xc2\xa0:= S - {x}_NEWLINE_    retornar S_NEWLINE_Otro de los problemas NP-equivalente conocido es el Problema del viajante.'