EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fully Characterizing Lossy Catalytic Computation

Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

Algorithmica · 2026-06 · 88 (3)

DOI: 10.1007/s00453-026-01376-6 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 20.05.2026. Verfasst von Marten Folkertsma und 3 weiteren Autor:innen. Beteiligte Einrichtung: CWI, Amsterdam, The Netherlands. Die Arbeit nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL program., Royal Society University Research Fellowship, Divide and Quantum of the program ‘NWA-ORC’, which is partly funded by the Dutch Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, “catalytic” tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have surprising additional power; a logspace machine with a polynomial length catalytic tape, known as catalytic logspace ( $${\textsf {CL}} $$ CL ), can compute problems which are believed to be impossible for $$\textsf {L} $$ L . A fundamental question of the model is whether the catalytic condition, of leaving the catalytic tape in its exact original configuration, is robust to minor deviations. This study was initialized by Gupta et al. (2024), who defined lossy catalytic logspace ( $${\textsf {LCL}} [e]$$ LCL [ e ] ) as a variant of $${\textsf {CL}} $$ CL where we allow up to e errors when resetting the catalytic tape. They showed that $${\textsf {LCL}} [e] = {\textsf {CL}} $$ LCL [ e ] = CL for any $$e = O(1)$$ e = O ( 1 ) , which remains the frontier of our understanding. In this work we completely characterize lossy catalytic space ( $${\textsf {LCSPACE}} [s,c,e]$$ LCSPACE [ s , c , e ] ) in terms of ordinary catalytic space ( $${\textsf {CSPACE}} [s,c]$$ CSPACE [ s , c ] ). We show that $$\begin{aligned} {\textsf {LCSPACE}} [s,c,e] = {\textsf {CSPACE}} [\Theta (s + e \log c), \Theta (c)] \end{aligned}$$ LCSPACE [ s , c , e ] = CSPACE [ Θ ( s + e log c ) , Θ ( c ) ] In other words, allowing e errors on a catalytic tape of length c is equivalent, up to a constant stretch, to an equivalent errorless catalytic machine with an additional $$e \log c$$ e log c bits of ordinary working memory. As a consequence, we show that for any e , $${\textsf {LCL}} [e] = {\textsf {CL}} $$ LCL [ e ] = CL implies $${\textsf {SPACE}} [e \log n] \subseteq {\textsf {ZPP}} $$ SPACE [ e log n ] ⊆ ZPP , thus giving a barrier to any improvement beyond $${\textsf {LCL}} [O(1)] = {\textsf {CL}} $$ LCL [ O ( 1 ) ] = CL . We also extend all our results to every variant of catalytic space.

Autor:innen und Institutionen

  • CWI, Amsterdam, The Netherlands.
  • QuSoft, Amsterdam, The Netherlands.
  • University of Warwick, England, UK.
  • University of Amsterdam, Amsterdam, The Netherlands.

Förderung

  • Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL program.
  • Royal Society University Research Fellowship
  • Divide and Quantum of the program ‘NWA-ORC’, which is partly funded by the Dutch Research Council

Zitieren

APA

Folkertsma, M., Mertz, I., Speelman, F., & Tupker, Q. (2026). Fully Characterizing Lossy Catalytic Computation. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01376-6

Vancouver

Folkertsma M, Mertz I, Speelman F, Tupker Q. Fully Characterizing Lossy Catalytic Computation. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01376-6

BibTeX
@article{Folkertsma2026,
  author = {Folkertsma, Marten and Mertz, Ian and Speelman, Florian and Tupker, Quinten},
  title = {Fully Characterizing Lossy Catalytic Computation},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {3},
  doi = {10.1007/s00453-026-01376-6}
}
Kostenlos starten →