✦ LIBER ✦

On time hierarchies

✍ Scribed by W.J. Paul

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 386 KB
Volume: 19
Category: Article
ISSN: 0022-0000
DOI: 10.1016/0022-0000(79)90028-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On average time hierarchies

✍ Mikael Goldmann; Per Grape; Johan Håstad 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 531 KB

Tighter constant-factor time hierarchies

✍ Amir M. Ben-Amram 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 89 KB

For certain computational models, a constant-factor time hierarchy theorem is known, showing that a constant-factor difference in time bounds makes a difference in problem-solving power (unlike the situation with Turing machines). In this paper we apply the classic "translational technique" (padding

Some results on relativized deterministi

Some results on relativized deterministic and nondeterministic time hierarchies

✍ Shlomo Moran 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 576 KB

The Analytic Polynomial-Time Hierarchy

✍ Herbert Baier; Klaus W. Wagner 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 863 KB

Motivated by results on interactive proof systems we investigate an 3-V-hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the (arithmetic) polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every

A Turing machine time hierarchy

✍ Stanislav Žák 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 727 KB

Relating the bounded arithmetic and poly

Relating the bounded arithmetic and polynomial time hierarchies

✍ Samuel R. Buss 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 711 KB