Verifying proofs in constant depth

Abstract

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer to this problem is not determined by the complexity of the language. On the one hand, we construct NC0 proof systems for a variety of languages ranging from regular to NP complete. On the other hand, we show by combinatorial methods that even easy regular languages such as Exact-OR do not admit NC0 proof systems. We also show that Majority does not admit NC0 proof systems. Finally, we present a general construction of NC0 proof systems for regular languages with strongly connected NFA's.