В теории сложности вычислений , проблема обещания является обобщением задачи принятия решения , где вход обещанная принадлежать к определенному подмножеству всех возможных входов. [1] В отличие от задач решения, экземпляры yes (входные данные, для которых алгоритм должен возвращать yes ) и экземпляры no не исчерпывают набор всех входных данных. Интуитивно алгоритму было обещано, что ввод действительно принадлежит набору экземпляров « да» или « нет» . Могут быть входы, которые не являются ни да, ни нет. Если такой вход предоставляется алгоритму для решения проблемы обещания, алгоритму разрешается выводить что угодно, и он может даже не останавливаться.
Формальное определение
Проблема принятия решения может быть связана с языком , где проблема состоит в том, чтобы принять все входные данные в и отклонить все входы, не входящие в . Для задачи с обещанием есть два языка, а также , который должен быть непересекающимся , что означает, так что все входы в должны быть приняты, и все входы в подлежат отклонению. Наборназывается обещанием . Нет требований к выходу, если вход не принадлежит обещанию. Если обещание равно, то это тоже проблема принятия решения, и обещание считается тривиальным.
Примеры
Многие естественные проблемы на самом деле являются проблемами обещаний. Например, рассмотрим следующую проблему: для данного ориентированного ациклического графа определить, имеет ли граф путь длины 10. Экземпляры yes - это направленные ациклические графы с путем длиной 10, тогда как экземпляры no - это ориентированные ациклические графы без пути. длины 10. Обещание представляет собой набор ориентированных ациклических графов. В этом примере обещание легко проверить. В частности, очень легко проверить, является ли данный граф циклическим. Однако обетованное имущество бывает сложно оценить. Например, рассмотрим задачу «Для гамильтонова графа определите, имеет ли граф цикл размера 4». Теперь обещание NP-сложно оценить, но проблему обещания легко решить, поскольку проверка циклов размера 4 может выполняться за полиномиальное время.
Смотрите также
Рекомендации
Обзоры
- Гольдрайх, Одед (2006). О проблемах обещаний (обзор) . LNCS . 3895 . С. 254–290. DOI : 10.1007 / 11685654_12 .
- Sahai, A .; Вадхан, СП (1997). «Полная обещающая проблема для статистического нулевого знания». FOCS 1997 . С. 448–457. CiteSeerX 10.1.1.34.6920 . DOI : 10.1109 / SFCS.1997.646133 .
- Даже, Шимон; Селман, Алан Л .; Якоби, Яков (1984). «Сложность обещаний проблем с приложениями к криптографии с открытым ключом» . Информация и контроль . 61 (2): 159–173. DOI : 10.1016 / S0019-9958 (84) 80056-X .