3
$\begingroup$

The Time Hierarchy Theorem is a basic result in computational complexity, stating that Turing Machines that can run for longer time (i.e., $f(n)$) are able to decide more languages than Turing Machines that run in less time (i.e., $o(f(n)/\log n)$).

The Blum-Shub-Smale (BSS) algebraic model of computation is a uniform model of computation. Therefore, it is natural to ask if there is a similar time (or space) hierarchy theorem for this model. That is, showing that with more time, an algorithm in the BSS model can compute more than an algorithm that runs in less time in this model.

Is such an hierarchy result known?

$\endgroup$
  • $\begingroup$ Watch the HOTT lectures. cs.cmu.edu/~rwh/courses/hott $\endgroup$ – Chad Brewbaker Jan 24 '14 at 20:39
  • $\begingroup$ Thanks. But how is it related? $\endgroup$ – Dilworth Jan 25 '14 at 5:11
  • $\begingroup$ Harper goes into why Turing Machine based models are an inadequate model for many complexity problems. $\endgroup$ – Chad Brewbaker Jan 27 '14 at 17:41
  • $\begingroup$ I'd have to check the details carefully, but I'm fairly certain that the same diagonalization proof that works in the boolean case should work in the BSS model (with very slight modifications - e.g. about how to encode multiple real numbers into one). $\endgroup$ – Joshua Grochow Jan 28 '14 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.