Проблема с обещанием

Тип вычислительной задачи

В теории сложности вычислений проблема обещания — это обобщение проблемы принятия решения , где входные данные обещают принадлежать определенному подмножеству всех возможных входных данных. ^[1] В отличие от задач принятия решений, экземпляры «да» (входные данные, для которых алгоритм должен возвращать « да ») и экземпляры « нет » не исчерпывают набор всех входных данных. Интуитивно алгоритму было обещано , что входные данные действительно принадлежат набору экземпляров «да» или «нет ». Могут быть входные данные, которые не являются ни да , ни нет . Если такие входные данные подаются в алгоритм решения задачи обещания, алгоритму разрешено выводить что угодно, и он может даже не останавливаться.

Формальное определение

Проблема принятия решения может быть связана с языком , где проблема состоит в том, чтобы принять все входные данные и отклонить все входные данные, не входящие в него . Для задачи обещания существуют два языка и , которые должны быть непересекающимися , что означает , что все входные данные в должны быть приняты, а все входные данные в должны быть отклонены. Набор называется обещанием . Нет никаких требований к выходным данным, если входные данные не принадлежат обещанию. Если обещание равно , то это тоже проблема решения, и обещание называется тривиальным. ${\displaystyle L\subseteq \{0,1\}^{*}}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L_{\text{YES}}}$ ${\displaystyle L_{\text{NO}}}$ ${\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing }$ ${\displaystyle L_{\text{YES}}}$ ${\displaystyle L_{\text{NO}}}$ ${\displaystyle L_{\text{YES}}\cup L_{\text{NO}}}$ ${\displaystyle \{0,1\}^{*}}$

Примеры

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

Смотрите также

• Вычислительная задача
• Проблема решения
• Проблема оптимизации
• Проблема с поиском
• Задача на счет (сложность)
• Функциональная проблема
• ТФНП

Рекомендации

1. «Проблема с обещаниями» . Зоопарк «Комплекс» .

Опросы

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