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.

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.

DOI : 10.1051/ita/2018012
Classification : 68Q05, 68Q15, 68Q75
Mots-clés : Probabilistic and quantum computation, small-space bounds, unary languages, uncountable classes, counter machines
Dimitrijevs, Maksims 1 ; Yakaryılmaz, Abuzer 1

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://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] L.M. Adleman, J. Demarrais and M.-D.A. Huang, Quantum computability. SIAM J. Comput. 26 (1997) 1524–1540 | DOI | MR | Zbl

[2] H. Alt and K. Mehlhorn, A language over a one symbol alphabet requiring only O(log log n) space. ACM SIGACT 7 (1975) 31–33 | DOI

[3] A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states. Theor. Comput. Sci. 287 (2002) 299–311 | DOI | MR | Zbl

[4] A. Ambainis and A. Yakaryılmaz, Automata and quantum computing. Technical Report. Preprint (2015) | arXiv

[5] Z. Bednárová, V. Geffert, K. Reinhardt and A. Yakaryılmaz, New results on the minimum amount of useful space. Int. J. Found. Comput. Sci. 27 (2016) 259–282 | DOI | MR | Zbl

[6] A.C. Cem Say and A. Yakaryılmaz, 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] A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quantum Inf. Comput. 17 (2017) 1027–1043 | MR

[8] M. Dimitrijevs, 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] M. Dimitrijevs and A. Yakaryılmaz, 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] M. Dimitrijevs and A. Yakaryılmaz, 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] M. Dimitrijevs and A. Yakaryılmaz, 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] M. Dimitrijevs and A. Yakaryılmaz, Probabilistic verification of all languages. Technical Report. Preprint (2018) | arXiv

[13] M. Dimitrijevs and A. Yakaryılmaz, 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] C. Dwork and L. Stockmeyer, A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput. 19 (1990) 1011–1123 | DOI | MR | Zbl

[15] R. Freivalds, 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] J. Kaņeps, Regularity of one-letter languages acceptable by 2-way finite probabilistic automata, in FCT’91. Springer, Berlin, Heidelberg (1991) 287–296 | MR | Zbl

[17] J. Kaņeps and R. Freivalds, 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] A. Kondacs and J. Watrous, On the power of quantum finite state automata, in FOCS’97. IEEE Computer Society Washington, DC (1997) 66–75

[19] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) | MR | Zbl

[20] A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971) | MR | Zbl

[21] M.O. Rabin, Probabilistic automata. Inf. Control 6 (1963) 230–243 | DOI | Zbl

[22] A.M. Shur and A. Yakaryılmaz, 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] A.M. Shur and A. Yakaryılmaz, More on quantum, stochastic, and pseudo stochastic languages with few states. Nat. Comput. 15 (2016) 129–141 | DOI | MR | Zbl

[24] A. Szepietowski, Turing Machines with Sublogarithmic Space. Springer-Verlag, Berlin, Heidelberg (1994) | DOI | MR | Zbl

[25] A. Yakaryılmaz, Superiority of one-way and realtime quantum machines. RAIRO: ITA 46 (2012) 615–641 | Numdam | MR | Zbl

[26] A. Yakaryılmaz, 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] A. Yakaryılmaz and A.C. Cem Say, Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10 (2010) 747–770 | MR | Zbl

[28] A. Yakaryılmaz and A.C. Cem Say Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theor. Comput. Sci. 12 (2010) 19–40 | MR | Zbl

[29] A. Yakaryılmaz and A.C. Cem Say 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] A. Yakaryılmaz and A.C. Cem Say Unbounded-error quantum computation with small space bounds. Inf. Comput. 209 (2011) 873–892 | DOI | MR | Zbl

[31] A. Yakaryılmaz and A.C. Cem Say Proving the power of postselection. Fundam. Inform. 123 (2013) 107–134 | DOI | MR | Zbl

[32] A. Yakaryılmaz, R. Freivalds, A.C. Cem Say and R. Agadzanyan, Quantum computation with write-only memory. Nat. Comput. 11 (2012) 81–94 | DOI | MR | Zbl

[33] S. Zheng, D. Qiu, L. Li and J. Gruska, 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 :