In Theoretical Computer Science, which one is more important? Computability of a problem or Complexity of a problem?

  • 2
    $\begingroup$ What do you mean with "more important"? $\endgroup$ – Vor Oct 27 '13 at 10:51
  • $\begingroup$ Which one leads to best solution! $\endgroup$ – Andy Oct 27 '13 at 11:29
  • 1
    $\begingroup$ What do you mean with "leads to best solution" :-) ? $\endgroup$ – Vor Oct 27 '13 at 11:46

Both computability and complexity are theoretical abstractions. A theoretical abstraction is most useful, if the gap between theory and practice is small.

  1. It is well known that there is a large gap between a problem whose solutions is computable in theory, and one whose solution is computable in practice. Complexity theory managed to shrink that gap considerably, to the point where the remaining gap is caused by factors like cache behavior, parallelization, large scale distribution and similar advanced practical issues.

  2. Computability theory has been able to prove that certain problems can't be solved. One might believe that there can't be any gap between theory and practice here, but this is not the case. It seems like Gödel's incompleteness theorems from 1931 would prove that the consistency of the Peano axioms can't be decided. However, Gentzen proved the consistency of the Peano axioms in a paper published in 1936. I know that there is a nice theoretical explanation for this, but I'm (still) unable to judge the practical consequences, and I guess I'm not alone in this.

  3. Complexity theory still struggles to rigorously prove lower bounds for most important practical problems, even so it slowly advances in this direction. One may question whether these theoretical lower bounds are important at all, because we have no guarantee that the practical lower bounds have to respect these theoretical bounds. However, it turns out that the practical lower bounds closely match the theoretical lower bounds, so that this objection is unfounded in practice.

  4. The above comparison might suggest that computability theory is not much use in practice compared to complexity theory. However, things like the Chomsky hierarchy and a bunch of other similarly useful results should easily disprove this suspicion.

| cite | improve this answer | |

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