Problema de función

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

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

Un algoritmo resuelve si por cada entrada tal que existe un satisfactorio , el algoritmo produce uno . ${\ Displaystyle P}$ ${\ Displaystyle x}$ ${\ Displaystyle y}$ ${\ Displaystyle (x, y) \ in R}$ ${\ Displaystyle y}$

Un problema de función bien conocido viene dado por el Problema de satisfacción 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:

En este caso, la relación viene dada por tuplas de fórmulas booleanas codificadas adecuadamente y asignaciones satisfactorias. Mientras que 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. ${\ 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 enteros , que solicita la lista de factores.