4
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Jun 5, 2014 at 8:46
  • 3
    $\begingroup$ Nevertheless I think there's a useful question lurking underneath. $\endgroup$
    – Suresh Venkat
    Jun 5, 2014 at 9:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    Jun 5, 2014 at 10:00
  • $\begingroup$ @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. $\endgroup$
    – babou
    Jun 5, 2014 at 10:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – Niel de Beaudrap
    Jun 5, 2014 at 11:34

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – babou
    Jun 5, 2014 at 13:23
  • $\begingroup$ 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. $\endgroup$
    – Rhymoid
    Jun 5, 2014 at 15:56
4
$\begingroup$

Another well known example of how a Turing complete computational model can lead to a time complexity blow-up is 2 Counter Automata (2CA)

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.