Space-efficient informational redundancy

DOI10.1016/j.jcss.2010.03.005zbMath1208.68128OpenAlexW2120788090MaRDI QIDQ1959428

Christian Glaßer

Publication date: 7 October 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.03.005

zbMATH Keywords

computational complexityautoreducibilitymitoticitylog-space reductions

Mathematics Subject Classification ID

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

Related Items

Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

Cites Work

• Unnamed Item
• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• Relativized alternation and space-bounded computation
• A measure of relativized space which is faithful with respect to depth
• Log space machines with multiple oracle tapes
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Completely Mitotic Nonrecursive R.E. Degree
• Relativization of questions about log space computability
• Mitotic recursively enumerable sets
• Redundancy in Complete Sets
• Non-mitotic Sets
• The Priority Method I