27
votes
Accepted
Deciding whether an interval contains a prime number
Disclaimer: I'm not an expert in number theory.
Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\...
- 1,134
21
votes
Accepted
Decidability of diophantine equations over {=, +, gcd}
($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$...
- 14.9k
18
votes
Accepted
Is Hartmanis-Stearns conjecture settled by this article?
First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".
Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
- 6,908
17
votes
Easy problems with hard counting versions
A very nice and simple example from Graph Theory is counting the number of Eularian circuits in an undirected graph.
The decision version is easy (... and the Seven Bridges of Königsberg problem has ...
- 22.3k
17
votes
Easy problems with hard counting versions
One interesting example from number theory is expressing a positive integer as a sum of four squares. This can be done relatively easily in random polynomial time (see my 1986 article with Rabin at ...
- 6,908
17
votes
Accepted
Is there a natural problem on the naturals that is NP-complete?
This problem has a variation with a single integer input:
Does $n$ have a divisor strictly in between its two largest prime
factors?
The idea is to use the same randomized reduction from subset ...
- 550
11
votes
Is square removal easier than factoring?
We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard.
It is obvious, that if we can factor $n$, we can also compute square removal of $n$.
The ...
- 211
10
votes
Accepted
Is square removal easier than factoring?
I believe no polynomial algorithm is known.
According to a paper this is used in at least one cryptosystem:
Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA
cryptosystem. We ...
- 1,955
10
votes
Base-k representations of the co-domain of a polynomial - is it context-free?
Of course $k \geq 2$ here.
There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.
As far as I know, ...
- 6,908
9
votes
Accepted
Easy problems with hard counting versions
Here's a truly excellent example (I may be biased).
Given a partially ordered set:
a) does it have a linear extension (i.e., a total order compatible with the partial order)? Trivial: All posets ...
- 342
9
votes
Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?
There are essentially only two algorithms that I'm aware of:
Use repeated-squaring, along the lines you mentioned.
Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder ...
- 10.5k
9
votes
Accepted
Factoring assuming smoothness of some numbers
See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time ...
- 6,908
9
votes
Accepted
A curious statement in an old blog
I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your ...
- 13.3k
9
votes
Decidability of diophantine equations over {=, +, gcd}
A something that might be too long for a comment, based on the previous answer by Emil.
In the case you are interested in the complexity of such a logic, consider reading LICS'2015 paper by Joël ...
- 1,110
7
votes
complexity of greatest common divisor (gcd)
Somewhat late in the day but the following paper by Allender, Saks, Shparlinski proves that (among other lower bounds) that GCD is not in $\mathsf{AC}^0$ or $\mathsf{AC}^0[p]$ for any prime $p$.
- 2,267
7
votes
Formalizing the "no formula for primes" intuition
[Certainly not a complete answer, but too long for a comment]
Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were ...
- 35.9k
6
votes
Accepted
Comparing two products of lists of integers?
(I understand the description of the problem so that the input numbers are bounded by a constant, so I will not track dependence on the bound.)
The problem is solvable in linear time and logarithmic ...
- 14.9k
6
votes
Easy problems with hard counting versions
Concerning your second question, problems such as Monotone-2-SAT (deciding of the satisfiability of a CNF-formula having at most 2 positive literals by clause) is completely trivial (you just have to ...
- 1,854
6
votes
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
This is impossible. No finite number of bits of $f(a_0,\dots,a_n)$ suffices to determine any of $a_0,\dots,a_n$; in fact, any nondegenerate real interval contains the values $f(a_0,\dots,a_n)$ for ...
- 14.9k
6
votes
Accepted
What is a known sequence for which being constant is not provable?
Let $T$ be a reasonble theory of arithmetic, say $\mathrm{PA}$. Consider the sequence
$$f(m) =
\begin{cases}
1 & \text{if $m$ encodes a proof of $\vdash_T 0 = 1$} \\
0 & \text{otherwise}
\end{...
- 26.8k
5
votes
Easy problems with hard counting versions
From [Kayal, CCC 2009]: Explicitly evaluating annihilating polynomials at some point
From the abstract: ``This is the only natural computational problem where
determining the existence of an object (...
- 5,973
5
votes
Which complexity class does this number theory problem belong to?
Added later: As noted in the comments, the NP upper bound is trivial if a, b, and c are positive, as was asked.
Theorem 1.2 in this paper shows that deciding if a given diophantine equation in two ...
- 7,509
5
votes
Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$
Terry Tao's answer on MathOverflow.
5
votes
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
Consider the function $T: \mathbb N \rightarrow \mathbb N$, where $T(n)=n/2$ when $n$ is even and $T(n)=n+1$ when $n$ is odd. Then it is known that for any $n \in \mathbb N$, there exists a $k \in \...
- 515
5
votes
Accepted
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [...
- 35.9k
4
votes
How to check if a number is a perfect power in polynomial time
Somehow, I can show that the binary search algorithm is $O(lg~n \cdot (lg~lg~n)^2)$.
Firstly, $a^b = n$, there is $b<lg~n$.
Binary Search Algorithm:
For each $b$, we use binary search to find ...
- 141
4
votes
Downward self-reducibility of factorization
The state of the art here is: We can decide primality in polynomial time, but the fastest, general-purpose algorithm to $\underline{\rm find}$ the factors of an n-bit composite integer takes time $\...
- 5,973
4
votes
Accepted
Two rectangles whose sum of areas is given
Assume all integers involved are even. This can be ensured by multiplying $P$ by 4. Here is an idea that should speed up the search. Let $p = \left\lceil\sqrt{P}\right\rceil$. If $p*p = P$ we are done....
- 9,566
4
votes
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
If you know that the $a_i$'s are all not too large, and you have a good approximation to $f(a_0,\dots,a_n)$, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the ...
- 10.5k
3
votes
Accepted
Relation between transcendental numbers and computational complexity?
One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number ...
- 35.9k
Only top scored, non community-wiki answers of a minimum length are eligible