11
votes

Accepted

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

$\let\itp\vartriangleright\def\mr{\mathrm}\DeclareMathOperator\dom{dom}\let\bez\smallsetminus\let\sset\subseteq$The weakened theory is much weaker than bounded arithmetic.
Let me denote the theory as $...

9
votes

Accepted

### Are the irrotational and solenoidal parts of a smooth vector field linearly independent?

$\newcommand\R{\mathbb R}\newcommand\na{\nabla}\newcommand\om{\boldsymbol{\omega}}\newcommand\si{\sigma}\newcommand\Ga{\Gamma}\newcommand\F{\mathbf F}\newcommand\x{\mathbf x}\newcommand\0{\mathbf 0}$...

7
votes

Accepted

### Intutionistic Robinson Arithmetic

Both are false. Consider the following Kripke model $M\vDash Q^e$ (in fact, it satisfies the intuitionistic version of $\mathrm{PA}^-$): it consists of two worlds $u,v$ such that $u$ sees $v$; the ...

7
votes

Accepted

### Bounded Arithmetic vs Complexity Theory

If $T_1$ and $T_2$ are theories corresponding to complexity classes $C_1$ and $C_2$ (resp.), then separation of $C_1$ from $C_2$ from $C_2$ implies separation of $T_1$ from $T_2$, but not necessarily ...

5
votes

### Bounded Arithmetic vs Complexity Theory

The arithmetic theories you're talking about typically have the property that the provably total functions are precisely the functions in some familiar complexity class.
So suppose that the provably ...

5
votes

Accepted

### Weak Bounded Arithmetics

$\def\dotminus{\mathbin{\dot{-}}}$Actually, there are a number of papers on variants of $S^0_2$, $T^0_2$, and other theories axiomatized by $\Sigma^b_0$ (sharply bounded) schemata, in particular:
[1] ...

4
votes

Accepted

### Logical complexity of hard functions conjectures

As given, $\phi_1$ and $\phi_2$ are $\Sigma_2$.
They cannot be shown equivalent to $\Pi_2$ statements by any proof that relativizes. This follows by the same argument as in Examples of $G_\delta$ ...

4
votes

Accepted

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

All these theories coincide: if exponentiation is total, a bounded formula is equivalent on any bounded domain to a sharply bounded formula (with an exponentially large parameter), hence bounded ...

3
votes

Accepted

### Bounded Arithmetic and Counting

Q1: Yes. The paper you linked to in the question actually proves the theorem for every pair of natural numbers $p,q$ such that $p$ has a prime factor that does not divide $q$ (in other words, $p$ does ...

1
vote

### Provability in $S^1_2$

(Note: I'm not actually familiar with $S^1_2$ and the related formalism, but I'm going by your description of the theory, and I have been already thinking about related questions in an informal way.)
...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

bounded-arithmetic × 24lo.logic × 22

computational-complexity × 11

model-theory × 10

proof-theory × 6

theories-of-arithmetic × 5

constructive-mathematics × 3

reference-request × 2

set-theory × 1

prime-numbers × 1

sequences-and-series × 1

computability-theory × 1

open-problems × 1

alternative-proof × 1

wave-equation × 1

intuitionism × 1

periodic-functions × 1

ultrafinitism × 1

linear-matrix-inequalities × 1

proof-complexity × 1