1
$\begingroup$

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".

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ How large is "very large"? They sorta have to be large to form a hard instance. $\endgroup$
    – Dmitri Urbanowicz
    Commented Aug 12, 2020 at 7:46
  • $\begingroup$ @DmitriUrbanowicz For example, in one similar question (can't find it), for two variables and three clauses, one of the weights was $11223$. $\endgroup$
    – DUO Labs
    Commented Aug 12, 2020 at 13:48
  • 1
    $\begingroup$ 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 $\endgroup$
    – Vor
    Commented Aug 13, 2020 at 12:33
  • $\begingroup$ @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. $\endgroup$
    – DUO Labs
    Commented Aug 13, 2020 at 13:07
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Dec 27, 2023 at 22:00

1 Answer 1

Reset to default
0
$\begingroup$

Note that FACTOR isn't known to be NP-complete.

Improve this answer
$\endgroup$
1
  • $\begingroup$ But can't you not still convert it into a 3-SAT instance? $\endgroup$
    – DUO Labs
    Commented Aug 12, 2020 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.