Motivation
A decision algorithm says whether a satisfying assignment exists; a student often wants the assignment itself. For SAT, these tasks are closely linked: asking whether a partially fixed formula remains satisfiable reveals one witness bit at a time. The same idea works for every polynomially verifiable relation, provided the witness length is polynomially bounded.
Combining yes- and no-conditions leads to another useful class. A formula can have at least one satisfying assignment, and it can fail to have two distinct ones. The first claim has an NP witness, while the second is a coNP claim. Keeping both roles explicit avoids mistaking “exactly one” for an ordinary NP certificate.
Definitions
Definition 2.4.1
(Polynomially balanced NP relation and its decision language)
A polynomially balanced NP relation is a deterministic polynomial-time predicate with a fixed polynomial such that valid witnesses may be taken to have exactly bits. Shorter representations can be encoded and padded with a length marker, with the verifier checking the encoding and ignoring padding. Its decision language is
A search procedure must output a valid on every ; on inputs with no witness we will explicitly state whether it must report failure or may return an arbitrary string.
Definition 2.4.2
(Prefix language)
The prefix language of is
In words, when the partial witness can still be completed to a valid one.
The prefix language is in NP: the remaining suffix is a polynomial-length witness, and the verifier checks the length and . Invalid overlong prefixes are rejected. We use SAT's polynomial-time many-one completeness for NP from the companion Cook–Levin notes.
Theorem
Theorem 2.4.3
(Search by prefix decision)
For every polynomially balanced NP relation, a deterministic polynomial-time machine with a SAT oracle can output a valid witness when one exists and report failure otherwise. It uses at most oracle queries after polynomial-time reductions from prefix questions to SAT.
The theorem does not assume that an arbitrary decision language can itself answer every prefix question. The oracle solves the prefix language, using its NP reduction to SAT. That distinction matters when generalizing the familiar SAT procedure to other relations.
Proof
Proof
(Fixing the witness one bit at a time)
First query whether , where is the empty prefix. If not, no witness exists and the machine reports failure. Otherwise maintain a prefix that has at least one valid completion. If , query whether . When the answer is yes, append ; when it is no, append .
The invariant is preserved. If a valid completion begins with , the first branch chooses such a prefix. If none begins with , the old prefix still has some valid completion and its next bit must be . At length the only possible suffix is empty, so the invariant says . The machine makes one initial query and at most one per witness bit. Constructing each prefix query and reducing it to SAT takes polynomial time.
The output is the lexicographically smallest valid witness under the order : at the first position where another valid witness differs, the algorithm could not have chosen if a valid completion with existed. The lexicographic property is a useful consequence of the invariant, not an extra oracle assumption.
Proof X-ray
The invariant behind a search bit
A “no” answer for is useful only because the current prefix was already known to have a completion. Without that invariant, choosing after a failed zero-branch could lead to another impossible prefix. The initial existence query establishes the invariant, and each later query preserves it. The two branches also play different roles: a “yes” answer needs no further check because the completion it promises extends , while a “no” answer is converted into information about only through the invariant. Finally, the machine asks about and not about , since a decision oracle for need not answer questions about a partially fixed witness.
Worked examples
Worked example 2.4.4
(Recovering a satisfying assignment)
Let and use the variable order . The initial query confirms satisfiability. Fixing leaves a satisfying completion, so choose zero. With that prefix, fixing is unsatisfiable, so choose one. The output satisfies and is lexicographically smallest; the other satisfying assignment is .
Concept lensCombinatorial
Search as a walk down a binary tree
Arrange the strings of length as the leaves of a binary tree in which node has children and . Mark a node when , that is, when some valid witness lies among the leaves below it. The search starts at the root, which the initial query tests, and moves to if that child is marked and to otherwise. It ends at the leftmost marked leaf, the lexicographically smallest valid witness.
Worked example 2.4.5
(A non-SAT relation)
Let check that a bit string encodes an independent set of exactly vertices in a graph , with included in the input and an agreed polynomial encoding. The prefix question asks whether a partial encoding can be completed to such a set. It is in NP because the remaining bits complete the certificate. A SAT oracle can decide each prefix question after a polynomial reduction, so the same search procedure constructs a set if one exists. It need not enumerate all vertex subsets.
The next example shows what goes wrong if the invariant is not established first.
Counterexample mode
Skipping the initial existence query
Claim: after a “no” answer for the prefix , the bit is always the right choice. Take with the single variable . Both values fail: and . A procedure that skips the initial existence check tests , receives “no”, and automatically outputs , which does not satisfy . The claim is false because the empty prefix had no completion. Repair: query first. Here the answer is “no”, so the machine reports failure, which is correct.
A consequence of
Theorem 2.4.6
(Decision and polynomial witness search)
If , every polynomially balanced NP relation has a deterministic polynomial-time search procedure that reports failure exactly when no witness exists. Conversely, if every such relation has a deterministic polynomial-time procedure that outputs a valid witness whenever one exists, even with arbitrary output on no-instances, then .
Proof
(Replacing the oracle; deciding NP by a witness search)
For the first direction, , so the hypothesis gives a deterministic polynomial-time algorithm for each prefix question. Replace the oracle calls in the previous proof by this algorithm. There are polynomially many calls, so the complete search remains polynomial time.
For the converse, take any language and a polynomially balanced verifier for it. Run the assumed search procedure, then check the returned string's length and evaluate . Accept if and only if the check passes. On a yes-instance the procedure supplies a valid witness; on a no-instance no string can pass the verifier, regardless of what the procedure returns. The resulting deterministic polynomial-time decider shows . Since , equality follows.
The converse requires a uniform polynomial-time search procedure that halts on every input, including no-instances. A method that can run forever when no witness exists does not yield the stated polynomial-time decider.
Combining an NP condition with a coNP condition
Definition 2.4.7
(The class DP)
A language in DP asks for an NP condition to hold while a possibly different NP condition fails.
The letters name a complexity class here; they do not mean dynamic programming. Both NP and coNP are contained in DP: for NP take to be the empty language, and for coNP take to be the universal language. These containments alone do not establish that either inclusion is strict.
Theorem 2.4.8
(SAT–UNSAT is DP-complete)
The language of pairs for which is satisfiable and is unsatisfiable is DP-complete under deterministic polynomial-time many-one reductions.
Proof
(Pairing two NP reductions)
Membership follows directly from the definition: the first component is in SAT and the second is outside SAT. For hardness, let with . Use SAT completeness to compute formulas and in polynomial time such that iff is satisfiable, and iff is satisfiable. The single map satisfies
Both reductions are deterministic and polynomial, so their pairing is a valid many-one reduction. Invalid encodings can be mapped to fixed no-instances; they do not change completeness.
Worked example 2.4.9
(Two formulas, two different roles)
Take and . The first is satisfiable and the second is unsatisfiable, so is in SAT–UNSAT. Swapping them gives a no-instance: the new first formula has no witness. Showing an assignment for the first formula alone would not certify that the second formula is unsatisfiable.
Exactly one satisfying assignment
Definition 2.4.10
(EXACT-ONE-SAT)
EXACT-ONE-SAT is the language of formulas with exactly one satisfying assignment over a fixed explicit variable list.
It lies in DP. The condition “at least one” is SAT. The condition “at least two” is also in NP: a certificate consists of two assignments, both satisfying the formula and differing on at least one listed variable. Thus
Both tests can be implemented by SAT queries: the second uses two copies of the variables, two copies of the formula and a polynomial-size constraint that the assignments differ. Therefore EXACT-ONE-SAT is also in .
This is a total language: formulas with zero, one or more than one satisfying assignments all have specified yes/no answers. A promise problem in which the input is guaranteed to have at most one solution has a different correctness contract. We do not infer deterministic DP-completeness of EXACT-ONE-SAT from its membership in DP, nor do we claim that a polynomial-time algorithm for it is known.
Worked example 2.4.11
(Zero, one and two assignments)
With the single listed variable , the formula has zero assignments, has exactly one, and has two. Only the middle formula is in EXACT-ONE-SAT. Its witness certifies the “at least one” part; establishing that there is no second assignment is the separate coNP side.
Common mistakes
Common mistake
(A decision oracle is not a prefix oracle)
A decision oracle for the original yes/no language is not automatically a prefix oracle for an arbitrary witness relation. The uniform NP reduction for is what makes the general search proof work.
Common mistake
(One satisfying assignment does not prove uniqueness)
A single valid assignment certifies only the “at least one” side of EXACT-ONE-SAT. It does not rule out a distinct second assignment, and membership in DP does not by itself prove DP-completeness.
Common mistake
(A search that may loop on no-instances)
A search method allowed to run forever on no-instances is not a deterministic polynomial-time algorithm in the equivalence theorem, and it cannot be turned into a decider for .
Summary
Polynomially bounded witnesses can be recovered by asking whether successive prefixes admit a completion. If P equals NP, the prefix questions can be decided without an oracle, and conversely uniform polynomial witness search would decide every NP language. The class DP makes a conjunction of an NP condition and the complement of an NP condition explicit.
Exercises
Quick check
(Why is in NP?)
Describe the certificate and what the verifier checks.
Solution · Answer
A suffix of length is a polynomial-size certificate. The verifier checks the prefix length and evaluates .
Quick check
(What invariant justifies choosing bit one after the query for prefix fails?)
Recall what is known about before the query.
Solution · Answer
The current prefix is known to have some valid completion. If none starts with zero, at least one starts with one.
Quick check
(How many SAT-oracle queries does the general search algorithm use at most?)
Count the initial query separately from the per-bit queries.
Solution · Answer
At most : one existence query and one query for each witness bit.
Quick check
(For , find the lexicographically smallest satisfying assignment.)
Examine assignments in the order .
Solution · Answer
With , the assignments are examined in order ; fails, and the first satisfying assignment is .
Quick check
(In the converse direction, why can arbitrary output on no-instances still be rejected correctly?)
Ask whether any string can be a valid witness for a no-instance.
Solution · Answer
On a no-instance no string is a valid witness, so the deterministic length and verifier check rejects whatever the search procedure outputs.
Quick check
(Show that every NP language lies in DP.)
Write as an intersection with a complement.
Solution · Answer
For , write , and .
Quick check
(Is a satisfying assignment alone a certificate that a formula has exactly one satisfying assignment?)
Consider whether a second assignment is excluded.
Solution · Answer
No. It proves at least one assignment exists but does not rule out a distinct second assignment.
Quick check
(Does EXACT-ONE-SAT being in DP prove it is DP-complete?)
Recall the two parts of completeness.
Solution · Answer
No. Completeness also requires a hardness proof under a specified reduction. Only membership was established here. Note also that the total language EXACT-ONE-SAT specifies the answer on every encoded formula, whereas a promise-problem algorithm need only be correct on inputs satisfying its promise.