1
$\begingroup$
  1. If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded knapsack problems since two factors can be viewed as one value, say within the set for the knapsack problem, and the other being the number of copies of the first factor?

    FACTOR 15; 3, 5

    Unbounded KNAPSACK with value of 15 and the set of all integers; {5,5,5} andor {3,3,3,3,3}

  2. Would this mean FACTOR was NP-Complete?

  3. Would solving unbounded knapsack problems in polynomial time in this way prove P=NP?

$\endgroup$
4
$\begingroup$

(1) NP-complete only contains problems that can be answered by Yes or No, which are called decision problems. So FACTOR is not an NP-complete problem even your reduction is correct. In fact, if your reduction were correct, it proves that FACTOR is NP-hard.

(2) If you want to prove the NP-hardness of FACTOR by reducing UKP (unbounded knapsack problem) to it, you should find an integer $M$ (in polynomial time) for each instance $I$ of UKP and show that the answer of $I$ can be gotten (in polynomial time) using the factorization of $M$.

In your proof, you can only solve a specific subset of UKP instances by FACTOR, so it is not a correct reduction.

$\endgroup$
2
$\begingroup$

If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently

Starting from a self-contradicting statement like this, you can prove anything. Why is it self-contradicting?

Let $n$ be a natural number. The number of possible factors of $n$ is $\sqrt{n}$; there may be number theory that pushes this down more, but there is no such result that eliminates all but $\Theta(\log^k n)$ numbers¹. So, you have to consider $\Omega(n^\varepsilon)$ numbers for some $\varepsilon > 0$. Note that the length of $n$ -- which is the input size! -- is $\lceil \log n \rceil$. Therefore, your assumed algorithm examines super-polynomially² many numbers in polynomial time³ -- impossible.


  1. If there were such a result (and you could list those candidates in polynomial time), factoring would be possible in polynomial time, which would be well-known. As far as I know, the problem is still open.
  2. $n^\varepsilon = 2^{\varepsilon\log n}$
  3. Assuming you mean "in polynomial time" when you say "efficiently".
$\endgroup$
  • $\begingroup$ When I said efficiently I meant in such a way that examines values without needing to examine them. Think about search algorithms. In an alphabetical list containing 17 values where you are looking for the value NAG if you look at the third value and it is LAG, you know that the first two values are below the value you are looking for without actually examining them individually. You could say my statement was confusing, but it was sound; it was your interpretation that contradicted itself, but your explanation as to why your interpretation is impossible was very thorough. $\endgroup$ – Char May 16 '12 at 9:28
  • $\begingroup$ Do I contradict myself? Very well, then, I contradict myself;. I am large—I contain multitudes. -Walt Whitman, Song Of Myself $\endgroup$ – Char May 16 '12 at 9:28

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.