Proper Hierarchies in Polylogarithmic Time and Absence of Complete\n Problems

2019/11/29 by Flavio Ferrarotti, Ferrarotti, Flavio, Senén González +5
Computer Science · #Advanced Algebra and Logic #semigroups and automata theory #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.1911.13104

Abstract

The polylogarithmic time hierarchy structures sub-linear time complexity. In\nrecent work it was shown that all classes \\Σ_m^\plog\nor \\Π_m^\plog (m \∈ \ℕ) in this hierarchy can\nbe captured by semantically restricted fragments of second-order logic. In this\npaper the descriptive complexity theory of polylogarithmic time is taken\nfurther showing that there are strict hierarchies inside each of the classes of\nthe hierarchy. A straightforward consequence of this result is that there are\nno complete problems for these complexity classes, not even under polynomial\ntime reductions. As another consequence we show that the polylogarithmic time\nhierarchy itself is strict.\n

Related

• Completeness in Polylogarithmic Time and Space
• The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic
• A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time
• Descriptive Complexity of Deterministic Polylogarithmic Time and Space
• Polynomial Depth, Highness and Lowness for E