✦ LIBER ✦

Tighter constant-factor time hierarchies

✍ Scribed by Amir M. Ben-Amram

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 89 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00253-9

No coin nor oath required. For personal study only.

✦ Synopsis

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) to these hierarchies and show that they are tighter than indicated by the previous proofs.

📜 SIMILAR VOLUMES

On time hierarchies

✍ W.J. Paul 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 386 KB

On average time hierarchies

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

Tighter time bounds on fault-tolerant br

Tighter time bounds on fault-tolerant broadcasting and gossiping

✍ Luisa Gargano 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 751 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