Problema de función

Tipo de problema computacional

En la teoría de la complejidad computacional , un problema de función es un problema computacional en el que 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 . En los problemas de función, la salida no es simplemente "sí" o "no".

Definición formal

Un problema funcional se define mediante una relación sobre cadenas de un alfabeto arbitrario : ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle \Sigma }$

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$

Un algoritmo resuelve si para cada entrada tal que existe un satisfactorio , el algoritmo produce uno de ellos , y si no hay ninguno , lo rechaza. ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle y}$ ${\displaystyle y}$

A un problema de función de promesa se le permite hacer cualquier cosa (por lo tanto, no puede terminar) si tal cosa no existe. ${\displaystyle y}$

Ejemplos

Un problema de función bien conocido es el problema de satisfacibilidad booleana funcional, o FSAT, por sus siglas en inglés. El problema, que está estrechamente relacionado con el problema de decisión SAT , se puede formular de la siguiente manera:

Dada una fórmula booleana con variables , encuentre una asignación tal que evalúe o decida que no existe tal asignación. ${\displaystyle \varphi }$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}}$ ${\displaystyle \varphi }$ ${\displaystyle {\text{TRUE}}}$

En este caso, la relación se da mediante tuplas de fórmulas booleanas codificadas adecuadamente y asignaciones satisfactorias. Mientras que un algoritmo SAT, alimentado con una fórmula , solo necesita devolver "insatisfactorio" o "satisfactorio", un algoritmo FSAT necesita devolver alguna asignación satisfactoria en el último caso. ${\displaystyle R}$ ${\displaystyle \varphi }$

Otros ejemplos notables incluyen el problema del viajante , que pregunta por la ruta tomada por el vendedor, y el problema de factorización de números enteros , que pregunta por la lista de factores.

Relación con otras clases de complejidad

Consideremos un problema de decisión arbitrario en la clase NP . Según la definición de NP , cada instancia del problema que se responde "sí" tiene un certificado de tamaño polinomial que sirve como prueba de la respuesta "sí". Por lo tanto, el conjunto de estas tuplas forma una relación que representa el problema de función "dado en , encuentre un certificado para ". Este problema de función se denomina variante de función de ; pertenece a la clase FNP . ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle L}$

FNP puede considerarse como el análogo de la clase de función de NP , en el sentido de que las soluciones de los problemas FNP pueden verificarse de manera eficiente (es decir, en tiempo polinomial en términos de la longitud de la entrada) , pero no necesariamente encontrarse de manera eficiente . Por el contrario, la clase FP , que puede considerarse como el análogo de la clase de función de P , consiste en problemas de función cuyas soluciones pueden encontrarse en tiempo polinomial.

Autorreducibilidad

Obsérvese que el problema FSAT introducido anteriormente se puede resolver utilizando solo un número polinomial de llamadas a una subrutina que decide el problema SAT : Un algoritmo puede preguntar primero si la fórmula es satisfacible. Después de eso, el algoritmo puede fijar la variable en VERDADERO y preguntar de nuevo. Si la fórmula resultante todavía es satisfacible, el algoritmo se mantiene fija en VERDADERO y continúa fijando , 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 llama autorreducible si su variante de función se puede resolver en tiempo polinomial utilizando un oráculo que decide el problema original. Todo problema NP-completo es autorreducible. Se conjetura ^{[¿ por quién? ]} que el problema de factorización de enteros no es autorreducible, porque decidir si un entero es primo está en P (fácil), ^[1] mientras que se cree que el problema de factorización de enteros es difícil para una computadora clásica. Existen varias nociones (ligeramente diferentes) de autorreducibilidad. ^{[2] [3] [4]} ${\displaystyle \varphi }$ ${\displaystyle x_{1}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$

Reducciones y problemas completos

Los problemas de función se pueden reducir de forma muy similar a los problemas de decisión: Dados los problemas de función y decimos que se reduce a si existen funciones computables en tiempo polinomial y tales que para todas las instancias de y posibles soluciones de , se cumple que ${\displaystyle \Pi _{R}}$ ${\displaystyle \Pi _{S}}$ ${\displaystyle \Pi _{R}}$ ${\displaystyle \Pi _{S}}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle S}$

• Si tiene una -solución, entonces tiene una -solución. ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle f(x)}$ ${\displaystyle S}$
• ${\displaystyle (f(x),y)\in S\implies (x,g(x,y))\in R.}$

Por lo tanto, es posible definir problemas FNP-completos análogos al problema NP-completo:

Un problema es FNP-completo si cada problema en FNP puede reducirse a . La clase de complejidad de los problemas FNP-completos se denota por FNP-C o FNPC . Por lo tanto, el problema FSAT también es un problema FNP-completo y se cumple que si y solo si . ${\displaystyle \Pi _{R}}$ ${\displaystyle \Pi _{R}}$ ${\displaystyle \mathbf {P} =\mathbf {NP} }$ ${\displaystyle \mathbf {FP} =\mathbf {FNP} }$

Problemas de función total

La relación utilizada para definir problemas de función tiene el inconveniente de ser incompleta: no toda entrada tiene una contraparte tal que . Por lo tanto, la cuestión de la computabilidad de las demostraciones no está separada de la cuestión de su existencia. Para superar este problema es conveniente considerar la restricción de los problemas de función a relaciones totales que producen la clase TFNP como una subclase de FNP . Esta clase contiene problemas tales 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 cualquier problema FNP-completo se deduce que . ${\displaystyle R(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle \mathbf {NP} ={\textbf {co-NP}}}$

Véase también

• Problema de decisión
• Problema de búsqueda
• Problema de conteo (complejidad)
• Problema de optimización

Referencias

1. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 . JSTOR  3597229.
2. Ko, K. (1983). "Sobre la autorreducibilidad y la P-selectividad débil". Revista de Ciencias de la Computación y de Sistemas . 26 (2): 209–221. doi :10.1016/0022-0000(83)90013-2.
3. Schnorr, C. (1976). "Algoritmos óptimos para problemas autorreducibles". En S. Michaelson y R. Milner, editores, Actas del 3er Coloquio Internacional sobre Autómatas, Lenguajes y Programación : 322–337.
4. Selman, A. (1988). "Conjuntos autorreducibles naturales". Revista SIAM de Computación . 17 (5): 989–996. doi :10.1137/0217062.

• 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ág. 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", pp. 689–694