On Functions and Relations

摘要

We present a uniform definition for classes of single-and multi-valued functions. We completely analyzed 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 [VW93, HW00] 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.