Abstract
Johannes Köbler
Abstract:
Over a decade ago, Schöning 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.