# 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 "big deal"? 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 "junk".

• How large is "very large"? They sorta have to be large to form a hard instance. Commented Aug 12, 2020 at 7:46
• @DmitriUrbanowicz For example, in one similar question (can't find it), for two variables and three clauses, one of the weights was $11223$. Commented Aug 12, 2020 at 13:48
• Don't expect "short" weights because SUBSET-SUM is weakly NPC and you have a pseudo-polynomial algorithm for it. The conversion from 3SAT is straightforward so you could also use hard 3SAT instances from datasets used in Sat competitions or use a constraint satisfaction program as a "preprocessor" to quickly generate SAT instances from FACTOR and then convert them to SUBSET SUM
– Vor
Commented Aug 13, 2020 at 12:33
• @Vor Since the conversion from SAT to 3SAT usually makes the problem harder, I wonder if I could just convert FACTOR to SAT, then to SUBSET-SUM. While it won't give me "short" weights, it would almost certainly give me an easier problem. Commented Aug 13, 2020 at 13:07
• What exactly is your question? I'm having a hard time telling what exactly the question is. I tried answering, but got the feedback that I wasn't answering the main question. It would also help to ask only one question, so there is no risk of confusion about what you are asking.
– D.W.
Commented Dec 27, 2023 at 22:00