Solution to SAT III

Authors: Chieu Nguyen, Pranjal Vachaspati, and Cathy Wu

This puzzle is made to resemble a section of the SAT exam, but with difficult optimization problems instead. Each of the 9 problems is a classic NP-hard optimization problem that has an associated NP-complete decision problem. The first problem is MAX-3SAT, which has the classic 3SAT boolean satisfiability problem as an associated decision problem; this is what the title of the puzzle refers to.

Each problem has a unique integer solution which is not among the choices given. Mapping alphanumerically (A=1, etc.), the solutions spell out KEEP GOING, as a confirmation in case some of the problems were solved incorrectly.

As suggested by the example problem, and by the subtly ambiguous wording of the directions, the correct answer is to be calculated by combining the 5 answer choices with arithmetic operations (addition, subtraction, multiplication, division), following the conventional order of operations. In each case, there is a unique sequence of operations that combines with the answer choices to yield the correct answer. For example, for the first problem, the answers combine in the following way: 1×5×2+13−12=11.

Returning to the example problem, we see that all 5 of the example answer choices make a valid equation. In a similar manner, plug in the sequence of operations from each problem into the example equation, and solve the equation for the missing number on the right-hand side. These map alphanumerically (A=1, etc.) to spell out the answer to the puzzle: MILLSTONE.

ProblemDescriptionSolutionOperationsExample solution
1What is the maximum number of 3-CNF clauses that can be satisfied? (MAX-3SAT)11 (K)××+−13 (M)
2What is the domination number of this graph?5 (E)++×÷9 (I)
3What is the chromatic number of this graph?5 (E)+++−12 (L)
4What is the maximum value of a subset of items that does not exceed the given weight capacity? (0/1 knapsack problem)16 (P)−+×−12 (L)
5What is the size of the largest clique?7 (G)×+×−19 (S)
6How long is the longest simple path between the given points?15 (O)++×−20 (T)
7How long is the shortest cycle that includes all vertices exactly once? (traveling salesperson problem)9 (I)×÷×−15 (O)
8What is the minimum number of sets whose union covers the universe?14 (N)+×+−14 (N)
9What is the maximum number of jobs that can be serially scheduled without exceeding the deadline?7 (G)+−+÷5 (E)