  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.
