Test Instance Generation for NP-Search Problems

点击翻译按钮获取中文摘要

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].