Collapsing Catalytic Classes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10512686" target="_blank" >RIV/00216208:11320/25:10512686 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/FOCS63196.2025.00025" target="_blank" >https://doi.org/10.1109/FOCS63196.2025.00025</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/FOCS63196.2025.00025" target="_blank" >10.1109/FOCS63196.2025.00025</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Collapsing Catalytic Classes

Popis výsledku v původním jazyce

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, exhibited the power of catalytic space (CSPACE) and, in particular, catalytic logspace machines (CL) beyond that of traditional space-bounded machines. Several variants of CL have been proposed, including nondeterministic and co-non-deterministic catalytic computation by Buhrman et al. (STACS 2016) and randomized catalytic computation by Datta et al. (CSR 2020). These and other works proposed several questions, such as catalytic analogues of the theorems of Savitch and Immerman and Szelepcsényi. Catalytic computation was recently derandomized by Cook et al. (STOC 2025), but only in certain parameter regimes. We settle almost all questions regarding randomized and nondeterministic catalytic computation by giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes. With regards to non-determinism, our main result is that CL = CNL and with regards to randomness we show CL = CPrL where CPrL denotes randomized catalytic logspace where the accepting probability can be arbitrarily close to 1/2. We also have a number of near-optimal partial results for non-deterministic and randomized catalytic computation with less catalytic space. We show catalytic versions of Savitch’s theorem, Immerman-Szelepscényi, and the derandomization results of Nisan and Saks and Zhou, all of which are unconditional and hold for all parameter settings. Our results build on the compress-or-compute framework of Cook et al. (STOC 2025). Despite proving broader and stronger results, our framework is simpler and more modular.

Název v anglickém jazyce

Collapsing Catalytic Classes

Popis výsledku anglicky

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, exhibited the power of catalytic space (CSPACE) and, in particular, catalytic logspace machines (CL) beyond that of traditional space-bounded machines. Several variants of CL have been proposed, including nondeterministic and co-non-deterministic catalytic computation by Buhrman et al. (STACS 2016) and randomized catalytic computation by Datta et al. (CSR 2020). These and other works proposed several questions, such as catalytic analogues of the theorems of Savitch and Immerman and Szelepcsényi. Catalytic computation was recently derandomized by Cook et al. (STOC 2025), but only in certain parameter regimes. We settle almost all questions regarding randomized and nondeterministic catalytic computation by giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes. With regards to non-determinism, our main result is that CL = CNL and with regards to randomness we show CL = CPrL where CPrL denotes randomized catalytic logspace where the accepting probability can be arbitrarily close to 1/2. We also have a number of near-optimal partial results for non-deterministic and randomized catalytic computation with less catalytic space. We show catalytic versions of Savitch’s theorem, Immerman-Szelepscényi, and the derandomization results of Nisan and Saks and Zhou, all of which are unconditional and hold for all parameter settings. Our results build on the compress-or-compute framework of Cook et al. (STOC 2025). Despite proving broader and stronger results, our framework is simpler and more modular.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA24-10306S" target="_blank" >GA24-10306S: Nové výzvy proudových, online a kombinatorických algoritmů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

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 statě ve sborníku

Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025

ISBN

979-8-3315-7132-0

ISSN

2575-8454

e-ISSN

—

Počet stran výsledku

9

Strana od-do

455-463

Název nakladatele

IEEE

Místo vydání

USA

Místo konání akce

Sydney, Australia

Datum konání akce

14. 12. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—