𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On two questions about feasibly constructive arithmetic

✍ Scribed by Morteza Moniri

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
71 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

IPV is the intuitionistic theory axiomatized by Cook's equational theory PV plus PIND on NP‐formulas. Two extensions of IPV were introduced by Buss and by Cook and Urquhart by adding PIND for formulas of the form A(x) ∨ B, respectively ¬¬A(x), where A(x) is NP and x is not free in B. Cook and Urquhart posed the question of whether these extensions are proper. We show that in each of the two cases the extension is proper unless the polynomial hierarchy collapses.

πŸ“œ SIMILAR VOLUMES

On two questions about circular choosabi
On two questions about circular choosability
✍ Serguei Norine πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 122 KB

## Abstract We answer two questions of Zhu on circular choosability of graphs. We show that the circular list chromatic number of an even cycle is equal to 2 and give an example of a graph for which the infimum in the definition of the circular list chromatic number is not attained. Β© 2008 Wiley Pe