A Formal Analysis of Why Heuristic Functions Work

Many optimization problems in computer science have been proven to be NP-hard, and it is unlikely that polynomial-time algorithms that solve these problems exist unless P = NP. Alternatively, they are solved using heuristics algorithms, which provide a sub-optimal solution that, hopefully, is arbitrarily close to the optimal one. Such problems are found in a wide range of applications, including articial intelligence, game theory, graph partitioning, database query optimization, etc. Consider a heuristic algorithm, A. Suppose that A could invoke one of two possible heuristic functions. The question of determining which heuristic function is superior, has typically demanded a yes/no answer { one which is often substantiated by empirical evidence. In this paper, by using Pattern Classication Techniques (PCT), we propose a formal, rigorous theoretical model that provides a stochastic answer to this problem. We prove that given a heuristic algorithm, A, that could utilize either of two heuristic functions H 1 or H 2 used to nd the solution to a particular problem, if the accuracy of evaluating the cost of the optimal solution by using H 1 is greater than the accuracy of evaluating the cost using