Classical Automata on Promise Problems
Viliam Geffert, Abuzer Yakaryilmaz
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.
Full Text: PDF