Lifting query complexity to time-space complexity for two-way finite automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139267" target="_blank" >RIV/00216224:14330/24:00139267 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.jcss.2023.103494" target="_blank" >https://doi.org/10.1016/j.jcss.2023.103494</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2023.103494" target="_blank" >10.1016/j.jcss.2023.103494</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Lifting query complexity to time-space complexity for two-way finite automata

Popis výsledku v původním jazyce

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language L such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is ⠂⠂(n2), while of exact two-way quantum finite automata with classical states (2QCFA) is O ⠂(n5/3), that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing. (c) 2023 Elsevier Inc. All rights reserved.

Název v anglickém jazyce

Lifting query complexity to time-space complexity for two-way finite automata

Popis výsledku anglicky

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language L such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is ⠂⠂(n2), while of exact two-way quantum finite automata with classical states (2QCFA) is O ⠂(n5/3), that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing. (c) 2023 Elsevier Inc. All rights reserved.

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

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

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

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

1090-2724

Svazek periodika

141

Číslo periodika v rámci svazku

103494

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

13

Strana od-do

1-13

Kód UT WoS článku

001138384300001

EID výsledku v databázi Scopus

2-s2.0-85179893976