All Questions
Tagged with computability-theory computational-number-theory
10 questions
5
votes
0
answers
187
views
Is there an effective way to compute the square root of an algebraic number?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,087
16
votes
2
answers
1k
views
Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,087
0
votes
1
answer
126
views
Integer quadratic representation subject to discriminant minimization algorithm
Let $f(x)=ax^2+bx+c$ and $f(x)=n$. Is there an algorithm to choose $a,b,c$ such that the discriminant is minimized? Where $a,b,c,n,x$ are all integers.
More concretely, is there an algorithm to find $...
1
vote
0
answers
152
views
Efficient deterministic algorithms of factorizing
My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.
Are there such algorithms that use poly$(n, \log q)$ bit operations?
I know ...
- 2,576
13
votes
1
answer
1k
views
An efficient isomorphism between finite fields
Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
- 2,576
2
votes
3
answers
476
views
How to define the input of computable function or Turing machine over real numbers
Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
- 3,094
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
8
votes
1
answer
1k
views
Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?
Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...
- 297
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
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