Relativizations of Nonuniform Quantum Finite Automata Families
| Autor: | Tomoyuki Yamakami |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Finite-state machine Computational complexity theory Hierarchy (mathematics) Computer science 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Complexity Decision problem 01 natural sciences Nondeterministic algorithm Closure (mathematics) 010201 computation theory & mathematics Turing reduction 0202 electrical engineering electronic engineering information engineering Quantum finite automata 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Unconventional Computation and Natural Computation ISBN: 9783030193102 UCNC |
| DOI: | 10.1007/978-3-030-19311-9_20 |
| Popis: | Theory of relativization provides profound insights into the structural properties of various collections of mathematical problems by way of constructing desirable oracles that meet numerous requirements of the problems. This is a meaningful way to tackle unsolved questions on relationships among computational complexity classes induced by machine-based computations that can relativize. Slightly different from an early study on relativizations of uniform models of finite automata in [Tadaki, Yamakami, and Li (2010); Yamakami (2014)], we intend to discuss relativizations of state complexity classes (particularly, \(1\mathrm {BQ}\) and \(2\mathrm {BQ}\)) defined in terms of nonuniform families of time-unbounded quantum finite automata with polynomially many inner states. We create various relativized worlds where certain nonuniform state complexity classes become equal or different. By taking a nonuniform family of promise decision problems as an oracle, we can define a Turing reduction witnessed by a certain nonuniform finite automata family. We demonstrate closure properties of certain nonuniform state complexity classes under such reductions. Turing reducibility further enables us to define a hierarchy of nonuniform nondeterministic state complexity classes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|