Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/230160448467648512
edited tags; edited tags
Link
Kaveh
  • 22.5k
  • 4
  • 52
  • 112
Source Link
Xodarap
  • 1.5k
  • 1
  • 10
  • 17

Time complexity version of the Church-Turing Thesis

There's a lot of debate about what exactly the Church-Turing thesis is, but roughly it's the argument that "undecidable" should be considered equivalent to "undecidable by a universal turing machine."

I'm wondering if there's an analogous statement for time complexity, i.e. an argument that if some language is decided in $\Theta\left(f(n)\right)$ on a universal turing machine, then we should say its time complexity is $\Theta\left(f(n)\right)$.

This isn't equivalent to the CT thesis - e.g. quantum computers decide precisely those languages which are decidable in a non-quantum TM, but they may run that decision procedure more quickly.