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

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

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

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

Примеры

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

См. также

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

Ссылки

Опросы

• Гольдрайх, Одед (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 .