Strong Church-Turing Thesis
The Strong Church-Turing Thesis says that any model of computation, be it the circuit model or something else, can be simulated by a probabilistic Turing machine with at most polynomial overhead.
# Sources
# Uses
- We hope that quantum computer will be able to violate this thesis, as there’s some Evidence for Quantum Computers to violate Strong Church-Turning Thesis.