6533b82ffe1ef96bd1295a6e

RESEARCH PRODUCT

Uncountable classical and quantum complexity classes

Abuzer YakaryilmazMaksims Dimitrijevs

subject

Discrete mathematicsUnary operationComputer scienceGeneral MathematicsLinear spaceMagic (programming)Binary number0102 computer and information sciences02 engineering and technology01 natural sciencesComputer Science ApplicationsTuring machinesymbols.namesake010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringComplexity classsymbols020201 artificial intelligence & image processingUncountable setTime complexitySoftware

description

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.

yearjournalcountryeditionlanguage
2018-04-01RAIRO - Theoretical Informatics and Applications
https://doi.org/10.1051/ita/2018012