Lesson · Intractability and Approximation · Deciding, verifying, searching

Decision, Search and the Certificate

The classes this course is about are classes of decision problems, which looks like a restriction and is not one. The lab hands a satisfiability oracle — a routine that answers yes or no and returns nothing else — four questions about a formula in three variables, and builds a satisfying assignment out of the four answers. That is the whole price of the restriction: n + 1 calls.

Open the interactive lesson Practice

a DECISION problem answers yes or no; a SEARCH problem hands back the object a certificate is an object a verifier accepts in polynomial time fix x1 = T and ask again: still yes, keep it; no, and every model has x1 = F 4 oracle calls against 8 assignments, and one more variable doubles only the 8 the reduction is polynomial in CALLS; the oracle is not polynomial in anything

Four questions, three variables, and the assignment the oracle never returned

Core ideas

What this lesson establishes

The hard idea is the asymmetry between finding an object and checking one. The other two say what the restriction to yes-or-no questions costs, which is a number the lab counts, and what the oracle costs, which is a separate question the reduction does not touch and must not be read as answering.

Checking is a different question from finding

Hand someone an assignment and they can evaluate every clause and tell you whether it satisfies the formula; the work is one pass over the clauses. Ask them to produce one and nobody knows a method that is not, in the worst case, a search. A certificate is an object that makes the yes answer checkable in polynomial time, and NP is the class of decision problems that have one. The definition says nothing at all about how the certificate is found, and that silence is the whole open question.

Restricting to yes-or-no questions costs n + 1 calls

It would be reasonable to think the decision version is a weaker, easier question than the search version, so that results about it say less. Here it is not. The lab fixes x1 to true and asks the oracle whether what is left is still satisfiable: if yes, some model has x1 true and committing is safe; if no, every model has x1 false and committing to false is safe. Either way one question settles one variable, and after n more the assignment is written out. On the formula loaded, four calls against eight assignments.

An exponential oracle is still an oracle

The oracle in the lab is brute force — it decides satisfiability by trying all eight assignments. That is deliberate and it is not a cheat, because the claim being demonstrated is about the number of CALLS, not about their cost. The reduction is polynomial in calls; the oracle is not polynomial in anything; and neither fact affects the other. A reader who concludes from this page that satisfiability has been solved efficiently has read a statement about one quantity as a statement about another.

The material

Three forms of one question, and the reduction between two of them

What a decision problem is, what a certificate is, the theorem that search reduces to decision, and the four calls the lab makes.

Definition · A decision problem

A decision problem is a set of inputs together with a yes-or-no question about each one. SAT is the decision problem whose input is a formula in conjunctive normal form and whose question is “is there an assignment satisfying every clause?”. An algorithm solves it by answering the question; it is not required to produce anything else, and the oracle in the lab does not.

Definition · A certificate, and the class NP

A decision problem is in NP when every yes instance has a certificate of size polynomial in the input, and a verifier that reads the instance and the certificate and accepts in polynomial time, accepting no certificate whatever for a no instance. For SAT the certificate is an assignment and the verifier evaluates the clauses. P is the class of decision problems solvable in polynomial time, and P is contained in NP because an algorithm that answers the question is a verifier that ignores its certificate.

Whether the containment is strict is not known, and nothing on this course settles it. What the rest of the course does is build the structure that makes the question sharp: a relation between problems that carries hardness from one to another, a family of problems at the top of that relation, and six things worth doing about a problem that reaches it.

The same question in three forms

Every problem here can be asked three ways, and it is worth separating them before the machinery starts. The decision form asks whether a solution exists; the search form asks for one; the optimisation form asks for the best one. They are different questions and the theory is stated for the first. The reason that costs nothing is this lesson.

Theorem · Search reduces to decision for satisfiability

Suppose a routine decides SAT in one unit of time. Then a satisfying assignment for a formula on n variables can be produced with n + 1 calls to it.

Call the oracle on the formula itself. If it says no there is no assignment to produce and the work is over, which is the first call. Otherwise fix x1 to true, simplify — delete every clause containing x1 and delete ¬x1 from the clauses containing it — and call the oracle on what is left.

If that call says yes, some satisfying assignment of the original has x1 true, so committing to true loses nothing. If it says no, no satisfying assignment has x1 true; since the original is satisfiable, every satisfying assignment has x1 false, so committing to false loses nothing. Either way one call settles one variable and the remaining formula is still satisfiable.

Repeat for x2 up to xn. After n more calls every variable is fixed and no clause remains unsatisfied, so reading the commitments off gives an assignment. The total is n + 1 calls, each on a formula no larger than the original.

□

What the lab counts, and what it refuses to count

The loaded formula is (x1 or x2 or not x3) and (not x1 or x2 or x3) and (x1 or not x2 or x3) and (not x1 or not x2 or not x3): three variables, four clauses. The panel reports 4 oracle calls against 8 assignments a search would try, the assignment x1=T x2=T x3=F, and the formula's 4 models out of those 8. Both branches are allowed at x1 and at x2, so the reduction takes true and moves on; at x3 the oracle refuses true and the reduction takes false, which is the only place on this instance where a question does any work.

Two checks run beside the trace and neither is decoration. Every restricted formula is re-decided by brute force independently of the reduction, and all three steps are required to agree; and the assignment at the end is evaluated clause by clause rather than assumed. A reduction that produced a confident wrong witness would look identical on the page without them.

Example · The step that refuses a branch

After x1 and x2 are both fixed true, the formula that is left is (not x3). The oracle is asked whether fixing x3 to true leaves something satisfiable and answers no, so x3 is false. That single refusal is the difference between an assignment and a guess, and it cost one question.

Now read the two numbers side by side and resist the conclusion. Four calls against eight assignments is a saving of one half on this formula. Move to the four-variable example in the panel and it is five calls against sixteen. The calls grow by one per variable and the assignments double, so the gap widens without limit — but that sentence is a claim about the two expressions, not about the two numbers on screen, and the numbers on screen cannot establish it.

Interactive

Search from decision: n + 1 questions build the answer

The oracle only says yes or no, and asking it once per variable produces a satisfying assignment it never returned

Edit the formula and watch a branch be refused

Every restricted formula is re-decided by brute force, separately from the reduction, and the two answers are required to agree at every step. The assignment at the end is checked clause by clause rather than assumed — a reduction that produced a confident wrong witness would look identical without that check.

Worked example

Clauses, literals by spaces and clauses by a semicolon

Highlight the question asked about this variable1

Variables and clauses—

The decision oracle says—

Oracle calls used—

Assignments a search would try—

The assignment produced—

It satisfies every clause—

Every step agrees with brute force—

Models the formula has—

The oracle answers one question: is this formula satisfiable. It never returns an assignment. Fix x1 to true, ask again; if the answer is still yes, keep it, otherwise x1 must be false. After n more questions every variable is fixed and what is left is the assignment. The oracle here is brute force, which is the joke: an exponential oracle is still an oracle, and what is being shown is the reduction, not an efficient algorithm.

Method

Turning a yes-or-no routine into one that hands back the object

The procedure is four lines and the discipline is in what you check afterwards.

Decide the whole instance first

One call, before anything is fixed. If the answer is no there is nothing to build and every later call would be answering a question about an instance you have already been told has no solution. The lab stops there, and the trace shows no variable being fixed.

Fix one variable and re-ask

Set the variable, simplify the instance, and call the oracle on the smaller instance. Keep the value if the answer is still yes; take the other value if it is no. Do not reason about which value looks more promising — the oracle's answer is the whole justification and a heuristic here would break the argument.

Check that the remaining instance is still a yes

The invariant that makes the induction work is that the formula in hand is satisfiable at every step. The lab re-decides each restricted formula with brute force and prints whether every step agreed; if one did not, the commitment before it was wrong and everything after it is about a different problem.

Verify the object against the original instance

Evaluate the finished assignment clause by clause on the formula as it was typed, not on the simplified one you ended with. The lab prints that verdict separately from the oracle's, because a witness checked only against the instance it was derived from is checked against itself.

Report the calls and their cost as two numbers

Say how many times the oracle was asked and say what one call costs. Collapsing them into a single claim about efficiency is the error this construction invites, and it is the one the panel refuses to make.

Deciding, verifying, and the difference

Score 0 / 0

Choose the answer you can justify.

Four calls on a four-clause formula

The formula is (x1 or x2 or not x3) and (not x1 or x2 or x3) and (x1 or not x2 or x3) and (not x1 or not x2 or not x3). One row per question, with the formula the question was asked about and what the oracle allowed.

question formula asked about T? F? taken clauses left 0 the whole formula satisfiable 4 1 (x2 ∨ x3) ∧ (¬x2 ∨ ¬x3) yes yes x1 = T 2 2 (¬x3) yes yes x2 = T 1 3 nothing left no yes x3 = F 0 assignment produced x1=T x2=T x3=F satisfies every clause yes, checked clause by clause every branch re-asked of brute force all 3 agree oracle calls used 4 n + 1 is 4 assignments a search would try 8 models the formula has 4 of 8 (000, 110, 101, 011)

Rows 1 and 2 have yes in both columns, and that is the ordinary case: both values of the variable extend to some model, so the reduction takes true and nothing is lost. Row 3 is where a question earns its keep. The formula in hand is (not x3), fixing x3 true empties a clause, the oracle says no, and false is forced.

Notice that the assignment produced, 110, is one of the four models and the reduction had no way of preferring it. Any of the four would have been a correct answer to the search question; the oracle's answers happen to walk to this one, and which one they walk to depends on the order the variables are fixed in, not on anything about the formula.

For a faded rehearsal, switch the panel to the formula with exactly one model and predict the two columns before running it. The supplied first move: with only one model, no variable can go both ways, so every row must read yes in exactly one column. Say which one, for each of the three variables, and then check — and notice that being right about this formula tells you nothing about the next.

Common mistakes

Reading the certificate definition as a claim about findingNP says a yes answer can be justified quickly once the justification is in hand. It says nothing about producing it, and the definition would be trivially uninteresting if it did. Every misunderstanding of what P versus NP asks comes from collapsing the two.

Taking the call count for a running timeFour calls is four calls. On this page one call is a search over eight assignments, so the page's own total work is larger than the search it is compared against. The panel prints both numbers and refuses to divide them, and so should you.

Believing the decision form is a weaker resultIt is common to hear that hardness results are “only” about decision problems. For every problem on this course the search and optimisation forms are no harder than the decision form by an argument of exactly this shape, so a hardness result about the yes-or-no question is a hardness result about all three.

Check your understanding

✓

Finish when you can turn a yes-or-no routine into one that returns the object, and say what that costs.

You should be able to define a certificate and the class it defines, state the containment that is known and the one that is open, run the fixing argument on a formula of your own, and separate the number of calls a reduction makes from what a call costs.

Note: This is the only construction on this course that does not transform an instance: it transforms a question. Every reduction after it takes an instance of one problem and builds an instance of another, and “A Reduction Is a Construction” builds the first of them in front of you.