dc.description.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. |
en_US |