En la teoría de la complejidad computacional , un problema de promesa es una generalización de un problema de decisión donde se promete que la entrada pertenecerá a un subconjunto particular de todas las entradas posibles. [1] A diferencia de los problemas de decisión, los yes casos (las entradas para los cuales un algoritmo debe devolver sí ) y no hay casos no agotan el conjunto de todas las entradas. Intuitivamente, se ha prometido al algoritmo que la entrada pertenece al conjunto de instancias yes o no instancias. Puede haber entradas que no sean ni sí ni no. Si se le da una entrada de este tipo a un algoritmo para resolver un problema de promesa, el algoritmo puede generar cualquier cosa, e incluso puede que no se detenga.
Definicion formal
Un problema de decisión puede estar asociado con un idioma. , 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 idiomas, y , que debe ser disjunto , lo que significa, de modo que todas las entradas en deben ser aceptadas y todas las entradas en deben ser rechazados. El conjuntose llama la promesa . No hay requisitos en la salida si la entrada no pertenece a la promesa. Si la promesa es igual, entonces esto también es un problema de decisión, y se dice que la promesa es trivial.
Ejemplos de
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 sí son gráficas acíclicas dirigidas con una ruta de longitud 10, mientras que las instancias no son gráficas acíclicas dirigidas sin ruta. de longitud 10. La promesa es el conjunto de gráficos acíclicos dirigidos. En este ejemplo, la promesa es fácil de verificar. En particular, es muy fácil comprobar si un gráfico determinado es cíclico. Sin embargo, la propiedad prometida podría ser difícil de evaluar. Por ejemplo, considere el problema "Dada una gráfica hamiltoniana , determine si la gráfica tiene un ciclo de tamaño 4". Ahora la promesa es NP-difícil de evaluar, sin embargo, 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.
Ver también
Referencias
Encuestas
- Goldreich, Oded (2006). On Promise Problems (una encuesta) . LNCS . 3895 . págs. 254–290. doi : 10.1007 / 11685654_12 . Parámetro desconocido
|book-title=
ignorado ( ayuda ) - Sahai, A .; Vadhan, SP (1997). "Un problema de promesa completa para el conocimiento cero estadístico". FOCS 1997 . págs. 448–457. CiteSeerX 10.1.1.34.6920 . doi : 10.1109 / SFCS.1997.646133 .
- Incluso, Shimon; Selman, Alan L .; Yacobi, Yacov (1984). "La complejidad de los problemas de promesa con aplicaciones a la criptografía de clave pública" . Información y control . 61 (2): 159-173. doi : 10.1016 / S0019-9958 (84) 80056-X .