Building on the work of Deutsch and Jozsa, we construct oracles relati
ve to which (1) there is a decision problem that can be solved with ce
rtainty in worst-case polynomial time on the quantum computer, yet it
cannot be solved classically in probabilistic expected polynomial time
if errors are not tolerated, nor even in nondeterministic polynomial
time, and (2) there is a decision problem that can be solved in expone
ntial time on the quantum computer, which requires double exponential
time on all but finitely many instances on any classical deterministic
computer.