Test Instance Construction for NP-Hard Problems

The performance of heuristic approximation algorithms for NP-hard problems can often only be determined by experimentation. This paper explores some of the issues involved in the efficient generation of useful test sets for such problems, i.e. test sets consisting of instances of the problem for which the answer is known and having other properties useful for testing the performance of approximation algorithms. Some theoretical results are given concerning what kinds of test sets can and cannot be generated; these are derived by examining the complexity of length-restricted instance generation for languages in NP and co-NP. Also examples of test set generation procedures are presented