Введение
Тип вычислительной проблемы
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.
В теории вычислительной сложности проблема с обещанием — это обобщение задачи о принятии решения, в которой гарантируется, что входные данные принадлежат к определенному подмножеству всех возможных входных данных. В отличие от задач о принятии решения, положительные (входные данные, для которых алгоритм должен вернуть положительный ответ) и отрицательные экземпляры не составляют весь набор возможных входных данных. Интуитивно, алгоритму гарантируется, что входные данные действительно принадлежат либо к множеству положительных, либо к множеству отрицательных экземпляров. Могут существовать входные данные, которые не являются ни положительными, ни отрицательными. Если такие входные данные подаются алгоритму для решения проблемы с обещанием, алгоритм может выдать любой результат и даже может не завершиться.
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.
Формальное определение
Проблема принятия решения может быть связана с языком, где задача состоит в принятии всех входных данных из этого языка и отклонении всех входных данных, не принадлежащих ему. Для задачи с обещанием определяются два языка, L₁ и L₂, которые должны быть непересекающимися, то есть L₁ ∩ L₂ = ∅, таким образом, что все входные данные из L₁ должны быть приняты, а все входные данные из L₂ – отклонены. Множество L₁ называется обещанием. Нет требований к выходным данным, если входные данные не принадлежат обещанию. Если обещание равно пустому множеству, то это также проблема принятия решения, и такое обещание считается тривиальным.
Примеры
Многие естественные задачи на самом деле являются задачами с обещанием. Например, рассмотрим следующую задачу: дан ориентированный ациклический граф, определить, существует ли в графе путь длиной 10. Положительные экземпляры – это ориентированные ациклические графы, содержащие путь длиной 10, а отрицательные экземпляры – ориентированные ациклические графы, не содержащие пути длиной 10. Обещанием является множество ориентированных ациклических графов. В этом примере обещание легко проверить. В частности, очень легко проверить, является ли данный граф циклическим. Однако, проверка обещанного свойства может быть сложной. Например, рассмотрим задачу: "Дан гамильтонов граф, определить, содержит ли граф цикл размера 4". Теперь проверка обещания является NP-трудной задачей, однако сама задача с обещанием легко решается, поскольку проверка на наличие циклов размера 4 может быть выполнена за полиномиальное время.