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

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

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 \ComplexityClass**NP**
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

Article 3 Article 5

Volume 1999 Published articles

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