Questions tagged [bounded-arithmetic]
The bounded-arithmetic tag has no usage guidance.
23
questions
4
votes
1
answer
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
0
answers
181
views
Induction on open formulas vs. Induction on $\Pi_1$ formulas
There are infinitely many extension to Robinson's $Q$ arithmetic many of which are defined by adding an axiom schema of induction for particular set of formulas.
I am confused about the theory $\text{...
- 173
5
votes
0
answers
258
views
Finite axiomatizability and $\mathrm{PA^{top}}$
Is $\mathrm{PA^{top}}$ finitely axiomatizable? If not, does it have a finitely axiomatizable extension (allowing new predicates but not new variable types) that has arbitrarily large finite models?
$\...
- 6,475
6
votes
1
answer
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
6
votes
1
answer
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
0
votes
0
answers
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
6
votes
1
answer
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
5
votes
0
answers
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
3
votes
1
answer
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
2
votes
1
answer
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
2
votes
0
answers
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
10
votes
0
answers
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
3
votes
0
answers
63
views
Equational theory for resolution proof system
Is there any equational theory $T$ like $PV$ with following properties:
If $T\vdash f=g$ for terms $f$ and $g$, translation of $f=g$ to propositional formulas has polynomial resolution proof.(like $...
- 1,689
10
votes
2
answers
628
views
Bounded Arithmetic vs Complexity Theory
In this post, when I talk about bounded arithmetic theories,
I mean the theories of arithmetic according to "Logical Foundations of Proof Complexity", which capture the complexity classes between $AC^...
- 103
4
votes
1
answer
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
12
votes
1
answer
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
0
answers
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
8
votes
0
answers
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
8
votes
0
answers
196
views
Kripke models of $HA$
Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$.
What is the strongest theory of arithmetic like $T$ such that for
every kripke model $K\...
- 1,689
4
votes
3
answers
354
views
End Extension models of $I\Delta_0$
Recently I'm thinking about question below, but I can not prove or disprove it.
Is it true that for every model $M\models I\Delta_0$ there exists a
model $M'\models PA$ such that $M'$ is end ...
- 1,689
9
votes
3
answers
617
views
Model-theoretic accounts of feasibility in bounded arithmetic and related systems
Various weak theories of arithmetic have been partially motivated by a concern with numbers (or functions/proofs) that are feasible. This concern is sometimes connected to an interest in strictly ...
- 91
14
votes
2
answers
696
views
Unboundedness of primes in bounded arithmetic
Wilkie's well known question asks whether $I\Delta_{0}$ proves the unboundedness of primes. We know that by adding a sentence to $I\Delta_{0}$ which says "the exponential function is total", it is ...
- 1,403
8
votes
1
answer
420
views
Is there exponentiation in "sufficiently large" models of $I\Delta_{0}$?
Let $L_{E}$ be the language of discretely ordered rings together with an extra predicate symbol $E$. The system $A$ consists of the axioms of $I\Delta_{0}$ (basic arithmetic plus induction for bounded ...
- 521