There\'s a lot of debate about what exactly the Church-Turing thesis is, but rou

Question

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 ?(f(n)) on a universal turing machine, then we should say its time complexity is ?(f(n)).

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

Explanation / Answer

Short answer

The thesis that all reasonable models of computation are polynomially-equivalent

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.