All Questions
Tagged with computational-number-theory computer-science
8 questions
7
votes
1
answer
352
views
About the complexity of some operation involving integers
There are two integers: $A, B$. Given the below four allowed operations (and only them):
$A+1$, $A-1$, $\sqrt{A}$, $A^2$
Also, it is only allowed to take the square root of $A$ when this square root ...
- 71
3
votes
1
answer
167
views
Is factorial computation known to be in a class smaller than $FEXP$?
Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
- 13.9k
11
votes
1
answer
474
views
Representing field elements in a computer
I'm wondering if there is existing terminology to describe fields $F$ with the properties below. I don't have a completely precise description of the concept I have in mind, but hopefully this will be ...
- 1,021
3
votes
1
answer
382
views
Equivalence between Diffie Hellman and Discrete Log
For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...
user76479
2
votes
0
answers
106
views
Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?
Background
By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that
$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
- 1,389
3
votes
1
answer
386
views
Hermit H-machines
I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...
- 77
-1
votes
1
answer
1k
views
Transition Graph per alphabet? [closed]
How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
- 101
2
votes
1
answer
2k
views
How many cpus needed to check a 100 million digit prime number efficiently? [closed]
If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
- 123