Catalytic Space: Non-determinism and Hierarchy

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10368582" target="_blank" >RIV/00216208:11320/18:10368582 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00224-017-9784-7" target="_blank" >http://dx.doi.org/10.1007/s00224-017-9784-7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00224-017-9784-7" target="_blank" >10.1007/s00224-017-9784-7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Catalytic Space: Non-determinism and Hierarchy

Popis výsledku v původním jazyce

Catalytic computation, defined by Buhrman, Cleve, Koucky, 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.

Název v anglickém jazyce

Catalytic Space: Non-determinism and Hierarchy

Popis výsledku anglicky

Catalytic computation, defined by Buhrman, Cleve, Koucky, 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theory of Computing Systems

ISSN

1432-4350

e-ISSN

—

Svazek periodika

62

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

20

Strana od-do

116-135

Kód UT WoS článku

000419479100005

EID výsledku v databázi Scopus

2-s2.0-85020488734