Skip to main content
2 of 2
edited tags; edited tags
Kaveh
  • 22.5k
  • 4
  • 52
  • 112

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.

Xodarap
  • 1.5k
  • 1
  • 10
  • 17