Computational complexity theory, examines combinatorial problems and classifies them based on the computational resource needed to solve them. One of the most important and commonly studied resources is the time needed to solve a particular problem. Nondeterministic computation can be viewed as a process of guessing an answer to a problem and then checking to see if the guess is correct. Many problems that have deterministic solution that require exponential time to compute also have nondeterministic solutions that can be computed in a reasonable amount of time. In general, problems in complexity theory have been stated as questions concerning set membership. An alternative is to consider the more general case of partial functions. The advantage of considering functions as opposed to set membership question is that a function value can be an instance of a solution to a problem, whereas, a corresponding set membership question just states the existence of an instance. Although work has been done on the study of function classes to date these classes have not been examined as closely. This work examines the structure and relationship of both deterministic and nondeterministic function classes, primarily focusing on classes which are in the polynomial-time and exponential-time hierarchies, specifically considering these classes under certain models which use restricted resources. The resources considered include bounding the length of the function value to less than the computation time and limiting the access of the computation to additional information that may be provided by an oracle set. Further, through the study of function classes one can draw insight into the structure of corresponding classes of sets. Probabilistic models for function classes are also studied to determine an appropriate description of interactive proof systems in this environment.
