Observations on complete sets between linear time and polynomial time

DOI10.1016/J.IC.2010.11.027zbMATH Open1213.68295OpenAlexW2059442203MaRDI QIDQ627129FDOQ627129

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

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

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)

Cites Work

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

Cited In (5)

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

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)