Test Instance Generation for NP-Search Problems

在这个项目中，我们首先建立了一个讨论测试实例生成问题的数学框架，以及这些问题的内在困难，通过这次调查，我们发现了一些要点。例如，我们证明了在某种均匀分布下Tiling问题的测试实例生成对于所有测试实例生成问题都是必不可少的。更具体地说，我们证明了以下结果：如果在TILE这种均匀分布下的Tiling问题的测试实例生成是可行的，那么测试实例生成对于每个NP搜索问题和每个合理分布都是可行的。在这个理论框架下，我们利用一些技术成果，研究了一些具体NP搜索问题的测试实例生成。本文研究了满足性问题（Satisfiability Problem，SAT）在一定均匀分布下的测试实例生成问题.提出了一些测试实例生成算法，并证明了它们的有效性。然后，我们通过实验研究了它们的性能。另一方面，我们也研究了NP和相关问题的平均情况复杂性。我们发现了NP搜索问题和NP优化问题之间的一些差距。事实上，我们能够根据为这些问题生成（测试）实例的难度来描述这种差异。这一结果总结在[2]中。

In this project, we first established a mathematical framework for discussing test instance generation problems and the intrinsic difficulty of such problems.Some of the essential points were found through this investigation. For example, we showed that the test instance generation for Tiling Problem under a certain uniform distribution is essential for all test instance generation problems. More specifically, we showed the following result : if the test instance generation for Tiling Problem under TILE this uniform distribution is feasible, then test instance generation is feasible for every NP search problem and every reasonable distribution. This result and the framework is summarized in [1].In this theoretical framework and using several technical results, we investigated test instance generation for some concrete NP search problem. We consider the test instance generation for SAT,Satisfiability Problem, under a certain uniform distribution. We proposed some test instance generation algorithms, and proved their effectiveness. We then investigated their performance experimentally. These results are now being summarized for a technical paper.On the other hand, the average-case complexity of NP and related problems is also investigated. We found some gap between NP search problems and NP optimization problems. In fact, we were able to characterize this difference in terms of the difficulty of generating (test) instances for those problems. This result is summarized in [2].