Skip to main content
7 votes

NP-complete problems where the inputs are prime numbers

There are no known NP-complete problems whose input would consist of primes (or, say, $k$-tuples of primes, or even more complicated structures as long as they contain at least one prime of length $\...
Emil Jeřábek's user avatar
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 ...
Joshua Grochow's user avatar
3 votes
Accepted

Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?

In a practical sense, Levin search is not useful. It has an enormous constant factor (exponential in the length/size of the optimal factoring algorithm). This makes it of little use in practice. In ...
D.W.'s user avatar
  • 12.2k
3 votes
Accepted

Comparing Shor's and Regev's Quantum Factoring algorithm

First some background (that does not fit the comments section) since you asked for pointers: The continued fractions-based post-processing algorithm in Shor's order-finding algorithm [Shor94] [Shor97]...
Martin Ekerå's user avatar
2 votes

NP-complete problems where the inputs are prime numbers

I don't know if it has an official name, but this problem is NP-complete (actually it's a simple "number theory" reformulation of the exact cover by 3-sets problem): Given a set of $3n$ ...
Marzio De Biasi's user avatar
2 votes

pq factorization

Hart's one-line factorization algorithm can do it in 150 microseconds with my unoptimized implementation (in PARI/GP): ...
Charles's user avatar
  • 1,745
2 votes
Accepted

Would the following be an acceptable part of an algorithm if used for prime factorization

It's not cheating. The last step of an algorithm can certainly be: compute $n/p_1$ and check whether that is an integer and is prime. That's an allowable step in an algorithm and can be computed ...
D.W.'s user avatar
  • 12.2k
2 votes

Is prime-counting function #P-complete?

Some heuristic evidence: to the best of our knowledge $\pi(n)$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no ...
Geoffrey Irving's user avatar

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