Catalytic space: non-determinism and hierarchy
type: Item
instance of: scholarly article
title: Catalytic space: non-determinism and hierarchy
zbMATH Open document ID: 1387.68109
author: Harry Buhrman
author: Michal Koucký
author: Bruno Loff
author: Florian Speelman
published in: Theory of Computing Systems
publication date: 2018-03-01T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5725/
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6845592
zbMATH Keywords: computational complexity
zbMATH Keywords: space complexity
zbMATH Keywords: non-determinism
MaRDI profile type: Publication
OpenAlex ID: W2626690804
cites work: Power from Random Strings
cites work: Computational Complexity
cites work: Computing with a full memory
cites work: Nondeterministic Space is Closed under Complementation
cites work: On the complexity of \(k\)-SAT
cites work: Q4526985
cites work: Turing machines that take advice
cites work: Space hierarchy results for randomized and other semantic models
cites work: Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
cites work: The method of forced enumeration for nondeterministic automata
cites work: A generic time hierarchy with one bit of advice
cites work: A Turing machine time hierarchy
DOI: 10.1007/S00224-017-9784-7
description: scientific article; zbMATH DE number 6845592