NP-equivalente

clase de complejidad

En teoría de la complejidad computacional, la clase de complejidad NP-equivalente es el conjunto de problemas de la función que son NP-fácil y NP-duro.[1]​ NP-equivalente es el análogo de NP-completo para problemas de la función.

Por ejemplo, el problema BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalent. Dado un conjunto de números enteros, BUSQUEDA-SUBCONJUNTO-SUMA es el problema de encontrar algún subconjunto no vacío de enteros cuya suma sea cero (o devolver el conjunto vacío si no existe tal subconjunto). Este problema de optimización es similar al problema de decisión SUBCONJUNTO-SUMA. Dado un conjunto de números enteros, SUBCONJUNTO-SUMA es el problema de saber si existe algún subconjunto cuya suma sea exactamente cero. SUBCONJUNTO-SUMA es NP-Completo.

Para demostrar que BUSQUEDA-SUBCONJUNTO-SUMA es NP-equivalente,se debe demostrar que es a la vez NP-duro y NP-fácil.

Está claro que es NP-duro. Si tuviéramos un caja negra que resuelve BUSQUEDA-SUBCONJUNTO-SUMA en una unidad de tiempo, entonces sería fácil de resolver SUBCONJUNTO-SUMA. Simplemente se pregunta a la caja negra para que encuentre el subconjunto que sume cero, a continuación, se comprueba si se ha devuelto un conjunto no vacío.

También es NP-fácil. Si tuviéramos un caja negra que resuelve SUBCONJUNTO-SUMA en una unidad de tiempo, entonces podríamos utilizarlo para resolver BUSQUEDA-SUBCONJUNTO-SUMA. Si devuelve falso, devolvemos inmediatamente el conjunto vacío. De lo contrario, visitamos cada elemento en orden y lo eliminamos con tal de que SUBCONJUNTO-SUMA adquiera regreso verdadero después 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ñalar que las eliminaciones posteriores de elementos no alteran el hecho de que la eliminación de un elemento anterior cambió la respuesta de verdadero a falso. En pseudocódigo:

función BUSQUEDA-SUBCONJUNTO-SUMA(conjunto S)
    si no(SUBCONJUNTO-SUMA(S))
        retornar {}
    para cada x en S
        si SUBCONJUNTO-SUMA(S - {x})
            S := S - {x}
    retornar S

Otro de los problemas NP-equivalente conocido es el Problema del viajante.

Notas editar

Referencias editar