Generating Instances for MAX2SAT with Optimal Solutions

摘要

A test instance generator (an instance generator for short) for MAX2SAT is a procedure that produces, given a number n of variables, a 2-CNF formula F of n variables (randomly chosen from some reasonably large domain), and simultaneously provides one of the optimal solutions for F. We propose an outline to design an instance generator using an expanding graph of a certain type, called here an "exact 1/2-enlarger". We first show a simple algorithm for constructing an exact 1/2-enlarger, thereby deriving one concrete polynomial-time instance generator GEN. We also show that an exact 1/2-enlarger can be obtained with high probability from graphs randomly constructed. From this fact, we propose another type of instance generator RGEN; it produces a 2-CNF formula with a solution which is optimal for the formula with high probability. However, RGEN produces less structured formulas and a much larger class of formulas than GEN. In fact, we prove the NP-hardness of MAX2SAT over the set of 2-CNF formulas produced by RGEN.