Proper hierarchies in polylogarithmic time and absence of complete problems

Autoren Flavio Ferrarotti
Senén Andrés González Cornejo
Klaus-Dieter Schewe
José María Turull-Torres
Editoren Andreas Herzig
Juha Kontinen
Titel Proper hierarchies in polylogarithmic time and absence of complete problems
Buchtitel Proceedings of the 11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2020)
Typ in Konferenzband
Verlag Springer
Serie Lecture Notes in Computer Science
Band 12012
ISBN 978-3-030-39950-4
Monat January
Jahr 2020
Seiten 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.