Observations on complete sets between linear time and polynomial time

DOI10.1016/J.IC.2010.11.027MaRDI QIDQ627129zbMATHOpenAlexFDO

Authors 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 hierarchymany-one reducibilitypolynomial-time hierarchydeterminism versus nondeterminismlinear-time hierarchy

Mathematics Subject Classification ID

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

Recommendations

• Completeness for nondeterministic complexity classes
• A note on complete problems for complexity classes
• scientific article; zbMATH DE number 1222922
• Complete Problems and Strong Polynomial Reducibilities
• scientific article; zbMATH DE number 4099277

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 559220 (Why is no real title available?)
• scientific article; zbMATH DE number 1542049 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• Logical foundations of proof complexity
• Nondeterministic Space is Closed under Complementation
• Nonerasing, counting, and majority over the linear time hierarchy
• On quasilinear-time complexity theory
• Quasi-realtime languages
• Rudimentary Predicates and Relative Computation
• Satisfiability Is Quasilinear Complete in NQL
• The Boolean Hierarchy I: Structural Properties
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The method of forced enumeration for nondeterministic automata
• The polynomial-time hierarchy

Cited in

(5)

• Sets computable in polynomial time on average
• On the Teaching Complexity of Linear Sets
• A Polynomial-Time Algorithm to Check Closedness of Simple Second Order Mixed-Integer Sets
• On the teaching complexity of linear sets
• Light affine set theory: A naive set theory of polynomial time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q627129)