✦ LIBER ✦

On average time hierarchies

✍ Scribed by Mikael Goldmann; Per Grape; Johan Håstad

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 531 KB
Volume: 49
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(94)90048-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On time hierarchies

✍ W.J. Paul 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 386 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

Time Average in Micromagnetism

✍ Gilles Carbou; Pierre Fabrie 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 371 KB

On maximizing the average time at a goal

✍ S. Demko; T.P. Hill 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 375 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