I'm interested in simple step explanation of reduction from CNF SAT(preferably) / subset sum to decision problem mentioned in this answer and this topic.

E.g. given either CNF formula or set of integers, I want to encode it in the single number n.

Does 𝑛 have a divisor strictly in between its two largest prime factors?

I also want to know how significant are the drawbacks of randomization in this case, and can we rely on Cramer's theorem in the case of large input? Am I supposed to reduce the problem instance several times with different logarithms to get a deterministic output?


1 Answer 1


You would likely need a very powerful algorithm, such as SAT solver or other algorithm that is capable of placing NP-complete problems in polynomial time. In general, number theoretic decision problems are not known to be easy to prove to be NP-complete; if you had an algorithm for this, it would prove that your mentioned decision problem is NP-complete. One notable counter-example is the modular square root decision problem, which is known to be NP-complete. Interestingly, based on the properties of logarithms, certain "thorough enough" discrete logarithm problem algorithms could solve MSR, thereby establishing P = NP. (That doesn't mean DLP is NP-complete, though.)

  • $\begingroup$ There is a paper(linked in discussions) that proves this problem as NP-complete and describes polynomial time reduction from the subset sum problem to the search version of this problem. It also states that decision version exist, so I'm interested in the decision encoding. $\endgroup$ Aug 17 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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