Recent work on phase transition has detected apparently interesting phenomena in the distribution of hard optimisation problems (find, on some measure, the least m such that the given instance x has a solution of value m) and their corresponding decision problems (determine, for a given bound m, whether or not x has a solution of value less than m). In this talk we analyse the relationship between the hardness of optimisation and that of decision. We identify a simple expression for the latter in terms of the former together with the distance between the bound and the optimal solution size. These results explain both the appeal and the shortcomings of other accounts in the literature. We validate our analysis with a case study taken from AI planning, showing that it predicts the hardness of decision problems in the Blocks World with much improved accuracy.

This is joint work with Dr Sylvie Thiebaux of CSIRO. It presupposes a basic knowledge of complexity but no particularly advanced mathematics.