I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable for finite state automata and decidable for pushdown automata.Does something similar hold for the complexity of problems? For instance, are there problems that are in $\mathbf{P}$ with respect to one computational model, but are in $\mathbf{EXPTIME} \setminus \mathbf{P}$ with respect to a strictly weaker one?
Can complexities differ w.r.t. different computational models?
cc.complexity theory;computability;terminology
Niel De Beaudrap's point is an important one: a complexity class is defined with respect to a machine model. But if I were to re-interpret your question as:Can the complexity of a problem differ greatly in different computational models ? Then the answer is yes. JeffE's answer to my earlier question about decision tree complexity presents an example of an NP-hard problem (SUBSET SUM) that has polynomial decision tree complexity. 