WikiDer > Проблема с обещанием - Википедия

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

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

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

Примеры

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

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

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

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

Обзоры

• Гольдрайх, Одед (2006). О проблемах с обещаниями (обзор). LNCS. 3895. С. 254–290. Дои:10.1007/11685654_12.
• Sahai, A .; Вадхан, С.П. (1997). «Полная обещающая проблема для статистического нулевого знания». FOCS 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.