Proper hierarchies in polylogarithmic time and absence of complete problems
Senén Andrés González Cornejo
José María Turull-Torres
|Title||Proper hierarchies in polylogarithmic time and absence of complete problems|
|Booktitle||Proceedings of the 11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2020)|
|Series||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.