Where the Really Hard Problems Are: Beyond the Decision Case

这是一个经验式人工智能项目。我们研究了影响计算最优或接近最优解的平均难度的因素，这些问题的最坏情况通常是难以解决的。现有的大多数关于硬实例分布的研究都涉及决策问题，其中的问题是解决方案是否存在。对于优化，我们寻求可比较的结果，其中目标是最佳解，而对于近似值，目标是好的解。预期结果包括搜索算法的新启发式，预测搜索成本的新方法，以及对算法的平均案例行为的解释。

This is a project in empirical artificial intelligence. We study factors affecting the average difficulty of computing optimal or near-optimal solutions to instances of problems whose worst cases are typically intractable. Most existing research on the distribution of hard instances concerns decision questions, where the issue is whether solutions exist or not. We seek comparable results for optimization, where the goal is the best solution, and for approximation, where the goal is a good solution. Expected outcomes include new heuristics for search algorithms, new methods for predicting search costs, and explanations of the average case behaviour of algorithms.