𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounded arithmetic and the polynomial hierarchy

✍ Scribed by Jan Krajíček; Pavel Pudlák; Gaisi Takeuti

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
706 KB
Volume
52
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Polynomial induction and length minimiza
Polynomial induction and length minimization in intuitionistic bounded arithmetic
✍ Morteza Moniri 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract It is shown that the feasibly constructive arithmetic theory IPV does not prove (double negation of) LMIN(NP), unless the polynomial hierarchy CPV‐provably collapses. It is proved that PV plus (double negation of) LMIN(NP) intuitionistically proves PIND(coNP). It is observed that PV + P

Epistemic entrenchment and arithmetical
Epistemic entrenchment and arithmetical hierarchy
✍ Petr Hájek 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 467 KB

Hfijek, P., Epistemic entrenchment and arithmetical hierarchy (Research Note), Artificial Intelligence 62 (1993) 79-87. If the underlying theory is sufficiently rich (e.g. like first-order arithmetic), then no epistemic entrenchment preorder of sentences is recursively enumerable. Consequently, the

The Analytic Polynomial-Time Hierarchy
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