Where the Really Hard Problems Are: Beyond the Decisions 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.