Test Instance Generation for NP-Search Problems

在这个项目中，我们首先建立了一个数学框架来讨论测试用例生成问题以及测试用例生成问题的内在困难，并通过调查找到了一些要点。例如，我们证明了在一定的均匀分布下，平铺问题的测试用例生成对于所有的测试用例生成问题都是必不可少的。更具体地说，我们证明了如下结果：如果该均匀分布下的贴片问题的测试用例生成是可行的，那么测试用例生成对于每个NP搜索问题和每个合理的分布都是可行的。在这个理论框架下，我们利用一些技术成果，研究了一些具体的NP搜索问题的测试用例生成问题。在一定的均匀分布下，我们考虑了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].