  Many unconventional computing models, including some that appear to be quite
different from traditional ones such as Turing machines, happen to characterise
either the complexity class P or PSPACE when working in deterministic
polynomial time (and in the maximally parallel way, where this applies). We
discuss variants of cellular automata and membrane systems that escape this
dichotomy and characterise intermediate complexity classes, usually defined in
terms of Turing machines with oracles, as well as some possible reasons why
this happens.
