A FORMAL FRAMEWORK FOR EVALUATING HEURISTIC PROGRAMS

We address the question of how one evaluates the usefulness of a heuri stic program on a particular input. If theoretical tools do not allow us to decide for every instance whether a particular heuristic is fast enough, might we at least write a simple, fast companion program that makes this decision on some inputs of interest? We call such a compan ion program a timer for the heuristic. Timers are related to program c heckers, as defined by Blum (1993), in the following sense: Checkers a re companion programs that check the correctness of the output produce d by (unproven but bounded-time) programs on particular instances; tim ers, on the other hand, are companion programs that attempt to bound t he running time on particular instances of correct programs whose runn ing times have not been fully analyzed. This paper provides a family o f definitions that formalize the notion of a timer and some preliminar y results that demonstrate the utility of these definitions.