Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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

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