Definition
Extended Church-Turing Thesis
Every reasonable formal model of an algorithm is equivalent to the SIMPLE programming language up to polynomial overhead in time.
For space complexity, stronger restrictions are partly needed.
Extended Church-Turing Thesis
Every reasonable formal model of an algorithm is equivalent to the SIMPLE programming language up to polynomial overhead in time.
For space complexity, stronger restrictions are partly needed.