Editing Promise problem (section)

{{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.