Catalytic Space: Non-determinism and Hierarchy
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Catalytic Space : Non-determinism and Hierarchy. / Buhrman, Harry; Koucky, Michal; Loff, Bruno; Speelman, Florian.
I: Theory of Computing Systems, Bind 62, Nr. 1, 01.2018, s. 116-135.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Catalytic Space
T2 - Non-determinism and Hierarchy
AU - Buhrman, Harry
AU - Koucky, Michal
AU - Loff, Bruno
AU - Speelman, Florian
PY - 2018/1
Y1 - 2018/1
N2 - Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation.
AB - Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation.
KW - Computational complexity
KW - Space complexity
KW - Non-determinism
U2 - 10.1007/s00224-017-9784-7
DO - 10.1007/s00224-017-9784-7
M3 - Journal article
VL - 62
SP - 116
EP - 135
JO - Theory of Computing Systems
JF - Theory of Computing Systems
SN - 1432-4350
IS - 1
ER -
ID: 190652879