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.

Autoren
  • Flavio Ferrarotti
  • Klaus-Dieter Schewe
  • José María Turull-Torres
BuchProceedings of the 11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2020)
TypIn Konferenzband
VerlagSpringer
SerieLecture Notes in Computer Science
Band12012
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 (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.