Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems.

The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it was shown that all classes \(\tilde{\varSigma }_{m}^{ plog }\) or \(\tilde{\varPi }_{m}^{ plog }\) (\(m \in \mathbb {N}\)) in this hierarchy can be captured by semantically restricted fragments of second-order logic. In this paper the descriptive complexity theory of polylogarithmic time is taken further showing that there are strict hierarchies inside each of the classes of the hierarchy. A straightforward consequence of this result is that there are no complete problems for these complexity classes, not even under polynomial time reductions.