En la teoría de la complejidad computacional , un problema de promesa es una generalización de un problema de decisión en el que se promete que la entrada pertenece a un subconjunto particular de todas las entradas posibles. [1] A diferencia de los problemas de decisión, las instancias sí (las entradas para las que un algoritmo debe devolver sí ) y las instancias no no agotan el conjunto de todas las entradas. Intuitivamente, se le ha prometido al algoritmo que la entrada pertenece de hecho al conjunto de instancias sí o instancias no . Puede haber entradas que no sean ni sí ni no . Si se proporciona dicha entrada a un algoritmo para resolver un problema de promesa, se permite que el algoritmo genere cualquier cosa, e incluso puede no detenerse.
Un problema de decisión puede estar asociado con un lenguaje , donde el problema es aceptar todas las entradas en y rechazar todas las entradas que no están en . Para un problema de promesa, hay dos lenguajes, y , que deben ser disjuntos , lo que significa , de modo que todas las entradas en deben aceptarse y todas las entradas en deben rechazarse. El conjunto se llama promesa . No hay requisitos sobre la salida si la entrada no pertenece a la promesa. Si la promesa es igual a , entonces este también es un problema de decisión, y se dice que la promesa es trivial.
Muchos problemas naturales son en realidad problemas de promesa. Por ejemplo, considere el siguiente problema: Dado un grafo acíclico dirigido , determine si el grafo tiene un camino de longitud 10. Las instancias sí son grafos acíclicos dirigidos con un camino de longitud 10, mientras que las instancias no son grafos acíclicos dirigidos sin camino de longitud 10. La promesa es el conjunto de grafos acíclicos dirigidos. En este ejemplo, la promesa es fácil de verificar. En particular, es muy fácil verificar si un grafo dado es cíclico. Sin embargo, la propiedad prometida podría ser difícil de evaluar. Por ejemplo, considere el problema "Dado un grafo hamiltoniano , determine si el grafo tiene un ciclo de tamaño 4". Ahora bien, la promesa es NP-difícil de evaluar, pero el problema de la promesa es fácil de resolver ya que la verificación de ciclos de tamaño 4 se puede hacer en tiempo polinomial.
