Paper Info
Title
Uncountable classical and quantum complexity classes.
Abstract
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. Yakaryilmaz, 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.
Year
DOI
Venue
2016
10.1051/ita/2018012
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Keywords
DocType
Volume
Probabilistic and quantum computation,small-space bounds,unary languages,uncountable classes,counter machines
Conference
52
Issue
ISSN
Citations 
SP2-4
0988-3754
1
PageRank 
References 
Authors
0.37
15
2
Name
Order
Citations
PageRank
Maksims Dimitrijevs133.14
Abuzer Yakaryilmaz216825.31