Space-efficient informational redundancy

DOI10.1016/J.JCSS.2010.03.005MaRDI QIDQ1959428zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Space-Efficient Informational Redundancy
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• Introduction to autoreducibility and mitoticity

Cites work

• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• scientific article; zbMATH DE number 3343692 (Why is no real title available?)
• A Completely Mitotic Nonrecursive R.E. Degree
• A measure of relativized space which is faithful with respect to depth
• Deterministic coin tossing with applications to optimal parallel list ranking
• Log space machines with multiple oracle tapes
• Mitotic recursively enumerable sets
• Non-mitotic Sets
• Redundancy in Complete Sets
• Relativization of questions about log space computability
• Relativized alternation and space-bounded computation
• Space-bounded hierarchies and probabilistic computations
• The Priority Method I

Cited in

(2)

• Space-Efficient Informational Redundancy
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

This page was built for publication: Space-efficient informational redundancy

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