文章基本信息

标题：The Query Complexity of Program Checking by Constant-Depth Circuits
本地全文：下载
作者：Vikraman Arvind ; K.V. Subrahmanyam ; N. V. Vinodchandran 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we study program checking (in the sense of Blum and Kannan) using constant-depth circuits as checkers. Our focus is on the number of queries made by the checker to the program being checked and we term this as the query complexity of the checker for the given problem. We study the query complexity of both deterministic and randomized constan-depth circuits as checkers. We show sub-linear lower bounds on the query complexity of checkers that are deterministic constant-depth circuits for Parity and certain P-complete and NC^1-complete problems. On the other hand, we show that there are randomized constant-depth circuits of constant query complexity that check Parity and suitably encoded complete problems for P, NL, and NC^1. The latter results are proved using techniques from the PCP(poly,1) protocol for 3-SAT.
关键词：constant-depth circuits, Probabilistically Checkable Proofs, program checking, Randomized