Weakly hard languages and Kuratowski-Ulam theorems for resource-bounded category
Randall J. Pruim · 1995
In his thesis, Lutz initiated what he calls quantitative study of complexity theory. There the notions of resource-bounded measure and resource bounded category were introduced. One of the objectives of this program was to provide a framework in which complexity theory could move beyond qualitative (or structural) statements about (individual elements of) complexity classes and speak quantitatively about the behavior of the complexity classes themselves, e.g. which properties occurred frequently or were rare among problems in a given class. Resource-bounded category generalizes the classical notion of category on 2$\sp{\omega}$. The generalization occurs by placing effectivity constraints upon the functions which witness that a set is meager or null (measure 0). This allows one to identify some (but not all) subclasses of naturally occurring countable classes as small viz a viz the entire class. In the classical notions, of course, such classes (and therefore all of their subclasses) are necessarily small, since they are countable. This thesis answers two previously open questions regarding these notions. First we will demonstrate the existence of weakly complete languages for exponential time which are not complete. These are languages which are sufficient to compute some non-negligible (i.e., non-meager) portion of the class but not the entire class. The existence of such languages had been conjectured already by Jack Lutz. We also investigate an abstract property of notions of category. In the classical notions of measure and category, theorems of Fubini and of Kuratowski and Ulam which relate smallness (being null or meager) in product spaces to smallness of one-dimensional slices have proven very useful. Unfortunately, for most notions of resource-bounded category, we are able to show that the analogous theorem does not hold. There is, however, one interesting case where there is a Kuratowski-Ulam analogue, namely in the class of recursive languages.