𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on deterministic and nondeterministic time complexity

✍ Scribed by Shimon Even; Timothy J. Long; Yacov Yacobi

Book ID
114037620
Publisher
Elsevier Science
Year
1982
Weight
346 KB
Volume
55
Category
Article
ISSN
0019-9958

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A hierarchy for nondeterministic time co
A hierarchy for nondeterministic time complexity
✍ Stephen A. Cook πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 515 KB

We prove the following theorem in this paper: For any real numbers rl, r2, 1 ~ rl ~ r2, there is a set .4 of strings which has nondeterministic time complexity n\*2, but not nondeterministic time complexity n\*l. The computing devices are nondeterministic multitape Turing machines.

Relationships between nondeterministic a
Relationships between nondeterministic and deterministic tape complexities
✍ Walter J. Savitch πŸ“‚ Article πŸ“… 1970 πŸ› Elsevier Science 🌐 English βš– 816 KB

The amount of storage needed to simulate a nondeterministic tape bounded Turing machine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic [L(n)]2-tape bounded Turing machi