Title: Circuit Definitions of Nondeterministic Complexity Classes
Abstract: This paper considers restrictions on Boolean circuits and uses them to obtain new uniform circuit characterizations of nondeterministic space and time classes. It also obtains characterizations of counting classes based on nondeterministic time bounded computations on the arithmetic circuit model. It is shown how the notion of semi-unboundedness unifies the definitions of many natural complexity classes.
Publication Year: 1992
Publication Date: 1992-08-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 53
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot