Uncountable classical and quantum complexity classes

DOI10.1051/ITA/2018012MaRDI QIDQ5223610zbMATH OpenOpenAlexFDO

Authors Maksims Dimitrijevs, Abuzer Yakaryılmaz

Publication date 18 July 2019

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00417

zbMATH Keywords

counter machinesquantum computationunary languagesprobabilistic computationuncountable classessmall-space bounds

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: Polynomial--time constant--space quantum Turing machines (QTMs) and logarithmic--space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (Say and Yakaryi lmaz 2014, arXiv:1411.7647). 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 follow the result for a restricted sweeping head, known as restarting realtime.

Recommendations

• Unbounded-error quantum computation with small space bounds
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Space-bounded quantum complexity

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 18635 (Why is no real title available?)
• scientific article; zbMATH DE number 1346510 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Capabilities of ultrametric automata with one, two, and three states
• Languages recognized by nondeterministic quantum finite automata
• More on quantum, stochastic, and pseudo stochastic languages with few states
• New results on the minimum amount of useful space
• One-way finite automata with quantum and classical states
• Probabilistic automata
• Proving the power of postselection
• Quantum Computability
• Quantum finite automata: a modern introduction
• Quantum, stochastic, and pseudo stochastic languages with few states
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• Superiority of one-way and realtime quantum machines
• Turing machines with sublogarithmic space
• Two-way finite automata with quantum and classical states.
• Unbounded-error quantum computation with small space bounds
• Uncountable classical and quantum complexity classes

Cited in

(2)

• Descriptional complexity and operations -- two non-classical cases
• Uncountable classical and quantum complexity classes

This page was built for publication: Uncountable classical and quantum complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223610)