All Questions
Tagged with theories-of-arithmetic computational-complexity
7 questions
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
- 4,713
21
votes
2
answers
1k
views
Is factorial definable using a $\Delta_0$ formula?
The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?
- 4,713
7
votes
0
answers
179
views
The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory
Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...
- 7,853
6
votes
1
answer
172
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 ...
CommunityBot
- 1
3
votes
2
answers
328
views
Efficient representations of natural numbers via arithmetical expressions
A given natural number $n \in \mathbb{N}$ has many representations
as expressions mixing other natural numbers and the operators and punctuation symbols
$\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...
- 1,545
4
votes
2
answers
924
views
Natural numbers of great kolmogorov complexity
Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...
- 5,502
3
votes
0
answers
771
views
Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
CommunityBot
- 1