Standa Zivny asks

I'd like to ask you about CLIQUE→SAT reduction. The reduction3-SAT→CLIQUE is a standard one from undergrad course. Since SATis NP-Complete, every problem from NP, i.e., CLIQUE as well, isreducible to SAT. Is this reduction "known", i.e. defined by some"natural way" as the reduction 3-SAT→CLIQUE is? Is thattrue for all NP-C problems?

The reduction in Cook's paper create formulas with variables thatrepresent the entire computation of an NP machine accepting CLIQUE. Wecan often do much better. Consider the problem of determining whethera graph on n vertices has a clique of size k.

Variables: y_i,r (true if node i is the rth node ofthe clique) for 1 ≤ i ≤ n, 1 ≤ r ≤ k.

Clauses:

• For each r,y_1,r∨y_2,r∨…∨y_n,r(some node is the rth node of the clique).
• For each i, r<s, ¬y_i,r∨¬y_i,s(no node is both the rth and sth node of the clique).
• For each r≠s and i<j such that (i,j) is not an edge of G, ¬y_i,r∨¬y_j,s. (If there's no edge fromi to j then nodes i and j cannot both be in the clique).

That's the entire formula that will be satisfiable if and only if Ghas a clique of size k.

While simple, an optimized Cook-Levin style reduction can produce smallerformula for large k. This reduction has Θ(n²k²)clauses. Using Robson'sreductionone can create formulas of size O(n²log^O(1)n).

We can get similarly nice reductions for many other NP-completeproblems like 3-COLORING and HAMILTONIAN CYCLE. But there is nogeneral procedure for producing simple formula, especially if thereare calculations involved like SUBSET SUM.