Gadget (computer science)

NP-completeness reduction from 3-satisfiability to graph 3-coloring. The gadgets for variables and clauses are shown on the upper and lower left, respectively; on the right is an example of the entire reduction for the 3-CNF formula (x ∨ y ∨ ~z) ∧ (~x ∨ ~y ∨ z) with three variables and two clauses.

Many NP-completeness proofs are based on many-one reductions from 3-satisfiability, the problem of finding a satisfying assignment to a Boolean formula that is a conjunction (Boolean and) of clauses, each clause being the disjunction (Boolean or) of three terms, and each term being a Boolean variable or its negation. A reduction from this problem to a hard problem on undirected graphs, such as the Hamiltonian cycle problem or graph coloring, would typically be based on gadgets in the form of subgraphs that simulate the behavior of the variables and clauses of a given 3-satisfiability instance. These gadgets would then be glued together to form a single graph, a hard instance for the graph problem in consideration.[4]

For instance, the problem of testing 3-colorability of graphs may be proven NP-complete by a reduction from 3-satisfiability of this type. The reduction uses two special graph vertices, labeled as "Ground" and "False", that are not part of any gadget. As shown in the figure, the gadget for a variable x consists of two vertices connected in a triangle with the ground vertex; one of the two vertices of the gadget is labeled with x and the other is labeled with the negation of x. The gadget for a clause (t₀ ∨ t₁ ∨ t₂) consists of six vertices, connected to each other, to the vertices representing the terms t₀, t₁, and t₂, and to the ground and false vertices by the edges shown. Any 3-CNF formula may be converted into a graph by constructing a separate gadget for each of its variables and clauses and connecting them as shown.[5]

In any 3-coloring of the resulting graph, one may designate the three colors as being true, false, or ground, where false and ground are the colors given to the false and ground vertices (necessarily different, as these vertices are made adjacent by the construction) and true is the remaining color not used by either of these vertices. Within a variable gadget, only two colorings are possible: the vertex labeled with the variable must be colored either true or false, and the vertex labeled with the variable's negation must correspondingly be colored either false or true. In this way, valid assignments of colors to the variable gadgets correspond one-for-one with truth assignments to the variables: the behavior of the gadget with respect to coloring simulates the behavior of a variable with respect to truth assignment. Each clause assignment has a valid 3-coloring if at least one of its adjacent term vertices is colored true, and cannot be 3-colored if all of its adjacent term vertices are colored false. In this way, the clause gadget can be colored if and only if the corresponding truth assignment satisfies the clause, so again the behavior of the gadget simulates the behavior of a clause.

Agrawal et al. (1997) considered what they called "a radically simple form of gadget reduction", in which each bit describing part of a gadget may depend only on a bounded number of bits of the input, and used these reductions to prove an analogue of the Berman–Hartmanis conjecture stating that all NP-complete sets are polynomial-time isomorphic.[6]

The standard definition of NP-completeness involves polynomial time many-one reductions: a problem in NP is by definition NP-complete if every other problem in NP has a reduction of this type to it, and the standard way of proving that a problem in NP is NP-complete is to find a polynomial time many-one reduction from a known NP-complete problem to it. But (in what Agrawal et al. called "a curious, often observed fact") all sets known to be NP-complete at that time could be proved complete using the stronger notion of AC⁰ many-one reductions: that is, reductions that can be computed by circuits of polynomial size, constant depth, and unbounded fan-in. Agrawal et al. proved that every set that is NP-complete under AC⁰ reductions is complete under an even more restricted type of reduction, NC⁰ many-one reductions, using circuits of polynomial size, constant depth, and bounded fan-in. In an NC⁰ reduction, each output bit of the reduction can depend only on a constant number of input bits.[6]

The Berman–Hartmanis conjecture is an unsolved problem in computational complexity theory stating that all NP-complete problem classes are polynomial-time isomorphic. That is, if A and B are two NP-complete problem classes, there is a polynomial-time one-to-one reduction from A to B whose inverse is also computable in polynomial time. Agrawal et al. used their equivalence between AC⁰ reductions and NC⁰ reductions to show that all sets complete for NP under AC⁰ reductions are AC⁰-isomorphic.[6]

One application of gadgets is in proving hardness of approximation results, by reducing a problem that is known to be hard to approximate to another problem whose hardness is to be proven. In this application, one typically has a family of instances of the first problem in which there is a gap in the objective function values, and in which it is hard to determine whether a given instance has an objective function that is on the low side or on the high side of the gap. The reductions used in these proofs, and the gadgets used in the reductions, must preserve the existence of this gap, and the strength of the inapproximability result derived from the reduction will depend on how well the gap is preserved.

Trevisan et al. (2000) formalize the problem of finding gap-preserving gadgets, for families of constraint satisfaction problems in which the goal is to maximize the number of satisfied constraints.[7] They give as an example a reduction from 3-satisfiability to 2-satisfiability by Garey, Johnson & Stockmeyer (1976), in which the gadget representing a 3-SAT clause consists of ten 2-SAT clauses, and in which a truth assignment that satisfies 3-SAT clause also satisfies at least seven clauses in the gadget, while a truth assignment that fails to satisfy a 3-SAT clause also fails to satisfy more than six clauses of the gadget.[8] Using this gadget, and the fact that (unless P = NP) there is no polynomial-time approximation scheme for maximizing the number of 3-SAT clauses that a truth assignment satisfies, it can be shown that there is similarly no approximation scheme for MAX 2-SAT.

Trevisan et al. show that, in many cases of the constraint satisfaction problems they study, the gadgets leading to the strongest possible inapproximability results may be constructed automatically, as the solution to a linear programming problem. The same gadget-based reductions may also be used in the other direction, to transfer approximation algorithms from easier problems to harder problems. For instance, Trevisan et al. provide an optimal gadget for reducing 3-SAT to a weighted variant of 2-SAT (consisting of seven weighted 2-SAT clauses) that is stronger than the one by Garey, Johnson & Stockmeyer (1976); using it, together with known semidefinite programming approximation algorithms for MAX 2-SAT, they provide an approximation algorithm for MAX 3-SAT with approximation ratio 0.801, better than previously known algorithms.