En la teoría de la complejidad computacional , la clase de complejidad FNP es la extensión del problema de función de la clase de problema de decisión NP . El nombre es algo inapropiado, ya que técnicamente es una clase de relaciones binarias , no funciones, como explica la siguiente definición formal:
- Una relación binaria P ( x , y ), donde y es a lo sumo polinomialmente más larga que x , está en FNP si y solo si hay un algoritmo de tiempo polinomial determinista que puede determinar si P ( x , y ) se cumple dados tanto x como y . [1]
Esta definición no implica no determinismo y es análoga a la definición de verificador de NP.
Existe un lenguaje NP que corresponde directamente a cada relación FNP, a veces llamado problema de decisión inducido por o correspondiente a dicha relación FNP. Es el lenguaje que se forma tomando todas las x para las que se cumple P ( x , y ) dado algo de y ; sin embargo, puede haber más de una relación FNP para un problema de decisión particular.
Muchos problemas en NP, incluidos muchos problemas NP-completos , preguntan si existe un objeto en particular, como una tarea satisfactoria, un color de gráfico o un grupo de cierto tamaño. Las versiones de FNP de estos problemas preguntan no solo si existe, sino cuál es su valor si existe. Esto significa que la versión FNP de cada problema NP-complete es NP-hard . Bellare y Goldwasser demostraron en 1994, utilizando algunos supuestos estándar, que existen problemas en NP tales que sus versiones FNP no son autorreducibles , lo que implica que son más difíciles que su correspondiente problema de decisión. [2]
Para cada P ( x , y ) en FNP, el problema de búsqueda asociado con P ( x , y ) es: dado x , encuentre una y tal que P ( x , y ) se cumpla, o indique que no existe tal y . El problema de búsqueda para cada relación en FNP puede resolverse en tiempo polinomial si y solo si P = NP . Este resultado generalmente se expresa como "FP = FNP si y solo si P = NP "; sin embargo, para que esta afirmación sea cierta, es necesario redefinir FP y FNP para que los miembros de FP y FNP no sean relaciones, sino problemas de búsqueda asociados a relaciones.
Reducciones
Sean P 1 y P 2 dos problemas en FNP, con algoritmos de verificación asociados A 1 , A 2 . Una reducción P 1 y P 2 se define como dos funciones computables de manera eficiente, f y g , tales que [3]
- f mapas de entradas x a P 1 a las entradas de f ( x ) a P 2 ;
- g asigna las salidas y a P 2 a las salidas g (y) a P 1 ;
- Para todos x y y : si A 2 ( f ( x ), y ) devuelve verdadero, entonces A 1 ( x , g ( Y )) devuelve verdadero;
- Para todo x : si A 2 ( f ( x ), y ) devuelve falso, entonces A 1 ( x , g ( y )) devuelve falso para todo y .
Clases de complejidad relacionadas
- FP es el conjunto de relaciones binarias para las que existe un algoritmo de tiempo polinomial que, dado x , encuentra alguna y para la que se cumple P ( x , y ). La relación entre FNP y FP es análoga a la relación entre NP y P.
- TFNP es un subconjunto de FNP: contiene aquellas relaciones en FNP para las cuales, para cada x , existe al menos una y para la que se cumple P ( x , y ).
Referencias
- ^ Elaine Rich, Autómatas, computabilidad y complejidad: teoría y aplicaciones , Prentice Hall, 2008, ISBN 0-13-228806-0 , sección 28.10 "Las clases de problemas FP y FNP", págs. 689-694
- ^ M. Bellare y S. Goldwasser. La complejidad de la decisión frente a la búsqueda . Revista SIAM de Computación, Vol. 23, No. 1, febrero de 1994.
- ^ Daskalakis, Costis (2015). "22. PPAD" . MIT OpenCourseWare .