On Functions and Relations

by    A. Große, H. Hempel

Preprint series: 03-01, Reports on Computer Science

MSC:
68Q15 Complexity classes, See also {03D15}
03D15 Complexity of computation, See also {68Q15}

Abstract: We present a uniform definition for classes of single- and multi-valued functions. We completely analyze the inclusion structure of function classes. In order to compare classes of multi-valued and single-valued functions with respect to the existence of refinements we extend the so called operator method to make it applicable to such cases. Our approach sheds new light on well-studied classes like NPSV and NPMV, allows to give simpler proofs for known results, and shows that the spectrum of function classes closely resembles the spectrum of well-known complexity classes.

Keywords: complexity theory, functions, relations

Upload: 2003-01-14

Update: 2003-01-23


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.