Published by Dept. CS U. Chicago. Copyright 2002 CJTCS

Abstract

We consider deterministic and randomized AC0 program checkers for standard P-complete and NC1-complete problems. Our focus is on the query complexity of the checker: i.e. the number of queries made by the checker to the program. We show that OMEGA(n^{1-\epsilon is a lower bound on the query complexity of deterministic AC0 checkers for these problems, for each epsilon>0, and inputs of length n. On the other hand, we design randomized AC0 checkers of constant query complexity for these problems.

• Preformatted versions of the article
  • DVI (63,276 bytes)
  • PostScript (224,384 bytes)
  • PDF (217,263 bytes)
• Source materials for custom formatting
  • LaTeX (cj02-02.tex, 60,120 bytes)
  • BIBTeX (cj02-02.bib, 16,983 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 165 bytes)
  • Self citation in BIBTeX (311 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.2002.002

---

Article 2
Volume 2002 Published articles