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 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 de función${\displaystyle P}$se define por una relación${\displaystyle R}$sobre cadenas de un alfabeto arbitrario${\displaystyle \Sigma }$:

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

Tenga en cuenta que${\displaystyle R}$No tiene por qué ser una relación binaria funcional .

Un algoritmo resuelve${\displaystyle P}$si para cada entrada${\displaystyle x}$de tal manera que exista una${\displaystyle y}$satisfactorio${\displaystyle (x,y)\in R}$, el algoritmo produce uno de esos${\displaystyle y}$y si no existen tales${\displaystyle y}$, lo rechaza.

Un problema de función de promesa permite que el algoritmo haga cualquier cosa (por lo tanto, puede que no termine) si no existe tal${\displaystyle y}$existe.

Un problema funcional bien conocido es el problema de satisfacibilidad booleana funcional, o FSAT por sus siglas en inglés. Este problema, estrechamente relacionado con el problema de decisión SAT , puede formularse de la siguiente manera:

Dada una fórmula proposicional${\displaystyle \varphi }$con variables${\displaystyle x_{1},\ldots ,x_{n}}$encontrar una tarea${\displaystyle x_{i}\rightarrow \{{\text{VERDADERO}},{\text{FALSO}}\}}$de tal manera que${\displaystyle \varphi }$evalúa a${\displaystyle {\text{VERDADERO}}}$o decidir que no existe tal asignación.

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

Otros ejemplos destacables incluyen el problema del viajante , que pide la ruta que siguió el vendedor, y el problema de la factorización de números enteros , que pide la lista de factores.

Consideremos un problema de decisión arbitrario.${\displaystyle L}$en la clase NP . Por definición de NP , existe un sistema de certificados tal que cada instancia del problema${\displaystyle x}$que se responde 'sí' tiene un certificado de tamaño polinomial${\displaystyle y}$que sirve como prueba de la respuesta "sí" (y las instancias de problemas respondidas "no" no tienen tales certificados). Por lo tanto, el conjunto de estos pares${\displaystyle (x,y)}$forma una relación, que representa el problema de la función "dado${\displaystyle x}$en${\displaystyle L}$encontrar un certificado${\displaystyle y}$para${\displaystyle x}$". Este problema de función se denomina variante de función de${\displaystyle L}$; pertenece a la clase FNP .

Por el contrario, cada problema R en FNP induce un problema de decisión correspondiente (único): dado x , decidir si existe algún y tal que R ( x , y ) se cumple.

La clase FNP puede considerarse el análogo de la clase NP en el ámbito de las funciones , ya que las soluciones de los problemas FNP pueden verificarse de forma eficiente (es decir, en tiempo polinomial con respecto a la longitud de la entrada) , pero no necesariamente hallarse de forma eficiente . En cambio, la clase FP , que puede considerarse el análogo de la clase P en el ámbito de las funciones , consta de problemas de funciones cuyas soluciones pueden hallarse en tiempo polinomial.

Obsérvese que el problema FSAT introducido anteriormente puede resolverse utilizando solo un número polinomial de llamadas a una subrutina que decide el problema SAT : Un algoritmo puede primero preguntar si la fórmula${\displaystyle \varphi }$es satisfacible. Después de eso, el algoritmo puede fijar la variable.${\displaystyle x_{1}}$a VERDADERO y preguntar de nuevo. Si la fórmula resultante aún se puede satisfacer, el algoritmo continúa${\displaystyle x_{1}}$Se corrigió a VERDADERO y continúa corrigiéndose${\displaystyle x_{2}}$, de lo contrario decide que${\displaystyle x_{1}}$tiene que ser FALSO y continúa. Por lo tanto, FSAT es resoluble en tiempo polinomial usando un oráculo que decide SAT . En general, un problema en FNP se llama autorreducible si puede resolverse en tiempo polinomial usando un oráculo para su problema de decisión inducido. Cada variante de función de cada problema NP-completo es autorreducible. Hay varias nociones (ligeramente diferentes) de autorreducibilidad. ^{[ 1 ] [ 2 ] [ 3 ]}

Los problemas de función se pueden reducir de forma muy similar a los problemas de decisión: Dados los problemas de función${\displaystyle R}$y${\displaystyle S}$decimos que${\displaystyle R}$se reduce a${\displaystyle S}$si existen funciones computables en tiempo polinomial${\displaystyle f}$y${\displaystyle g}$de tal manera que para todos los casos${\displaystyle x}$de${\displaystyle R}$y posibles soluciones${\displaystyle y}$de${\displaystyle S}$, sostiene que

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

Por lo tanto, es posible definir problemas FNP-difíciles análogos a problemas NP-difíciles:

Un problema${\displaystyle R}$es FNP-difícil si cada problema en FNP se puede reducir a${\displaystyle R}$Un problema${\displaystyle R}$es FNP-completo si es FNP-difícil y está en FNP . El problema FSAT es un problema FNP-completo y, por lo tanto, por la autorreducción de FSAT, se cumple que${\displaystyle \mathbf {P} =\mathbf {NP} }$si y solo si${\displaystyle \mathbf {FP} =\mathbf {FNP} }$.

La relación${\displaystyle R(x,y)}$utilizado para definir problemas de función tiene el inconveniente de ser posiblemente incompleto: no todas las entradas${\displaystyle x}$necesariamente tiene una contraparte${\displaystyle y}$de tal manera que${\displaystyle (x,y)\in R}$Por lo tanto, la cuestión de la computabilidad de las salidas no está separada de la cuestión de su existencia. Para superar este problema, es conveniente considerar la restricción de los problemas de funciones a relaciones totales, lo que da 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 la existencia de una solución. Además, si TFNP contiene algún problema FNP-completo, se deduce que${\displaystyle \mathbf {NP} ={\textbf {co-NP}}}$.

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