On the Hardness of Decision and Optimisation Problems
John Slaney, Sylvie Thiébaux · ANU Open Research (Australian National University) · 1998
. 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 m). This paper examines the relationship between the hardness of optimisation and that of decision. We identify an 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 by showing that it predicts the hardness of Blocks World decision problems with much improved accuracy. 1 MOTIVATION The empirical study of phase transition phenomena has proved to be a fruitful approach to the location of hard problems [2, 8, 9]. The most intensive research in this area has conc...