Abstract
Christoph Karg, Johannes Köbler and Rainer Schuler
Abstract:
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.