Tagged Questions
1
vote
0answers
19 views
Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)
I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
1
vote
0answers
44 views
Is discrete ultralogarithm harder than discrete logarithm?
Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing
$g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
0
votes
0answers
48 views
Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?
In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I
asked:
we treat all inputs and intermediate results and
final outputs as ...
0
votes
2answers
43 views
Can all programs be modeled as operations of elementary arithmetic operations on inputs?
In mathematics and computabiltiy theory, we treat
all inputs and intermediate results and final
outputs as natural number. While algorithms/programs themselves are considered natural
numbers, here we ...
1
vote
2answers
38 views
In complexity, Is the relationship between P and R known?
The relationship between P and NP is unknown; However, we can ask an "easier" question, what is the relationship between P and R (=decidable languages)? In other words, is there a (decidable) problem ...
4
votes
2answers
231 views
What is the relationship between ZFC and Turing machine?
I did not learn Logic properly but so far I understand that proof systems can be viewed as a kind of machine. For proof system, ZFC seems to be the most powerful one that we use so far. Similarly, for ...
4
votes
2answers
176 views
Is there a function that only generates primes?
The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$?
I'm having difficulty specifying exactly what I want "nice" to mean, ...
2
votes
1answer
40 views
IF a language L logspace reduces to SAT, does L
If a language L logspace reduces to SAT, does L also reduce to SAT in polynomial time?
1
vote
2answers
53 views
What is this number $k$?
I'm reading A first Course on Logic, (Hedman).
An algorithm is said to be polynomial-time if there is some number
$k$ so that, given any input of size n, the algorithm reaches it's
conclusion ...
2
votes
2answers
86 views
Solovay Randomness
Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$.
...
2
votes
2answers
139 views
the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy
The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
1
vote
2answers
185 views
Is Turing completeness monotone with respect to Cook reductions?
I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example:
The language of Boolean expressions is Turing complete; Does this imply that ...
2
votes
1answer
79 views
Puzzle: Generate the Highest Bounded Number Using a Limited Number of Characters
A friend and I were sitting in our cubes at work and trying to create the greatest bounded number we could using only a few characters.
We came up with $A(G,G)$, which is the Ackermann function with ...
2
votes
1answer
90 views
Sipser's definition of a space constructable function
I have a problem with definition of space constructable function.
As I understood we use this definition just for simplification of further proofs and idea behind this definition is very clear, but ...
