On the Structure of Low Sets
Johannes Köbler, Abteilung Theoretische Informatik · 1995
Over a decade ago, Schoning introduced the concept of lowness into structural complexity theory. Since then a large body of results has been obtained classifying various complexity classes according to their lowness properties. In this paper we highlight some of the more recent advances on selected topics in the area. Among the lowness properties we consider are polynomial-size circuit complexity, membership comparability, approximability, selectivity, and cheatability. Furthermore, we review some of the recent results concerning lowness for counting classes. 1 Introduction The comparison of various complexity classes obtained by restricting different kinds of computational resources is a main theme in complexity theory. Indeed, much of the work in structural complexity originated from the fundamental unresolved question whether nondeterministic time computations are really more powerful than their deterministic counterparts. One approach to attack this and related problems has been ...