Gap-languages and log-time complexity classes
From MaRDI portal
Publication:1389651
DOI10.1016/S0304-3975(96)00288-5zbMath0893.68067OpenAlexW1997129529MaRDI QIDQ1389651
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
Related Items (7)
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I ⋮ The complexity of satisfiability for fragments of hybrid logic. I. ⋮ THE COMPLEXITY OF MODEL CHECKING FOR BOOLEAN FORMULAS ⋮ Relating polynomial time to constant depth ⋮ The Complexity of Satisfiability for Fragments of CTL and CTL⋆ ⋮ THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On input read-modes of alternating Turing machines
- The recursion-theoretic structure of complexity classes
- Independence results about context-free languages and lower bounds
- Reductions among polynomial isomorphism types
- How to prove representation-independent independence results
- On uniform circuit complexity
- 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
- Reducibility by algebraic projections
- Diagonalization, uniformity, and fixed-point theorems
- Minimum-complexity pairing functions
- Polynomial and abstract subrecursive classes
- Logspace and logtime leaf languages
- On uniformity within \(NC^ 1\)
- Sublattices of the polynomial time degrees
- A complexity theory based on Boolean algebra
- Languages that Capture Complexity Classes
- Alternation
- On the Structure of Polynomial Time Reducibility
- Circuit Bottom Fan-in and Computational Power
This page was built for publication: Gap-languages and log-time complexity classes
