Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems

Flavio Ferrarotti, Senén González, Klaus-Dieter Schewe +1

The polylogarithmic time hierarchy structures sub-linear time complexity. In recent work it was shown that all classes ${\tilde{\Sigma }}_m^{plog}$ or $\tildeΠ_{m}^{\mathit{plog}}…