Title: Determinism, Nondeterminism, Alternation, and Counting.
Abstract: The goal of complexity theory is to determine the amount of computational resources needed to solve various problems. Structural complexity theory attempts to determine the computational resources needed to solve problems in various complexity classes and to determine the relationships among complexity classes. This approach to complexity theory is less adhoc than consideration of individual problems in isolation.
In this dissertation we have considered three sets of results, all related to increasing our understanding of the structure of various complexity classes and relationships among them. The three sets of results that are explored are: (1) Separations of time complexity classes. (2) Closure properties of several function classes. (3) Tools for embedding one complexity class in another.
Publication Year: 2001
Publication Date: 2001-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot