A note on logspace optimization

DOI10.1007/BF01268143zbMath0838.68036OpenAlexW2002941015MaRDI QIDQ1904668

Birgit Jenner, Carme Àlvarez

Publication date: 27 May 1996

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01268143

zbMATH Keywords

complexity classesnondeterministic logspace functionsword matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Computation by interaction for space-bounded functional programming ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds

Cites Work

• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• A very hard log-space counting class
• The complexity of computing maximal word functions
• The complexity of iterated multiplication
• Circuits, matrices, and nonassociative computation
• Constant Depth Reducibility
• Positive Relativizations of Complexity Classes
• A taxonomy of problems with fast parallel algorithms
• Problems complete for deterministic logarithmic space
• Nondeterministic Space is Closed under Complementation
• Computing Algebraic Formulas Using a Constant Number of Registers
• Adaptive logspace reducibility and parallel time