Problema de función

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".

Un problema funcional se define mediante una relación sobre cadenas de un alfabeto arbitrario :${\estilo de visualización P}$ ${\estilo de visualización R}$ ${\estilo de visualización \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.${\estilo de visualización P}$${\estilo de visualización x}$${\estilo de visualización y}$${\displaystyle (x,y)\en R}$${\estilo de visualización y}$${\estilo de visualización 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.${\estilo de visualización y}$

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.${\estilo de visualización \varphi}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{i}\rightarrow \{{\text{VERDADERO}},{\text{FALSO}}\}}$${\estilo de visualización \varphi}$${\displaystyle {\text{VERDADERO}}}$

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.${\estilo de visualización R}$${\estilo de visualización \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.

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 .${\estilo de visualización L}$${\estilo de visualización x}$${\estilo de visualización y}$${\estilo de visualización (x,y)}$${\estilo de visualización x}$${\estilo de visualización L}$${\estilo de visualización y}$${\estilo de visualización x}$${\estilo de visualización 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.

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]}${\estilo de visualización \varphi}$$estilo de visualización x_{1}}$$estilo de visualización x_{1}}$$estilo de visualización x_{2}$$estilo de visualización x_{1}}$

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$Estilo de visualización: Pi__{R}$$Estilo de visualización: Pi__{S}$$Estilo de visualización: Pi__{R}$$Estilo de visualización: Pi__{S}$${\estilo de visualización f}$${\estilo de visualización g}$${\estilo de visualización x}$${\estilo de visualización R}$${\estilo de visualización y}$${\estilo de visualización S}$

• Si tiene una -solución, entonces tiene una -solución.${\estilo de visualización x}$${\estilo de visualización R}$${\estilo de visualización f(x)}$${\estilo de visualización S}$
• ${\displaystyle (f(x),y)\en S\implica (x,g(x,y))\en 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 .$Estilo de visualización: Pi__{R}$$Estilo de visualización: Pi__{R}$${\displaystyle \mathbf {P} =\mathbf {NP} }$${\displaystyle \mathbf {FP} =\mathbf {FNP} }$

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)}$${\estilo de visualización x}$${\estilo de visualización y}$${\displaystyle (x,y)\en R}$${\displaystyle \mathbf {NP} ={\textbf {co-NP}}}$

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

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Ayúdenos a mejorar este artículo introduciendo citas más precisas. ( Octubre de 2015 ) ( Aprenda cómo y cuándo eliminar este mensaje )