Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

The Complexity of Generating Test Instances

Christoph Karg, Johannes Köbler and Rainer Schuler


Recently, Watanabe proposed a new framework for testing the correctness and average case behavior of algorithms that purport to solve a given NP search problem efficiently on average. The idea is to randomly generate certified instances in a way that resembles the underlying distribution. We discuss this approach and show that test instances can be generated for every NP search problem with non-adaptive queries to an NP oracle. Further, we introduce Las Vegas as well as Monte Carlo types of test instance generators and show that these generators can be used to find out whether an algorithm is correct and efficient on average. In fact, it is not hard to construct Monte Carlo generators for all RP search problems as well as Las Vegas generators for all ZPP search problems. On the other hand, we prove that Monte Carlo generators can only exist for problems in co-AM.

Ps-File: The Complexity of Generating Test Instances.