Proper hierarchies in polylogarithmic time and absence of complete problems
|F. Ferrarotti, K. Schewe, J. Turull-Torres. Proper hierarchies in polylogarithmic time and absence of complete problems. volume 12012, pages 90-105, 1, 2020.|
|Buch||Proceedings of the 11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2020)|
|Serie||Lecture Notes in Computer Science|
The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it was shown that all classes Σ~plogmΣ~mplog or Π~plogmΠ~mplog (m∈Nm∈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.