Оглавление
Проблема с обещаниями
-
Определение задачи обещания
- Задача обещания обобщает задачу принятия решения, где входные данные могут не принадлежать только да или нет.
- Алгоритм получает обещание, что входные данные относятся к набору экземпляров да или нет.
-
Формальное определение
- Проблема принятия решения может быть сформулирована на языке
- L
- ⊆
- {
- 0
- ,
- 1
- }
- ∗
- {\displaystyle L\subseteq \{0,1\}^{*}}
- .
- Для задачи обещания существуют языки
- да
- {\displaystyle L_ _BOS_\текст{ДА}}}
- и
- НЕТ
- {\displaystyle L_{\текст{НЕТ}}}
- , которые не пересекаются.
- Обещание – это объединение
- ∪
-
Примеры задач обещания
- Задача определения наличия пути длиной 10 в направленном ациклическом графе является примером задачи обещания.
- Проверка наличия цикла размером 4 в гамильтоновом графе является примером задачи обещания, которую легко решить, но сложно вычислить с помощью NP-алгоритма.
-
Рекомендации
- Статья также упоминает другие вычислительные задачи, такие как проблема решения, задача оптимизации, поиск, подсчет и функциональные проблемы.
- В конце статьи приведены ссылки на опросы.
Полный текст статьи: