Revision as of 16:23, 28 August 2021 edit FG0711 (talk \| contribs) 144 edits →Proof ← Previous edit		Revision as of 16:27, 28 August 2021 edit undo FG0711 (talk \| contribs) 144 edits →Proof: We do not "construct" the machine K. It exists by definition. Next edit →
Line 118: so that if we substitute 2''n'' + 1 for ''m'', we get the desired result. Let us assume that ''H<sub>f</sub>'' is in this time complexity class, and we will attempt to reach a contradiction. If ''H<sub>f</sub>'' is in this time complexity class, itthen ~~means~~there weexists ~~can construct some~~a machine ''K'' which, given some machine description [''M''] and input ''x'', decides whether the tuple ([''M''], ''x'') is in ''H<sub>f</sub>'' within :<math>\mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right). </math>

Time hierarchy theorem: Difference between revisions