In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, a promise problem is a generalization of a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
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.
Formal definition
A decision problem can be associated with a
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
, where the problem is to accept all inputs in
and reject all inputs not in
. For a promise problem, there are two languages,
and
, which must be
disjoint, which means
, such that all the inputs in
are to be accepted and all inputs in
are to be rejected. The set
is called the ''promise''. There are no requirements on the output if the input does not belong to the promise. If the promise equals
, 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
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
, determine if the graph has a
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
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
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
, determine if the graph has a
cycle of size 4." Now the promise is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
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
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
*
Decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
*
Optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
*
Search problem
In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If ''R'' is a binary relation such that field(''R'') ⊆ Γ+ and ''T'' is a Turing machine, then '' ...
*
Counting problem (complexity)
In computational complexity theory and computability theory, a counting problem is a type of computational problem. If ''R'' is a search problem then
:c_R(x)=\vert\\vert \,
is the corresponding counting function and
:\#R=\
denotes the corre ...
*
Function problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...
*
TFNP In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and t ...
References
Surveys
*
*
* {{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=free
Computational problems