En la teoría de la complejidad computacional , un problema de función es un problema computacional donde se espera una única salida (de una función total ) para cada entrada, pero la salida es más compleja que la de un problema de decisión . Para problemas de funcionamiento, la salida no es simplemente 'sí' o 'no'.
Definicion formal
Un problema funcional se define como una relación sobre cadenas de un alfabeto arbitrario :
Un algoritmo resuelve si por cada entrada tal que existe un satisfactorio , el algoritmo produce uno de esos .
Ejemplos de
Un problema de función bien conocido viene dado por el Problema de Satisfabilidad Funcional Booleano, FSAT para abreviar. El problema, que está estrechamente relacionado con el problema de decisión del SAT , se puede formular de la siguiente manera:
- Dada una fórmula booleana con variables , encuentra una tarea tal que evalúa a o decidir que no existe tal asignación.
En este caso la relación viene dada por tuplas de fórmulas booleanas adecuadamente codificadas y asignaciones satisfactorias. Si bien es un algoritmo SAT, alimentado con una fórmula, sólo necesita devolver "insatisfactorio" o "satisfactorio", un algoritmo FSAT necesita devolver alguna asignación satisfactoria en el último caso.
Otros ejemplos notables incluyen el problema del viajante , que pregunta por la ruta tomada por el vendedor, y el problema de factorización de enteros , que solicita la lista de factores.
Relación con otras clases de complejidad
Considere un problema de decisión arbitraria en la clase NP . Según la definición de NP , cada instancia de problema que se responde 'sí' tiene un certificado de tamaño polinomial que sirve como prueba de la respuesta "sí". Por tanto, el conjunto de estas tuplas forma una relación, que representa el problema de la función "dado en , encuentra un certificado por ". Este problema de función se denomina variante de función de; pertenece a la clase FNP .
FNP puede considerarse como la clase de función análoga de NP , en el sentido de que las soluciones de los problemas de FNP pueden verificarse de manera eficiente (es decir, en tiempo polinomial en términos de la longitud de la entrada) , pero no necesariamente se pueden encontrar de manera eficiente . Por el contrario, la clase FP , que se puede considerar como la clase de función análoga de P , consta de problemas de función cuyas soluciones se pueden encontrar en el tiempo polinomial.
Autorreductibilidad
Observe que el problema FSAT presentado anteriormente se puede resolver usando solo polinomialmente muchas llamadas a una subrutina que decide el problema SAT : un algoritmo puede preguntar primero si la fórmulaes satisfactorio. Después de eso, el algoritmo puede arreglar la variablea VERDADERO y pregunte de nuevo. Si la fórmula resultante sigue siendo satisfactoria, el algoritmo mantiene fijo en TRUE y continúa arreglando , de lo contrario decide que tiene que ser FALSO y continúa. Por lo tanto, FSAT se puede resolver en tiempo polinomial utilizando un oráculo que decide SAT . En general, un problema en NP se denomina autorreducible si su función variante puede resolverse en tiempo polinomial utilizando un oráculo que decida el problema original. Cada problema NP-completo es autoreducible. ¿Se conjetura [ por quién? ] que el problema de la factorización de enteros no es autoreducible.
Reducciones y problemas completos
Los problemas de función se pueden reducir de forma muy similar a los problemas de decisión: Problemas de función dados y Nosotros decimos eso reduce a si existen funciones computables de tiempo polinomial y tal que para todos los casos de y posibles soluciones de , sostiene que
- Si tiene un -solución, entonces tiene un -solución.
Por tanto, es posible definir problemas FNP-completos análogos al problema NP-completo:
Un problema es FNP-completo si cada problema en FNP se puede reducir a. La clase de complejidad de los problemas FNP-completos se denota mediante FNP-C o FNPC . Por lo tanto, el problema FSAT es también un problema FNP completo , y sostiene que si y solo si .
Problemas de función total
La relación utilizado para definir problemas de funciones tiene el inconveniente de estar incompleto: no todas las entradas tiene una contraparte tal que . Por tanto, la cuestión de la computabilidad de las pruebas no se separa de la cuestión de su existencia. Para superar este problema, es conveniente considerar la restricción de los problemas de funciones a las relaciones totales que dan como resultado la clase TFNP como una subclase de FNP . Esta clase contiene problemas como el cálculo de equilibrios de Nash puros en ciertos juegos estratégicos donde se garantiza que existe una solución. Además, si TFNP contiene algún problema de FNP-completo , se deduce que.
Ver también
Referencias
- Raymond Greenlaw, H. James Hoover, Fundamentos de la teoría de la computación: principios y práctica , Morgan Kaufmann, 1998, ISBN 1-55860-474-X , p. 45-51
- 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