Proper hierarchies in polylogarithmic time and absence of complete problems

F. Ferrarotti, S. González Cornejo, K. Schewe, J. Turull-Torres. Proper hierarchies in polylogarithmic time and absence of complete problems. volume 12012, pages 90-105, DOI https://link.springer.com/chapter/10.1007/978-3-030-39951-1_6, 1, 2020.

Autoren
  • Flavio Ferrarotti
  • Senén Andrés González Cornejo
  • Klaus-Dieter Schewe
  • José María Turull-Torres
Editoren
  • Andreas Herzig
  • Juha Kontinen
BuchProceedings of the 11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2020)
TypIn Konferenzband
VerlagSpringer
SerieLecture Notes in Computer Science
Band12012
DOIhttps://link.springer.com/chapter/10.1007/978-3-030-39951-1_6
ISBN978-3-030-39950-4
Monat1
Jahr2020
Seiten90-105
Abstract

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.