3
$\begingroup$

Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?

We assume that we know the algorithm solving the problem of Subset Sum with complexity: $n ^ 4 \cdot m ^ 4$ (for example), where $n$ is the number of elements in the set, and $m$ is the size of the largest element (absolute value).

Theoretically, we can perform a reduction from FACT to 3SAT and from 3SAT to Subset Sum.

However, the reduction from 3SAT to Subset Sum has a problem.

After such a reduction (from 3SAT), the numbers in Subset Sum are very large.

For example, let's see page number four in this document.

The search number is: $11133$ for a logic function composed of only three variables and two clauses.

The number we are looking for is always around $ 10 ^ {v + c} $ where $v$ is number of variables and $c$ is number of clauses.

We can solve the Subset Sum in time $n ^ 4 \cdot m ^ 4$ but if $m$ grows exponentially, then the whole grows exponentially.

Is there any way to solve this?

---- Update:

I found this answer. It directs me to the conclusion that there is no classic decimal notation. Maybe this is some unary notation? Do I presume well? I am concerned, however, about the value of "3" in $k$ (the last row in the table on the fourth page in document). How can we encode it in decimal / binary form?

$\endgroup$
  • $\begingroup$ What do you mean by "size of the largest element"? Do you mean the number of bits needed to represent the largest element, or the value of the largest element? (Another way to ask is: are the elements of the set presented in the input in unary or in binary?) $\endgroup$ – D.W. Feb 2 '18 at 17:31
  • $\begingroup$ Anyway, I suggest you look at the definition of NP-completeness, and then use the fact that Subset Sum is NP-complete and FACT is in NP. $\endgroup$ – D.W. Feb 2 '18 at 17:32
  • $\begingroup$ Size of largest element is value of element eg. 7, but is not in unary 1111111. It is also not the number of bits. This is a normal value. $\endgroup$ – Aurelio Feb 2 '18 at 17:38
  • $\begingroup$ We do not expect subset sum to have a polynomial time algorithm. $\endgroup$ – Yuval Filmus Feb 2 '18 at 22:57
6
$\begingroup$

Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum.

To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction. (Implicitly, we get a reduction from FACT to SAT by Cook's theorem, and from the proof of NP-completeness for Subset Sum you will be able to extract a reduction from SAT to Subset Sum. Now compose those two reductions.)

$\endgroup$

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.