Promise Problems

Every computer science student learns decision problems: given an input, answer yes or no. Is this graph 3-colorable? Does this formula have a satisfying assignment? The input can be anything; the algorithm must handle all cases.

A promise problem adds one twist: the input comes with a guarantee. Some inputs are simply ruled out — they will never arrive. The algorithm only has to work correctly on inputs that satisfy the promise, and it can do whatever it likes on the others.

That sounds like a small relaxation. In practice it is a conceptual revolution. Problems that look identical under ordinary definitions split apart once a promise is imposed. Entire new complexity classes appear between the familiar ones. And some of the deepest conjectures in complexity theory — including the Unique Games Conjecture — are most naturally stated as promise problems.

The simplest example is Unique-SAT: the input is a Boolean formula promised to have either exactly one satisfying assignment or none at all. Formulas with two or more solutions are forbidden by the promise. Under that guarantee, does the algorithm's job get easier or harder? The answer is subtle and still not fully known — Unique-SAT is believed to be as hard as general SAT, but proving that is open.

The demo below lets you explore Unique-SAT hands-on. A small Boolean formula over variables $x_{1}$ $x_{2}$ $x_{3}$ is shown as clauses. The formula is promised to have either exactly one solution or none.

Toggle variables to build an assignment. The demo tells you which clauses are satisfied and whether the full formula is satisfied. Use Find all solutions to see every satisfying assignment — if the promise holds, you will find 0 or 1.

<p class="hint">{{hint}}</p>
<div id="formula"></div>
<div id="controls"></div>
<div class="status" id="status">{{toggle_prompt}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="findAll" type="button">{{btn_find_all}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="results"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#formula { display: flex; flex-direction: column; gap: 6px; margin-bottom: .8rem; }
.clause { display: flex; align-items: center; gap: 6px; font: 600 15px ui-monospace, monospace;
          padding: 6px 10px; border-radius: 8px; background: #f0f3f6; border: 1.5px solid #d4dde6;
          transition: background .2s, border-color .2s; }
.clause.sat { background: #d4f0de; border-color: #5baa76; }
.clause.unsat { background: #fde6e6; border-color: #d16060; }
.clause .lbl { font-size: .75rem; font-weight: 400; color: #888; width: 48px; flex-shrink: 0; }
.lit { color: #1d3557; }
.lit.neg { color: #6d4c41; }
.lit.true { color: #1a7a45; }
.lit.false { color: #b71c1c; }
.op { color: #888; font-weight: 400; margin: 0 2px; }
#controls { display: flex; flex-wrap: wrap; gap: 10px; margin-bottom: .8rem; }
.var-btn { display: flex; flex-direction: column; align-items: center; gap: 3px; cursor: pointer;
           padding: 8px 14px; border-radius: 10px; border: 1.5px solid #adb1b8;
           background: #e8ecf0; font: 700 15px ui-monospace, monospace; user-select: none;
           transition: all .15s; min-width: 64px; }
.var-btn .val-label { font-size: .72rem; font-weight: 600; letter-spacing: .04em; }
.var-btn.true { background: #1d3557; color: #fff; border-color: #1d3557; }
.var-btn.true .val-label { color: #90caf9; }
.var-btn.false .val-label { color: #888; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#results { font-size: .85rem; line-height: 1.6; color: #333; }
#results .sol { font-family: ui-monospace, monospace; background: #eef6ee;
                border-left: 3px solid #5baa76; padding: 3px 8px; border-radius: 4px; margin: 2px 0; }

// Code not found

Notice: checking an assignment (does it satisfy all clauses?) is instant regardless of the promise. Finding the unique solution without the promise means searching $2^{n}$ assignments; with the promise a solver can sometimes prune much earlier, because it knows a second solution cannot exist — the promise changes what the search space looks like.

Why do complexity theorists care so much about promises? Because they are the natural language for problems that have no clean decision version.

Unique-SAT and the class UP

The class UP (Unambiguous Polynomial time) contains decision problems solvable in polynomial time by a nondeterministic machine that has at most one accepting path on yes-instances. Unique-SAT is the canonical UP-complete problem under promise reductions. Whether UP = NP is open — it would follow from P = NP, but the converse is unknown.

Gap problems and hardness of approximation

Many approximation lower bounds are phrased as promise problems called gap problems. Gap-SAT(c, s) promises: either at least fraction c of the clauses are satisfiable, or at most fraction s are. The PCP theorem (proved by Arora, Lund, Motwani, Sudan, Szegedy in 1992) is equivalent to saying Gap-SAT(1, 7/8) is NP-hard — the promise collapses the gap between the easy and hard cases to a single threshold.

The Unique Games Conjecture

Proposed by Subhash Khot in 2002, the Unique Games Conjecture (UGC) is a promise problem at its core: given a system of linear equations mod q where each variable appears in exactly two equations (a unique game), distinguish the case where almost all equations are satisfiable from the case where few are. The UGC asserts this promise problem is NP-hard, and if true it would explain the tight approximation ratios for Max-Cut, Vertex Cover, and dozens of other problems. The UGC remains open as of 2025.

Quantum and beyond

The promise structure is essential in quantum complexity too. BQP vs QMA separations often rely on problems whose hardness is only well-defined under a promise (e.g., the local Hamiltonian problem promises the ground state energy is either below a or above b, with a gap). Without the gap promise the problem is not even well-defined computationally.

See also: P vs NP and the Unique Games Conjecture.

The promise framework is not an academic curiosity — it structures some of the most important open questions and practical tools in computer science:

• Hardness of approximation: almost every inapproximability result is a promise problem in disguise. The gap between the "easy" and "hard" instances is the promise, and the PCP theorem is the machine that manufactures those gaps.
• Cryptography: many cryptographic hardness assumptions (e.g., Learning With Errors, Shortest Vector Problem) are promise problems — they promise the input is either a structured sample or uniformly random, and no efficient algorithm can tell which.
• Quantum computing: the local Hamiltonian problem (QMA-complete, proved by Kitaev in 1999) is a promise problem — the promised gap between energy levels is what makes the problem well-posed as a complexity question.
• Algorithm design: knowing inputs satisfy a promise (e.g., a graph is promised to have a unique perfect matching) lets designers build faster, simpler algorithms that would be wrong on the full input space.
• Derandomization: the class promise-BPP captures what randomized algorithms can solve when the input distribution respects a promise. Showing promise-BPP = promise-P is a key step in derandomization research.

In short, wherever you see a "gap," a "unique," or an "either/or" in a complexity statement, you are looking at a promise problem.

A promise problem begins with a disarmingly simple idea: just rule out the inconvenient inputs. Yet that single move restructures the entire landscape of computational complexity. Problems that were indistinguishable become separable. New classes appear between P and NP. And the hardest conjectures of our era — the Unique Games Conjecture, the PCP theorem's tight thresholds — are all promise problems at heart.

The next time you read "distinguish case A from case B" in a complexity paper, you are reading a promise. The algorithm is not asked to handle everything — only to tell apart two specific worlds. That restriction is not a weakness. It is the lens that brings the structure of computation into focus.

Explore related ideas in P vs NP and the Unique Games Conjecture.