Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe.

Abstract

Recently, Watanabe proposed a framework for testing the correctness and average-case performance of algorithms that purport to solve a given NP search problem efficiently on average with respect to some distribution on the instances. The idea is to randomly generate certified instances under some distribution that resembles the input distribution. Watanabe showed that unless RE=NE, test instances cannot be generated for some NP search problems. We further discuss Watanabe's approach and show, as an upper bound, that test instances can be generated for every \ComplexityClassNP search problem with non-adaptive queries to an NP oracle.

We also introduce Las Vegas and Monte Carlo types of test instance generators and show that these generators can be used to find out (with high confidence) whether an algorithm is correct and efficient on average. It is shown that Monte Carlo generators can be easily constructed for all RP search problems and that Las Vegas generators exist for all ZPP search problems as well as for other problems such as prime factorization\@. On the other hand, we prove that Monte Carlo generators can only exist for problems in the intersection of NP and coAM.

• Preformatted versions of the article
  • DVI (108,856 bytes)
  • PostScript (546,199 bytes)
  • PDF (447,217 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj99-04.tex, 65,536 bytes)
  • BIBTeX (cj99-04.bib, 10,878 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 165 bytes)
  • Self citation in BIBTeX (395 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.1999.004

---

Article 3 Article 5
Volume 1999 Published articles

Last modified: Sat Mar 20 09:32:31 CST 1999