Proper hierarchies in polylogarithmic time and absence of complete problems

Authors Flavio Ferrarotti
Senén Andrés González Cornejo
Klaus-Dieter Schewe
José María Turull-Torres
Editors Andreas Herzig
Juha Kontinen
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)
Type in proceedings
Publisher Springer
Series Lecture Notes in Computer Science
Volume 12012
ISBN 978-3-030-39950-4
Month January
Year 2020
Pages 90-105
SCCH ID# 19098
Abstract

The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it was shown that all classes Σ~plogmΣ~mplog or Π~plogmΠ~mplog (mNm∈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.