Details

Autor(en) / Beteiligte

• Große, André
• Hempel, Harald

Titel

On Functions and Relations

Ist Teil von

• Discrete Mathematics and Theoretical Computer Science, 2003, p.181-192

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 [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.