Nondeterminism is typically used as an inherent part of the computational models used incomputational complexity. However, much work has been done looking at nondeterminism asa separate resource added to deterministic machines. This survey examines several differentapproaches to limiting the amount of nondeterminism, including Kintala and Fischer's βhierarchy, and Cai and Chen's guess-and-check model.
| Identifer | oai:union.ndltd.org:uky.edu/oai:uknowledge.uky.edu:gradschool_theses-1223 |
| Date | 01 January 2003 |
| Creators | Levy, Matthew Asher |
| Publisher | UKnowledge |
| Source Sets | University of Kentucky |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | University of Kentucky Master's Theses |
Page generated in 0.0021 seconds