В теории вычислительной сложности задача обещания является обобщением задачи принятия решения , в которой входные данные обещаны принадлежать определенному подмножеству всех возможных входных данных. [1] В отличие от задач принятия решения, примеры «да» (входные данные, для которых алгоритм должен возвращать «да» ) и примеры «нет» не исчерпывают множество всех входных данных. Интуитивно, алгоритму было обещано , что входные данные действительно принадлежат множеству экземпляров «да» или экземпляров « нет» . Могут быть входные данные, которые не являются ни «да» , ни «нет» . Если такие входные данные даны алгоритму для решения задачи обещания, алгоритму разрешено выводить что угодно, и он может даже не останавливаться.
Проблема принятия решения может быть связана с языком , где проблема состоит в том, чтобы принять все входы в и отклонить все входы, не входящие в . Для проблемы обещания есть два языка, и , которые должны быть непересекающимися , что означает , таким образом, что все входы в должны быть приняты , а все входы в должны быть отклонены. Набор называется обещанием . Нет никаких требований к выходу, если вход не принадлежит обещанию. Если обещание равно , то это также проблема принятия решения, и обещание называется тривиальным.
Многие естественные проблемы на самом деле являются проблемами обещаний. Например, рассмотрим следующую задачу: задан направленный ациклический граф , определить, имеет ли граф путь длины 10. Экземпляры «да» являются направленными ациклическими графами с путем длины 10, тогда как экземпляры «нет» являются направленными ациклическими графами без пути длины 10. Обещание — это множество направленных ациклических графов. В этом примере обещание легко проверить. В частности, очень легко проверить, является ли заданный граф циклическим. Однако обещанное свойство может быть трудно оценить. Например, рассмотрим задачу «Дан гамильтонов граф , определить, имеет ли граф цикл размера 4». Теперь обещание NP-трудно оценить, однако проблему обещания легко решить, поскольку проверку циклов размера 4 можно выполнить за полиномиальное время.
