A Note on Square Rooting of Time Functions of Turing Machines.
Saved in:
| Title: | A Note on Square Rooting of Time Functions of Turing Machines. |
|---|---|
| Authors: | Lipton, Richard J., Ogihara, Mitsunori, Zalcstein, Yechezkel |
| Source: | Theory of Computing Systems. May2003, Vol. 36 Issue 3, p295. 5p. |
| Subjects: | Machine theory, Square root, Mathematical functions, Mathematics |
| Abstract: | This article focuses on square rooting of time functions of Turning machines. It studies the conjecture that for all nondeterministic time functions T the square root of T is equivalent to the time function of a nondeterministic Turning machines. Mathematical studies show that deterministic version of this conjecture is false. |
| Database: | Engineering Source |
Be the first to leave a comment!
