Abstract | ||
---|---|---|
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-319-09704-6_12 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE |
Keywords | Field | DocType |
descriptional complexity,promise problems,nondeterministic automata,probabilistic automata,alternating automata | Discrete mathematics,Algebra,Automaton,Mathematics | Journal |
Volume | Issue | ISSN |
17.0 | 2.0 | 1462-7264 |
Citations | PageRank | References |
10 | 0.53 | 27 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Viliam Geffert | 1 | 459 | 42.93 |
Abuzer Yakaryilmaz | 2 | 168 | 25.31 |