𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Herbrandizing search problems in Bounded Arithmetic

✍ Scribed by Jiří Hanika

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
172 KB
Volume
50
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

We study search problems and reducibilities between them with known or potential relevance to bounded arithmetic theories. Our primary objective is to understand the sets of low complexity consequences (esp. Σ b 1 or Σ b 2 ) of theories S i 2 and T i 2 for a small i, ideally in a rather strong sense of characterization; or, at least, in the standard sense of axiomatization. We also strive for maximum combinatorial simplicity of the characterizations and axiomatizations, eventually sufficient to prove conjectured separation results. To this end two techniques based on the Herbrand's theorem are developed. They characterize/axiomatize Σ b 1 -consequences of Σ b 2 -definable search problems, while the method based on the more involved concept of characterization is easier and gives more transparent results. This method yields new proofs of Buss' witnessing theorem and of the relation between PLS and Σ b 1 (T 1 2 ), and also an axiomatization of Σ b 1 (T 2 2 ).

📜 SIMILAR VOLUMES

Arithmetic Progressions in Sequences wit
Arithmetic Progressions in Sequences with Bounded Gaps
✍ Tom C Brown; Donovan R Hare 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 528 KB

Let G(k, r) denote the smallest positive integer g such that if 1=a 1 , a 2 , ..., a g is a strictly increasing sequence of integers with bounded gaps a j+1 &a j r, 1 j g&1, then [a 1 , a 2 , ..., a g ] contains a k-term arithmetic progression. It is shown that G(k, 2) > -(k & 1)Â2 ( 43 ) (k&1)Â2 ,

An unexpected separation result in Linea
An unexpected separation result in Linearly Bounded Arithmetic
✍ Arnold Beckmann; Jan Johannsen 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB

The theories S i 1 (α) and T i 1 (α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i, a Σ b i+1 (α)-formula TOP i (a), which expresses a form of the t

Approximation bounds for Black Hole Sear
Approximation bounds for Black Hole Search problems
✍ Ralf Klasing; Euripides Markou; Tomasz Radzik; Fabiano Sarracco 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 329 KB

## Abstract A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of

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