✦ LIBER ✦

Separation of deterministic, nondeterministic and alternating complexity classes

✍ Scribed by Andrej Bebják; Ivana Štefáneková

Book ID: 107948688
Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 907 KB
Volume: 88
Category: Article
ISSN: 0304-3975
DOI: 10.1016/0304-3975(91)90379-g

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Relations among simultaneous complexity

Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

✍ Shigeki Iwata; Takumi Kasai; Etsuro Moriya 📂 Article 📅 1993 🏛 Springer-Verlag 🌐 English ⚖ 609 KB

Limitations on Separating Nondeterminist

Limitations on Separating Nondeterministic Complexity Classes

✍ Rackoff, Charles W.; Seiferas, Joel I. 📂 Article 📅 1981 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 484 KB

A note on deterministic and nondetermini

A note on deterministic and nondeterministic time complexity

✍ Shimon Even; Timothy J. Long; Yacov Yacobi 📂 Article 📅 1982 🏛 Elsevier Science ⚖ 346 KB

Separating NE from some nonuniform nonde

Separating NE from some nonuniform nondeterministic complexity classes

✍ Bin Fu; Angsheng Li; Liyu Zhang 📂 Article 📅 2010 🏛 Springer US 🌐 English ⚖ 465 KB

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

Space-bounded complexity classes and ite

Space-bounded complexity classes and iterated deterministic substitution

✍ Peter R.J. Asveld 📂 Article 📅 1980 🏛 Elsevier Science ⚖ 838 KB