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 $\...
- 18.2k
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 ...
- 37.8k
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 ...
- 12.3k
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]...
- 196
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$ ...
- 23.1k
2
votes
pq factorization
Hart's one-line factorization algorithm can do it in 150 microseconds with my unoptimized implementation (in PARI/GP):
...
- 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 ...
- 12.3k
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 ...
- 3,263
Only top scored, non community-wiki answers of a minimum length are eligible