Date Available

12-7-2011

Year of Publication

2003

Document Type

Thesis

College

Engineering

Department

Computer Science

First Advisor

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.

Download

Share

COinS