Gap-languages and log-time complexity classes

DOI10.1016/S0304-3975(96)00288-5MaRDI QIDQ1389651zbMATH OpenOpenAlexFDO

Authors Kenneth W. Regan, Heribert Vollmer

Publication date 30 June 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(96)00288-5

zbMATH Keywords

delayed diagonalizationgap languages

Mathematics Subject Classification ID

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

Recommendations

• Logics for complexity classes
• Remarks on languages acceptable in log log n space
• Logical and schematic characterization of complexity classes
• Languages that Capture Complexity Classes
• Parameterized Complexity Classes under Logical Reductions
• Applicative theories for logarithmic complexity classes
• On the complexity of a mildly context-sensitive language class
• scientific article; zbMATH DE number 4103047
• On complexity classes and algorithmically random languages (extended abstract)
• Closing the gap between runtime complexity and polytime computability

Cites work

• scientific article; zbMATH DE number 440476 (Why is no real title available?)
• scientific article; zbMATH DE number 3841832 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 512990 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• A complexity theory based on Boolean algebra
• A note on structure and looking back applied to the relative complexity of computable functions
• A uniform approach to obtain diagonal sets in complexity classes
• Alternation
• Circuit Bottom Fan-in and Computational Power
• Diagonalization, uniformity, and fixed-point theorems
• How to prove representation-independent independence results
• Independence results about context-free languages and lower bounds
• Languages that Capture Complexity Classes
• Logspace and logtime leaf languages
• Minimum-complexity pairing functions
• On input read-modes of alternating Turing machines
• On the Structure of Polynomial Time Reducibility
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Polynomial and abstract subrecursive classes
• Reducibility by algebraic projections
• Reductions among polynomial isomorphism types
• Sublattices of the polynomial time degrees
• The recursion-theoretic structure of complexity classes

Cited in

(9)

• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• The complexity of satisfiability for fragments of hybrid logic. I.
• The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
• The recursion-theoretic structure of complexity classes
• Relating polynomial time to constant depth
• A new complete language for DSPACE(log n)
• The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
• The complexity of model checking for Boolean formulas
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

This page was built for publication: Gap-languages and log-time complexity classes

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