Observations on complete sets between linear time and polynomial time

DOI10.1016/j.ic.2010.11.027zbMath1213.68295OpenAlexW2059442203MaRDI QIDQ627129

Armin Hemmerling

Publication date: 21 February 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.027

zbMATH Keywords

completenessBoolean hierarchypolynomial-time hierarchymany-one reducibilitydeterminism versus nondeterminismlinear-time hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• On quasilinear-time complexity theory
• The method of forced enumeration for nondeterministic automata
• The polynomial-time hierarchy
• Nonerasing, counting, and majority over the linear time hierarchy
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Nondeterministic Space is Closed under Complementation
• The Boolean Hierarchy I: Structural Properties
• Satisfiability Is Quasilinear Complete in NQL
• Rudimentary Predicates and Relative Computation
• Quasi-realtime languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Observations on complete sets between linear time and polynomial time