Uncountable classical and quantum complexity classes

DOI10.1051/ITA/2018012zbMATH Open1425.68126arXiv1608.00417OpenAlexW2963007886MaRDI QIDQ5223610FDOQ5223610

Authors: Maksims Dimitrijevs, Abuzer Yakaryılmaz 

Publication date: 18 July 2019

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

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.

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

Recommendations

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

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)

Cites Work

• Two-way finite automata with quantum and classical states.
• Title not available (Why is that?)
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Title not available (Why is that?)
• Quantum Computability
• Proving the power of postselection
• Succinctness of two-way probabilistic and quantum finite automata
• Unbounded-error quantum computation with small space bounds
• Probabilistic automata
• Title not available (Why is that?)
• One-way finite automata with quantum and classical states
• Turing machines with sublogarithmic space
• Languages recognized by nondeterministic quantum finite automata
• Superiority of exact quantum automata for promise problems
• Quantum computation with devices whose contents are never read
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum finite automata: a modern introduction
• More on quantum, stochastic, and pseudo stochastic languages with few states
• Superiority of one-way and realtime quantum machines
• Quantum, stochastic, and pseudo stochastic languages with few states
• Uncountable realtime probabilistic classes
• New results on the minimum amount of useful space
• Uncountable classical and quantum complexity classes
• Capabilities of ultrametric automata with one, two, and three states

Cited In (3)

• Descriptional complexity and operations -- two non-classical cases
• Uncountable classical and quantum complexity classes
• Uncountable realtime probabilistic 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)