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 pertenecerá a un subconjunto particular de todas las entradas posibles. [1] A diferencia de los problemas de decisión, las instancias de sí (las entradas para las cuales un algoritmo debe devolver sí ) y las instancias de no no agotan el conjunto de todas las entradas. Intuitivamente, se ha prometido al algoritmo que la entrada efectivamente pertenece a un conjunto de instancias de sí o no . Puede haber entradas que no sean ni sí ni no . Si se proporciona tal entrada a un algoritmo para resolver un problema de promesa, el algoritmo puede generar cualquier cosa y es posible que incluso no se detenga.
Un problema de decisión puede asociarse con un lenguaje , donde el problema es aceptar todas las entradas y rechazar todas las que no . Para un problema de promesa, hay dos lenguajes y , que deben ser disjuntos , lo que significa que todas las entradas deben aceptarse y todas las entradas 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 éste también es un problema de decisión y se dice que la promesa es trivial.
Muchos problemas naturales son en realidad problemas prometedores. Por ejemplo, considere el siguiente problema: Dado un gráfico acíclico dirigido , determine si el gráfico tiene una ruta de longitud 10. Las instancias de sí son gráficos acíclicos dirigidos con una ruta de longitud 10, mientras que las instancias no son gráficos acíclicos dirigidos sin ruta. de longitud 10. La promesa es el conjunto de grafos acíclicos dirigidos. En este ejemplo, la promesa es fácil de comprobar. En particular, es muy fácil comprobar si un gráfico determinado es cíclico. Sin embargo, la propiedad prometida podría resultar difícil de evaluar. Por ejemplo, considere el problema "Dado un gráfico hamiltoniano , determine si el gráfico 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 realizar en tiempo polinomial.
