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}
Would this mean FACTOR was NP-Complete?
Would solving unbounded knapsack problems in polynomial time in this way prove P=NP?
Asked By : Char
Answered By : Wu Yin
(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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1801
0 comments:
Post a Comment
Let us know your responses and feedback