Voir la notice de l'article provenant de la source Numdam
It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput. 17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary languages, arbitrary small non-constant space is enough for PTMs even using only counter as memory. For counter machines, when restricted to polynomial time, we can obtain the same result for linear space. For constant-space QTMs, we obtain the result for a restricted sweeping head, known as restarting realtime.
Dimitrijevs, Maksims 1 ; Yakaryılmaz, Abuzer 1
@article{ITA_2018__52_2-3-4_111_0,
author = {Dimitrijevs, Maksims and Yakary{\i}lmaz, Abuzer},
editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
title = {Uncountable classical and quantum complexity classes},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {111--126},
publisher = {EDP-Sciences},
volume = {52},
number = {2-3-4},
year = {2018},
doi = {10.1051/ita/2018012},
mrnumber = {3915304},
zbl = {1425.68126},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018012/}
}
TY - JOUR AU - Dimitrijevs, Maksims AU - Yakaryılmaz, Abuzer ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - Uncountable classical and quantum complexity classes JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 111 EP - 126 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018012/ DO - 10.1051/ita/2018012 LA - en ID - ITA_2018__52_2-3-4_111_0 ER -
%0 Journal Article %A Dimitrijevs, Maksims %A Yakaryılmaz, Abuzer %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T Uncountable classical and quantum complexity classes %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 111-126 %V 52 %N 2-3-4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018012/ %R 10.1051/ita/2018012 %G en %F ITA_2018__52_2-3-4_111_0
Dimitrijevs, Maksims; Yakaryılmaz, Abuzer. Uncountable classical and quantum complexity classes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 111-126. doi: 10.1051/ita/2018012
Cité par Sources :