<p>Another well known example of how a Turing complete computational model can lead to a time complexity blow-up is <a href="http://en.wikipedia.org/wiki/Counter_automaton" rel="nofollow">2 Counter Automata (2CA)</a></p>

<p>A 2CA is equipped with two registers that can store an unbounded nonnegative integer and can execute only simple instructions decrement/increment the counters, conditional jumps (after checking if a counter is zero), unconditional jump.
The input is placed in one of the two counters, so it must be represented in <em>unary</em>.</p>

<p>A 2CA can simulate an arbitrary Turing machine $M$ on input $x$ but only if its input is set to $2^x$. So every simulated tape operation of $M$ on $x$ requires exponential time.</p>

CC BY-SA 3.0
2014-06-05T10:46:41.523Z
2014-06-05T10:46:41.523Z
Marzio De Biasi
<p>Niel De Beaudrap's point is an important one: a complexity class is defined <em>with respect to</em> a machine model. But if I were to re-interpret your question as:</p>

<blockquote>
  <p>Can the complexity of a problem differ greatly in different computational models ? </p>
</blockquote>

<p>Then the answer is yes. <a href="https://cstheory.stackexchange.com/a/22080/80">JeffE's answer</a> to <a href="https://cstheory.stackexchange.com/questions/22079/provable-gaps-between-decision-tree-complexity-and-true-complexity">my earlier question</a> about decision tree complexity presents an example of an NP-hard problem (SUBSET SUM) that has polynomial decision tree complexity. </p>

CC BY-SA 3.0
2014-06-05T13:23:38.550Z
It looks like there is a different word needed (different from *complexity*). I understood that Niel de
Beaudrap was saying just the opposite. Complexity and complexity classes
are independent from computational models. I wonder whether one should
use here more the word *cost*, to measure the time, or space, or
whatever needed, that depends on the computational model. See above my [comment to the question](http://cstheory.stackexchange.com/questions/23783#comment60518_23783)
babou
CC BY-SA 3.0
2014-06-05T15:56:26.230Z
My mistake was to assume a definition for the well-known complexity classes while I could just as easily have looked it up. I take Niel de Beaudrap's comments as an observation of that, with further clarification that complexity *classes* are defined with a precise model of computation in mind. Complexity is, however, still the right term.
Rhymoid
CC BY-SA 3.0
2014-06-05T10:00:28.423Z
2014-06-05T10:00:28.423Z
2017-04-13T12:32:28.053Z
Suresh Venkat
<p>I understand that a decision problem can be decidable <em>with respect to</em> 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.</p>

<p>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?</p>

CC BY-SA 3.0
2014-06-05T08:46:47.847Z
One should not confuse run-times ("can this model of computation solve this problem in polynomial time?") with complexity classes ("is this problem in **P**?"). The class **P** refers, by *definition*, to problems solvable in polynomial time on a Turing Machine (and poly-time equivalent models of computation). Other classes may represent polynomial-time computation in another model: **BPP** and **BQP** are examples of this, for (bounded-error solvabilty by) randomised and quantum Turing machines, for instance.
Niel de Beaudrap
CC BY-SA 3.0
2014-06-05T09:54:31.437Z
Nevertheless I think there's a useful question lurking underneath.
Suresh Venkat
CC BY-SA 3.0
2014-06-05T10:00:30.810Z
I am no complexity expert in any way. But my impression was that the
question makes sense, though its statement may not use the right
terminology.  Why the downvote? If the reason is that you consider it
inappropriate for TCS: say so, at least. Or flag it for transfer to CS.
babou
CC BY-SA 3.0
2014-06-05T10:12:21.270Z
@SureshVenkat I commented at the same time you did. I liked his forward way of
talking of undecidability with respect to a computational model (is
that an accepted view, or is there a hidden trap?). Do you think you can rephrase the question in
a better way?  I do not have the expertise to understand the
subtleties of the issue, and I think I am missing the point made by
Niel de Beaudrap's comment.
babou
CC BY-SA 3.0
2014-06-05T10:13:06.157Z
We don't usually rephrase an OP's question unless they ask for it themselves.
Suresh Venkat
CC BY-SA 3.0
2014-06-05T11:34:20.393Z
@Babou: the point is just that the set of problems solvable in polynomial time by different models of computation form different complexity classes — not a single class whose definition changes with the model. That is to say, if one wishes to speak about polynomial time algorithms in *different* models of computation, one should simply say so, and not try to shoehorn it into **P**-parlance.
Niel de Beaudrap
CC BY-SA 3.0
2014-06-05T13:12:05.790Z
@NieldeBeaudrap Thanks. I thought there was something more subtle to it. The important
statement (possibly not always clear to non experts) is that *a
complexity class is just a set of problems*, usually characterized or
isentified by a specification of computing model and resources that
can solve them (though there may be other equivalent combinations). It
seem to me the OP's mistake was mainly to write **P** rather than
"*time polynomial*", given he was making analogy with *(un)decidable*, which
no one commented. Why?
babou
CC BY-SA 3.0
2014-06-05T16:00:17.420Z
@NieldeBeaudrap: good point! If I had actually paid attention when lookup up the definition of the complexity classes, I could have figured that out for myself. I should have picked my examples more carefully to avoid a debate on terminology :)
Rhymoid
CC BY-SA 3.0
2014-06-05T22:50:38.037Z
@babou, I have down-voted and voted to close as off-topic: there are basic misunderstandings as Niel mentioned and if they are fixed the question is trivial as obviously there weaker models. And if after that we further restrict our attention to polytime computable in reasonable/realistic models outside P then my answer would be Google for Complexity-Theoretic Church–Turing Thesis.
Kaveh
<cc.complexity-theory><computability><terminology>
Can complexities differ w.r.t. different computational models?
Rhymoid
# Can complexities differ w.r.t. different computational models?

(Asked by: username_0 on 2014-06-04)

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?

**Tags:** cc.complexity-theory, computability, terminology
> **Comments:**
> **username_1**: One should not confuse run-times ("can this model of computation solve this problem in polynomial time?") with complexity classes ("is this problem in **P**?"). The class **P** refers, by *definition*, to problems solvable in polynomial time on a Turing Machine (and poly-time equivalent models of computation). Other classes may represent polynomial-time computation in another model: **BPP** and **BQP** are examples of this, for (bounded-error solvabilty by) randomised and quantum Turing machines, for instance.  
> **username_2**: Nevertheless I think there's a useful question lurking underneath.  
> **username_3**: I am no complexity expert in any way. But my impression was that the question makes sense, though its statement may not use the right terminology.  Why the downvote? If the reason is that you consider it inappropriate for TCS: say so, at least. Or flag it for transfer to CS.  
> **username_3**: @SureshVenkat I commented at the same time you did. I liked his forward way of talking of undecidability with respect to a computational model (is that an accepted view, or is there a hidden trap?). Do you think you can rephrase the question in a better way?  I do not have the expertise to understand the subtleties of the issue, and I think I am missing the point made by Niel de Beaudrap's comment.  
> **username_2**: We don't usually rephrase an OP's question unless they ask for it themselves.  
> **username_1**: @Babou: the point is just that the set of problems solvable in polynomial time by different models of computation form different complexity classes — not a single class whose definition changes with the model. That is to say, if one wishes to speak about polynomial time algorithms in *different* models of computation, one should simply say so, and not try to shoehorn it into **P**-parlance.  
> **username_3**: @NieldeBeaudrap Thanks. I thought there was something more subtle to it. The important statement (possibly not always clear to non experts) is that *a complexity class is just a set of problems*, usually characterized or isentified by a specification of computing model and resources that can solve them (though there may be other equivalent combinations). It seem to me the OP's mistake was mainly to write **P** rather than "*time polynomial*", given he was making analogy with *(un)decidable*, which no one commented. Why?  
> **username_0**: @NieldeBeaudrap: good point! If I had actually paid attention when lookup up the definition of the complexity classes, I could have figured that out for myself. I should have picked my examples more carefully to avoid a debate on terminology :)  
> **username_4**: @babou, I have down-voted and voted to close as off-topic: there are basic misunderstandings as Niel mentioned and if they are fixed the question is trivial as obviously there weaker models. And if after that we further restrict our attention to polytime computable in reasonable/realistic models outside P then my answer would be Google for Complexity-Theoretic Church–Turing Thesis.  

---

## 2 answers

### Answer by username_2 on 2014-06-05. Score: 10 | Accepted answer

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](https://cstheory.stackexchange.com/a/22080/80) to [my earlier question](https://cstheory.stackexchange.com/questions/22079/provable-gaps-between-decision-tree-complexity-and-true-complexity) about decision tree complexity presents an example of an NP-hard problem (SUBSET SUM) that has polynomial decision tree complexity.

> **Comments:**
> **username_3**: It looks like there is a different word needed (different from *complexity*). I understood that Niel de Beaudrap was saying just the opposite. Complexity and complexity classes are independent from computational models. I wonder whether one should use here more the word *cost*, to measure the time, or space, or whatever needed, that depends on the computational model. See above my [comment to the question](http://cstheory.stackexchange.com/questions/23783#comment60518_23783)  
> **username_0**: My mistake was to assume a definition for the well-known complexity classes while I could just as easily have looked it up. I take Niel de Beaudrap's comments as an observation of that, with further clarification that complexity *classes* are defined with a precise model of computation in mind. Complexity is, however, still the right term.  

---

### Answer by username_5 on 2014-06-05. Score: 4

Another well known example of how a Turing complete computational model can lead to a time complexity blow-up is [2 Counter Automata (2CA)](http://en.wikipedia.org/wiki/Counter_automaton)

A 2CA is equipped with two registers that can store an unbounded nonnegative integer and can execute only simple instructions decrement/increment the counters, conditional jumps (after checking if a counter is zero), unconditional jump.
The input is placed in one of the two counters, so it must be represented in *unary*.

A 2CA can simulate an arbitrary Turing machine $M$ on input $x$ but only if its input is set to $2^x$. So every simulated tape operation of $M$ on $x$ requires exponential time.


---

