FNP (complejidad)

En la teoría de la complejidad computacional , la clase de complejidad FNP es la extensión de problemas de función de la clase de problemas de decisión NP . El nombre es algo engañoso, ya que técnicamente es una clase de relaciones binarias , no de funciones, como explica la siguiente definición formal:

Una relación binaria P ( x , y ), donde y es como máximo polinomialmente más larga que x , está en FNP si y solo si existe un algoritmo determinista de tiempo polinomial que puede determinar si P ( x , y ) se cumple dados x e y . ^{[ 1 ]}

Esta definición no implica no determinismo y es análoga a la definición de NP basada en el verificador.

Existe un lenguaje NP que corresponde directamente a cada relación FNP, a veces llamado problema de decisión inducido por dicha relación o que corresponde a ella. Es el lenguaje formado al tomar 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 que induzca un problema de decisión particular.

Muchos problemas en NP, incluyendo muchos problemas NP-completos , pueden especificarse preguntando si existe un objeto particular, como una asignación satisfactoria, una coloración de grafos o una camarilla de cierto tamaño. Estos problemas a menudo corresponden a relaciones en FNP que preguntan no solo si existe un objeto, sino también qué valor o valores puede tener dicho objeto. Cuando una relación FNP corresponde de esta manera a un problema NP-completo, la relación es autorreducible . Bellare y Goldwasser demostraron en 1994, utilizando algunos supuestos estándar de la teoría de la complejidad, que existen problemas en NP tales que ninguna de sus versiones FNP es autorreducible, lo que implica que son más difíciles que su problema de decisión correspondiente. ^{[ 2 ]}

Para cada P en FNP, el problema de búsqueda asociado a P es: dado x , encontrar un y tal que P ( x , y ) se cumpla, o bien, indicar que no existe tal y . El problema de búsqueda para cada relación en FNP puede resolverse de forma determinista en tiempo polinomial si y solo si P = NP . Este resultado se suele enunciar como " FP = FNP si y solo si P = NP "; sin embargo, para que esta afirmación sea cierta, es necesario redefinir FP y FNP de modo que los miembros de FP y FNP no sean relaciones, sino problemas de búsqueda asociados a relaciones.

Sean P ₁ y P ₂ dos problemas en FNP, con algoritmos de verificación asociados A ₁ , A ₂ . Una reducción P ₁ y P ₂ se define como dos funciones computables en tiempo polinomial, f y g , tales que ^{[ 3 ]}

• f asigna las entradas x de P ₁ a las entradas f ( x ) de P ₂  ;
• g mapea las salidas y de P ₂ a las salidas g (y) de P ₁  ;
• Para todo x e y : si A ₂ ( f ( x ), y ) devuelve verdadero, entonces A ₁ ( x , g ( y )) devuelve verdadero;
• Para todo x : si A ₂ ( f ( x ), y ) devuelve falso para todo y , entonces A ₁ ( x , g ( y )) devuelve falso para todo y .

• FP es el conjunto de relaciones binarias para las cuales existe un algoritmo de tiempo polinomial que, dado x , encuentra algún y para el cual 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 un y para el cual se cumple P ( x , y ).

• Zoológico de la complejidad : FNP