On verifying proofs in constant depth, and polynomial identity testing[HBNI Th76]

Abstract

This thesis is divided into two main parts. The first part deals with proof systems computable by Boolean circuit families that characterize the complexity class NC0 (bounded fanin, constant depth), which is one of the weakest complexity classes. A proof system for a language L is a function f : (0, 1)* --> (0,1)* such that Range( f ) = L. This thesis initiates a study of NC0 computable proof systems with an overarching goal of showing that such proof systems cannot capture the language Taut. The thesis begins by studying NC0 proof systems in the context of regular languages. Sufficient conditions are given for a regular language to have a proof system computable in NC0. On the other hand, it is shown that an explicit regular language does not have a proof system computable in NC0. By generalizing techniques used in constructing proof systems for regular languages, the author constructs NC0 proof systems for languages complete for various complexity classes ranging from NC1 to P. It remains open to characterize the regular languages that indeed have proof systems that are computable in NC0. In the context of Taut, 2TAUT is studied and shown a reduction from 2TAUT to the language associated with directed connectivity in terms of proof systems. It is shown that the set of all undirected graphs that have a path between two fixed vertices s and t has an NC0 proof system. The present study shows that the question of whether a language can be generated using these restricted proof systems is unrelated to the computational complexity of their associated membership problem. The second part of the thesis, studies the problem of testing if a given arithmetic circuit computes the identically zero polynomial (PIT) and give efficient algorithms for certain special cases. Also the complexity of other natural problems that arise in the context of arithmetic circuits, is determined. A multi linearity and identity test for read-thrice formulas is given. Then efficient algorithms are given for PIT on polynomials of the form f1 f2 f3 ... fm + g1 g2 ... gs where fiS and giS are presented as read-once formulas. A hardness of representation is shown for the elementary symmetric polynomial against read-once formulas with the added restriction that every leaf is labeled ax where a is a non-zero field element and x is a variable. Some natural problems in the context of arithmetic circuits are studied. These include counting the number of monomials, and checking if a given monomial has non-zero coefficient in the polynomial computed by a given arithmetic circuit. It is observed that even for monotone (no negative constants) read-twice formulas, counting the number of monomials is #P-hard. It is also shown that checking if the coefficient of a monomial is zero in a polynomial computed by a read-once formula is in logspace.