Uncountable classical and quantum complexity classes

DOI10.1051/ita/2018012zbMath1425.68126arXiv1608.00417OpenAlexW2963007886MaRDI QIDQ5223610

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

quantum computationcounter machinesunary languagesprobabilistic computationuncountable classessmall-space bounds

Mathematics Subject Classification ID

Related Items (2)

Uncountable realtime probabilistic classes ⋮ Uncountable classical and quantum complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Turing machines with sublogarithmic space
• Quantum computation with write-only memory
• Two-way finite automata with quantum and classical states.
• More on quantum, stochastic, and pseudo stochastic languages with few states
• Uncountable realtime probabilistic classes
• Capabilities of Ultrametric Automata with One, Two, and Three States
• New Results on the Minimum Amount of Useful Space
• Quantum Finite Automata: A Modern Introduction
• Quantum, Stochastic, and Pseudo Stochastic Languages with Few States
• One-Way Finite Automata with Quantum and Classical States
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Quantum Computability
• Superiority of one-way and realtime quantum machines
• Proving the Power of Postselection
• Uncountable classical and quantum complexity classes
• Probabilistic automata

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