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.
Mots clés : Probabilistic and quantum computation, small-space bounds, unary languages, uncountable classes, counter machines
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita/2018012/
[1] , and , Quantum computability. SIAM J. Comput. 26 (1997) 1524–1540 | DOI | MR | Zbl
[2] and , A language over a one symbol alphabet requiring only O(log log n) space. ACM SIGACT 7 (1975) 31–33 | DOI
[3] and , Two-way finite automata with quantum and classical states. Theor. Comput. Sci. 287 (2002) 299–311 | DOI | MR | Zbl
[4] and , Automata and quantum computing. Technical Report. Preprint (2015) | arXiv
[5] , , and , New results on the minimum amount of useful space. Int. J. Found. Comput. Sci. 27 (2016) 259–282 | DOI | MR | Zbl
[6] and , Quantum finite automata: A modern introduction, in Computing with New Resources. Vol. 8808 of Lect. Notes Comput. Sci. Springer, Cham (2014) 208–222 | DOI | MR | Zbl
[7] and , Magic coins are useful for small-space quantum machines. Quantum Inf. Comput. 17 (2017) 1027–1043 | MR
[8] , Capabilities of ultrametric automata with one, two, and three states, in Theory and Practice of Computer Science. Vol. 9587 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (2016) 253–264 | DOI | MR | Zbl
[9] and , Uncountable classical and quantum complexity classes, in Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016). Vol. 321. Austrian Computer Society, Australia, books@ocg.at (2016) 131–146 | Numdam | MR
[10] and , Uncountable realtime probabilistic classes, in Descriptional Complexity of Formal Systems. Vol. 10316 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (2017) 102–113 | DOI | MR | Zbl
[11] and , Postselecting probabilistic finite state recognizers and verifiers, in Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018). Vol. 332. Austrian Computer Society, Australia, books@ocg.at (2018) 65–82
[12] and , Probabilistic verification of all languages. Technical Report. Preprint (2018) | arXiv
[13] and , Recognition of uncountably many languages with one counter, in Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), Short Papers. (2018) 7–13
[14] and , A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput. 19 (1990) 1011–1123 | DOI | MR | Zbl
[15] , Probabilistic two-way machines, in Proceedings of the International Symposium on Mathematical Foundations of Computer Science. Springer-Verlag, London (1981) 33–45 | MR | Zbl
[16] , Regularity of one-letter languages acceptable by 2-way finite probabilistic automata, in FCT’91. Springer, Berlin, Heidelberg (1991) 287–296 | MR | Zbl
[17] and , Minimal nontrivial space complexity of probabilistic one-way Turing machines, in MFCS’90. Vol. 452 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (1990) 355–361 | DOI | MR | Zbl
[18] and , On the power of quantum finite state automata, in FOCS’97. IEEE Computer Society Washington, DC (1997) 66–75
[19] and , Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) | MR | Zbl
[20] , Introduction to Probabilistic Automata. Academic Press, New York (1971) | MR | Zbl
[21] , Probabilistic automata. Inf. Control 6 (1963) 230–243 | DOI | Zbl
[22] and , Quantum, stochastic, and pseudo stochastic languages with few states, in UCNC 2014. Vol. 8553 of Lect. Notes Comput. Sci. Springer, Cham (2014) 327–339 | MR | Zbl
[23] and , More on quantum, stochastic, and pseudo stochastic languages with few states. Nat. Comput. 15 (2016) 129–141 | DOI | MR | Zbl
[24] , Turing Machines with Sublogarithmic Space. Springer-Verlag, Berlin, Heidelberg (1994) | DOI | MR | Zbl
[25] , Superiority of one-way and realtime quantum machines. RAIRO: ITA 46 (2012) 615–641 | Numdam | MR | Zbl
[26] , Public qubits versus private coins, in The Proceedings of Workshop on Quantum and Classical Complexity, ECCC:TR12-130. University of Latvia Press, Riga (2013) 45–60.
[27] and , Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10 (2010) 747–770 | MR | Zbl
[28] and Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theor. Comput. Sci. 12 (2010) 19–40 | MR | Zbl
[29] and Probabilistic and quantum finite automata with postselection. (A preliminary version of this paper appeared in the Proceedings of Randomized and Quantum Computation (Satellite Workshop of MFCS and CSL 2010). (2010) 14–24.) Technical Report. Preprint (2011). | arXiv
[30] and Unbounded-error quantum computation with small space bounds. Inf. Comput. 209 (2011) 873–892 | DOI | MR | Zbl
[31] and Proving the power of postselection. Fundam. Inform. 123 (2013) 107–134 | DOI | MR | Zbl
[32] , , and , Quantum computation with write-only memory. Nat. Comput. 11 (2012) 81–94 | DOI | MR | Zbl
[33] , , and , One-way finite automata with quantum and classical states, in Languages Alive. Vol. 7300 of Lect. Notes Comput. Sci. Springer, Berlin, Heidelberg (2012) 273–290 | MR | Zbl
Cité par Sources :
