View Related Documents

Abstract

Counting functions can be defined syntactically or seman- tically depending on whether they count the number of witnesses in a non-deterministic or in a deterministic computation on the input. In the Turing machine based model, these two ways of defining counting were proven to be equivalent for many important complexity classes. In the circuit based model, it was done for #P and #L, but for low-level complexity classes such as #AC0 and #NC1 only the syntactical defi- nitions were considered. We give appropriate semantical definitions for these two classes and prove them to be equivalent to the syntactical ones. This enables us to show that #AC0 is included in the family of count- ing functions computed by polynomial size and constant width counting branching programs, therefore completing a result of Caussinus et al [CMTV98]. We also consider semantically defined probabilistic complex- ity classes corresponding to AC0 and NC1 and prove that in the case of unbounded error, they are identical to their syntactical counterparts.
This research was supported by the ESPRITWorking Group RAND2 No. 21726 and by the French-Hungarian bilateral project Balaton, Grant 99013

Fulltext Preview

Image of the first page of the fulltext document