Promise problem

Key takeaways

Promise problem belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Promise problem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Promise problem from memory before moving on to harder problems.

Reference excerpt

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 the 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 language L ⊆ { 0 , 1 } ∗ {\displaystyle L\subseteq \{0,1\}^{*}} , where the problem is to accept all inputs in L {\displaystyle L} and reject all inputs not in L {\displaystyle L} . For a promise problem, there are two languages, L YES {\displaystyle L_{\text{YES}}} and L NO {\displaystyle L_{\text{NO}}} , which must be disjoint, which means L YES ∩ L NO = ∅ {\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing } , such that all the inputs in L YES {\displaystyle L_{\text{YES}}} are to be accepted and all inputs in L NO {\displaystyle L_{\text{NO}}} are to be rejected. The set L YES ∪ L NO {\displaystyle L_{\text{YES}}\cup L_{\text{NO}}} is called the promise. There are no requirements on the output if the input does not belong to the promise. If the promise equals { 0 , 1 } ∗ {\displaystyle \{0,1\}^{*}} , 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 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 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

Surveys Goldreich, Oded (2006). "On Promise Problems (a survey)". Theoretical Computer Science: Essays in memory of Shimon Even. Lecture Notes in Computer Science. Vol. 3895. pp. 254–290. doi:10.1007/11685654_12. ISBN 978-3-540-32880-3. Sahai, A.; Vadhan, S.P. (1997). "A complete promise problem for statistical zero-knowledge". Proceedings 38th Annual Symposium on Foundations of Computer Science. pp. 448–457. CiteSeerX 10.1.1.34.6920. doi:10.1109/SFCS.1997.646133. ISBN 0-8186-8197-7. {{cite book}}: Cite uses deprecated parameter |citeseerx= (help) Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984). "The complexity of promise problems with applications to public-key cryptography". Information and Control. 61 (2): 159–173. doi:10.1016/S0019-9958(84)80056-X.

Worked examples

Example 1 — a first encounter with Promise problem

Start with the simplest possible case. Write down what Promise problem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Promise problem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Promise problem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Promise problem

In research: Promise problem appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Promise problem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Promise problem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational problems, so understanding it makes those chapters shorter.
In everyday life: Look for Promise problem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Promise problem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Promise problem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Promise problem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Promise problem in simple terms?

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 no…

Why does Promise problem matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Promise problem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Promise problem.