Recently, Osamu 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 egnerat ecertified instances in a way that resembles the underlying distribution #mu#. 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. We show that these generators can be used to find out whether an algorithm is correct and efficient on average under #mu#. In fact, it is not hard to construct Monte Carlo generators for all RP search problems as well as Las Vegas generators fo rall ZPP search problems. On the other hand, we prove that (under the uniform distribution) Monte Carlo generators can only exist for problems in NP intersect co-AM.
展开▼
