Promise Problems
In computational complexity theory, it is usually implicitly assumed that any string in {0, 1}* represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}* represent valid instances, and one specifies a proper subset of {0, 1}* as the set of "valid instances". Computational problems of this type are called promise problems.
The following is an example of a (decision) promise problem:
- "Given a graph G, determine if every independent set in G has size at most 5, or G has an independent set of size at least 10."
Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.
Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. The valid instances are those in Lyes ∪ Lno. Lyes and Lno represent the instances whose answer is yes and no, respectively.
Promise problems play an important role in several areas of computational complexity, including hardness of approximation, property testing, and interactive proof systems.
Read more about this topic: Computational Problem
Famous quotes containing the words promise and/or problems:
“Martin Pawley: Do ya think maybe’s there’s a chance we still might find her?
Ethan Edwards: Injun’ll chase a thing ‘til he thinks he’s chased it enough. Then he quits. Same way when he runs. Seems like he never learns there’s such a thing as a critter that’ll just keep comin’ on. So we’ll find ‘em in the end. I promise ya. We’ll find ‘em, just as sure as the turnin’ of the earth.”
—Frank S. Nugent (1908–1965)
“...I have wanted to believe people could make their dreams come true ... that problems could be solved. However, this is a national illness. As Americans, we believe all problems can be solved, that all questions have answers.”
—Kristin Hunter (b. 1931)