Time hierarchy theorem: Difference between revisions

Revision as of 04:32, 3 October 2005

Revision as of 04:34, 3 October 2005

Line 7:

===Statement===

For any [[time constructible]] function <math>t: N \rightarrow N</math>, there exists

a language <math>A</math> that is decidable in time <math>O(t(n))</math> but not in time

<math>o(t(n)/\log t(n))</math>.