Dataset of Hard Instances of SUBSET-SUM I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-SUM, in which there are hard instances that if solved, would be a &quot;big deal&quot;? I found this, but they don't seem to be unsolved.
One way would to take the RSA numbers, convert them to 3-SAT, then convert to SUBSET-SUM, but the weights generated are very large. Maybe there's a way to convert FACTOR (the special case of two prime factors, to be specific) directly to SUBSET-SUM without having to go through 3SAT (not the main question; just a thought)?
For the RSA numbers in particular, we know how long each non-trivial factor is: $\frac k2$, where $k$ is the number of bits of the number $n$. Maybe we can use that to shrink the number of variables to only $n$, without having to make extra variables and unnecessarily fill the problem with &quot;junk&quot;.
Note that FACTOR isn't known to be NP-complete.