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+\...
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 $|$, $+$...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 \...
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 [...
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....
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 ...

Only top scored, non community-wiki answers of a minimum length are eligible