Generating Instances for MAX2SAT with Optimal Solutions
Generating Instances for MAX2SAT with Optimal Solutions
复制标题
使用最佳解决方案生成 MAX2SAT 实例
DOI：
10.1007/s00224-005-1221-7
复制
发表时间：
2006
影响因子：
0.5
通讯作者：
Masaki Yamamoto
中科院分区：
文献类型：
--
作者：
Masaki Yamamoto
MAX2SAT 的测试实例生成器（简称实例生成器）是一个程序，它在给定 n 个变量的情况下生成 n 个变量的 2-CNF 公式 F（从一些相当大的域中随机选择），并同时提供 F 的最佳解决方案之一。我们提出了使用某种类型的扩展图（此处称为“精确 1/2 放大器”）设计实例生成器的概要。我们首先展示一种用于构造精确 1/2 放大器的简单算法，从而导出一个具体的多项式时间实例生成器 GEN。我们还表明，可以从随机构建的图中以高概率获得精确的 1/2 放大器。基于这个事实，我们提出了另一种类型的实例生成器 RGEN；它生成一个 2-CNF 公式，其中的解对于该公式具有高概率的最优解。然而，RGEN 生成的公式结构较少，但公式类别比 GEN 多得多。事实上，我们通过 RGEN 生成的一组 2-CNF 公式证明了 MAX2SAT 的 NP 硬度。
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.