2022 Developer Survey is open! Take survey.
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+\...
user avatar
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 $|$, $+$...
user avatar
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 ...
user avatar
18 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 1,945
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 13.1k
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 ...
user avatar
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 ...
user avatar
  • 10.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 ...
user avatar
8 votes

n irrational number whose digits are pseudo-random: conceptual mismatch?

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of ...
user avatar
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$.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 1,855
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 ...
user avatar
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 ...
user avatar
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{...
user avatar
  • 26.4k
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 (...
user avatar
  • 5,963
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 \...
user avatar
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 ...
user avatar
  • 7,459
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
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 [...
user avatar
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....
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
  • 5,963
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 ...
user avatar
  • 10.3k

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