The "Promise Problem" refers to a class of decision problems in computational complexity that involves promises — that is, certain guarantees about the input. Specifically, it's related to a decision problem where the input is guaranteed to satisfy one of several conditions (or "promises"), but not necessarily all. In more formal terms, a promise problem can be defined as a pair of languages \( L_1 \) and \( L_2 \).
Articles by others on the same topic
There are currently no matching articles.