Editing Promise problem

{{Short description|Type of computational problem}}
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.<ref>{{cite web | url = http://complexityzoo.net/Complexity_Zoo_Glossary#P | title = Promise problem | website = [[Complexity Zoo]] }}</ref> 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.

==Definition==

A decision problem can be associated with a [[formal language|language]] <math>L \subseteq \{0,1\}^*</math>, where the problem is to accept all inputs in <math>L</math> and reject all inputs not in <math>L</math>. For a promise problem, there are two languages, <math>L_{\text{YES}}</math> and <math>L_{\text{NO}}</math>, which must be [[Disjoint sets|disjoint]], which means <math>L_{\text{YES}} \cap L_{\text{NO}} = \varnothing</math>, such that all the inputs in <math>L_{\text{YES}}</math> are to be accepted and all inputs in <math>L_{\text{NO}}</math> are to be rejected. The set <math>L_{\text{YES}} \cup L_{\text{NO}}</math> is called the ''promise''. There are no requirements on the output if the input does not belong to the promise. If the promise equals <math>\{0,1\}^*</math>, then this is also a decision problem, and the promise is said to be trivial.

==Examples==
Many natural problems are actually promise problems. For instance, consider the following problem: Given a [[directed acyclic graph]], determine if the graph has a [[path (graph theory)|path]] of length 10. The ''yes'' instances are directed acyclic graphs with a path of length 10, whereas the ''no'' instances are directed acyclic graphs with no path of length 10. The promise is the set of directed acyclic graphs. In this example, the promise is easy to check. In particular, it is very easy to check if a given graph is cyclic. However, the promised property could be difficult to evaluate. For instance, consider the problem "Given a [[Hamiltonian graph]], determine if the graph has a [[cycle (graph theory)|cycle]] of size 4." Now the promise is [[NP-hard]] to evaluate, yet the promise problem is easy to solve since checking for cycles of size 4 can be done in polynomial time.

==See also==
* [[Computational problem]]
* [[Decision problem]]
* [[Optimization problem]]
* [[Search problem]]
* [[Counting problem (complexity)]]
* [[Function problem]]
*[[TFNP]]

==References==
{{reflist}}

===Surveys===
* {{cite book
|chapter-url=http://eccc.hpi-web.de/report/2005/018/
|chapter=On Promise Problems (a survey)
|title=Theoretical Computer Science: Essays in memory of Shimon Even
|series=[[Lecture Notes in Computer Science]]
|volume=3895
|year=2006
|doi=10.1007/11685654_12
|pages=254–290
|first=Oded
|last=Goldreich|isbn=978-3-540-32880-3
}}
* {{cite book
|doi=10.1109/SFCS.1997.646133
|citeseerx = 10.1.1.34.6920
|year=1997
|pages=448–457
|last1=Sahai
|first1=A.
|last2=Vadhan
|first2=S.P.
|chapter = A complete promise problem for statistical zero-knowledge
|title = Proceedings 38th Annual Symposium on Foundations of Computer Science
|isbn = 0-8186-8197-7
}}
* {{cite journal
|doi=10.1016/S0019-9958(84)80056-X
|title=The complexity of promise problems with applications to public-key cryptography
|journal=[[Information and Control]]
|volume=61
|issue=2
|pages=159–173
|year=1984
|last1=Even
|first1=Shimon
|first2=Alan L.
|last2=Selman | author2-link = Alan Selman
|first3=Yacov
|last3=Yacobi|doi-access=
}}

[[Category:Computational problems]]