A promise problem consists of disjoint sets of YES and NO instances. An algorithm or verifier must obey its correctness guarantees only on their union. Energy problems with separated thresholds are naturally promise problems because intermediate-energy instances require no prescribed answer.
Articles by others on the same topic
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 \).