Catalytic space: non-determinism and hierarchy

DOI10.1007/s00224-017-9784-7zbMath1387.68109OpenAlexW2626690804MaRDI QIDQ1702851

Florian Speelman, Harry Buhrman, Michal Koucký, Bruno Loff

Publication date: 1 March 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5725/

zbMATH Keywords

computational complexityspace complexitynon-determinism

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Randomized and Symmetric Catalytic Computation ⋮ Power of uninitialized qubits in shallow quantum circuits ⋮ On pure space vs catalytic space ⋮ On pure space vs catalytic space

Cites Work

• Unnamed Item
• A Turing machine time hierarchy
• Space hierarchy results for randomized and other semantic models
• Turing machines that take advice
• The method of forced enumeration for nondeterministic automata
• A generic time hierarchy with one bit of advice
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Nondeterministic Space is Closed under Complementation
• Computing with a full memory
• Computational Complexity
• Power from Random Strings
• On the complexity of \(k\)-SAT