FNP (clase de complejidad)

En complejidad computacional, FNP (function NP o NP funcional) es la clase de complejidad que extiende la clase NP (la cual incluye exclusivamente problemas de decisión), hacia problemas computacionales de tipo funcional, es decir, aquellos que obtienen como salidas valores distintos de SÍ o NO.

Sin embargo, a pesar del nombre de la clase, técnicamente ésta no incluye funciones, sino relaciones binarias.

Definición formal

Una relación binaria P(x,y), donde y es a lo más polinómicamente más grande que x, está en FNP si y sólo si existe un algoritmo determinista que puede determinar en tiempo polinómico si, dados x e y, se cumple P(x,y).

Esta definición no involucra no-determinismo y es análoga a la definición verificadora de NP. Existe un lenguaje NP directamente correspondiente a cada relación FNP, el cual es llamado problema de decisión "inducido por" o "correspondiente a" dicha relación FNP. Este es el lenguaje que se obtiene tomando todos los x para los cuales existe algún y tal que se cumple P(x,y). Sin embargo, puede haber más de una relación FNP para un problema de decisión en particular.

Muchos problemas en NP, incluyendo muchos NP-completos, preguntan si existe un objeto solución con ciertas características: por ejemplo, una asignación satisfacible en un problema de lógica, o un coloreo de grafos o un clique de un cierto tamaño, en un problema de teoría de grafos. Las versiones FNP de estos problemas preguntan no sólo si existe una solución, sino además qué valores posee ésta si es que existe. Esto significa que la versión FNP de cada problema NP-completo es NP-hard. En 1994 se demostró que existen problemas NP-completos tales que sus versiones FNP no son auto-reducibles, lo que implica que dichos problemas son más difíciles que su correspondiente problema de decisión.^[1]

FP = FNP si y sólo si P = NP.

Referencias

↑ Bellare, Mihir; Goldwasser, Shafi (Febrero de 1994). «The complexity of decision versus search». SIAM Journal on Computing (en inglés) 23 (1).

Bibliografía

Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 0132288060, section 28.10 "The problem classes FP and FNP", pp. 689-694

Véase también

FP (clase de complejidad)

Enlaces externos

Complexity Zoo: FNP

Datos: Q2898287

[1] Bellare, Mihir; Goldwasser, Shafi (Febrero de 1994). «The complexity of decision versus search». SIAM Journal on Computing (en inglés) 23 (1).

[1]