Archived
This content is available here strictly for research, reference, and/or recordkeeping and as such it may not be fully accessible. If you work or study at University of Kentucky and would like to request an accessible version, please use the SensusAccess Document Converter.
Date Available
12-7-2011
Year of Publication
2003
Document Type
Thesis
College
Engineering
Department/School/Program
Computer Science
Faculty
Judy Goldsmith
Abstract
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.
Recommended Citation
Levy, Matthew Asher, "A SURVEY OF LIMITED NONDETERMINISM IN COMPUTATIONAL COMPLEXITY THEORY" (2003). University of Kentucky Master's Theses. 221.
https://uknowledge.uky.edu/gradschool_theses/221
