𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A sorting network in bounded arithmetic

✍ Scribed by Emil Jeřábek

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
300 KB
Volume
162
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Herbrandizing search problems in Bounded
Herbrandizing search problems in Bounded Arithmetic
✍ Jiří Hanika 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB

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

A bounded arithmetic AID for Frege syste
A bounded arithmetic AID for Frege systems
✍ Toshiyasu Arai 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 303 KB

In this paper we introduce a system AID (alogtime inductive deÿnitions) of bounded arithmetic. The main feature of AID is to allow a form of inductive deÿnitions, which was extracted from Buss' propositional consistency proof of Frege systems F in Buss (Ann. Pure Appl. Logic 52 (1991) 3-29). We show

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