Gap-languages and log-time complexity classes
From MaRDI portal
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)