# Questions tagged [bounded-arithmetic]

The tag has no usage guidance.

23 questions
Filter by
Sorted by
Tagged with
131 views

### Does this hierarchy of fragments of $I \Sigma_1$ collapse?

Does anyone know whether the following hierarchy of fragments of $\mathrm{I} \Sigma_1$ (or rather $\mathrm{I} \Pi_1$) collapses or not? Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...
1 vote
181 views

• 6,475
720 views

### What is the consistency strength of this theory?

Language: first-order logic Primitives: $=, S, \in$ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation). Axioms: those of identity ...
• 10.5k
280 views

### Provability in $S^1_2$

What are some examples of natural true statements of the form $∀n φ(n)$ ($φ$ is a polynomial time computation/test) that are unprovable in $S^1_2$? Examples may be unconditional or dependent on ...
• 6,475
224 views

### Does Bounded Arithmetic, $I\Delta_0$, prove the Recursion Theorem?

Compare my question Does Robinson Arithmetic already entail the Recursion Theorem. I would find it desirable and interesting if $I\Delta_0$ could be extended with a comprehension principle CP stating ...
• 3,544
169 views

### Logical complexity of hard functions conjectures

Let $\phi_1$ and $\phi_2$ be the following statements: $\phi_1:$ There is a function $f:\{0,1\}^*\to\{0,1\}$ computable in $E$ that has circuit complexity $2^{\Omega(n)}$. $\phi_2:$ There is a ...
• 1,689
126 views

### Collapsing the Intuitionistic Bounded Arithmetics Hierarchy

Let $iT$ be the intuitionistic first order theory with non-logical axioms of classical first order theory $T$. Theorem1. If $\mathsf{T^i_2}\vdash \mathsf{T_2}$, then $\mathsf{T^i_2}$ proves that the ...
• 1,689
124 views

### On subtheories of $\mathsf{T_2+EXP}$

By famous KPT theorem, if $\mathsf{T^i_2}\vdash \mathsf{T^j_2}$ for some $0<i<j$, then the polynomial hierarchy collapses. So it seems this bounded arithmetic hierarchy does not collapse. Also, ...
• 1,689
218 views

### Bounded Arithmetic and Counting

Let $\mathcal{L}=\{0,S,+,\cdot,=,<,X,R,S\}$ be the language of arithmetic with three additional predicate symbols $X(v)$, $R(v,u)$ and $S(v,u)$. Let $\phi(x),\psi(x,y)$ and $\eta(x,y)$ be formulas ...
• 1,689
192 views

### $P=NP$ and provability of family of propositional formulas

Let $\mathcal{L}'=\{+,\cdot,0,S,=,<,||,\#,R\}$ be the lanugage of bounded arithmetic with a $k$-ary relation $R$. For every bounded sentence $\phi({\bf\bar{n}})$ in $\mathcal{L}'$ define ...
• 1,689
266 views

### Collapsing the Linear Time Hierarchy and finite axiomatizability of bounded arithmetic

It is well known that if ${\bf T_2}$ (or $I\Delta_0+\Omega_1$) is finitely axiomatizable, then the Polynomial Hierarchy collapses. Q. Is there any similar relation between $I\Delta_0$ and Linear ...
• 1,689
63 views

• 103
288 views

### Weak Bounded Arithmetics

Let $\Sigma^b_i$ and $\Pi^b_i$ formulas be bounded formulas defined by Buss in language of $L_b$. $PIND(\phi(x))$ is the formula: \phi(0)\land \forall x(\phi(\left \lfloor \frac{x}{2} \right \...
• 1,689
688 views

### Intutionistic Robinson Arithmetic

By Friedman translation $HA$ and $PA$ prove the same $\Pi_2$ formulas. Is it true for Intutionistic Robinson arithmetic(Robinson axioms with intutionistic logic) and classic Robinson arithmetic? ...
• 1,689
1 vote
87 views

### models of $I\exists^+_1$

$\phi$ is a $\exists^+_1$ formula iff it is in language of arithmetic and does not have $\forall$,$\neg$ and $\rightarrow$, therefore $I\exists^+_1$ is theory of $Q$+induction axioms for $\exists^+_1$ ...
• 1,689
135 views

### Does every model of $I\Delta_0$ has an end extension to a model of $I\Delta_0+\Omega_1$?

Does every model of $I\Delta_0$ has an end extension to a model of $I\Delta_0+\Omega_1$? In End extensions of models of linearly bounded arithmetic paper the author said this problem is open. I want ...
• 1,689