[Solved]: Subset sum algorithm in O(n³ log n)?

Problem Detail: 

I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers.

After my research, I'm lost between all the algorithms for this problem.

• $O(2^N*N)$ for the naive algorithm (I understand)
• $O(2^{N/2})$ for advanced algorithm (I understand)
• $O(N * C)$ for pseudo-polynomial time algorithm (only positive numbers)

Reference : Wikipedia

• $O(N^3 * log(N))$ for an exact resolution but I don't understand the whole process

Reference : Andrea Bianchini paper

I would like to know if my resolution is in polynomial time ?

If it is, the paper of Andrea Bianchini is too. So it should proove that P=NP, but it's not the case. Why ?

Asked By : Niels

Answered By : john_leo

This is a common misconception many have. Subset sum, among others, is NP-complete only if the input is encoded in binary (or ternary etc). In unary encoding it's polynomial-time solvable by a simple dynamic programming approach. These problems are sometimes referred as weakly NP-complete.
If you're not quite sure what I mean by unary encoding: Unary encoding means we encode a number by a sequence of $1$'s of appropriate length.
All in all, I fear you haven't settled P/NP (unless, of course, your runtime refers to binary-encoded problems). But good luck!
As an example, suppose your input consists of $10$ numbers, each between $128$ and $256$. Then your input size is, in unary, about $10 \times 256=2560$, whereas your input size is, in binary, $10 \times \log_2 (256) =80$.
That's quite a difference!

Wikipedia describes an algorithm that works in polynomial time for unary encoding. Wikipedia's solution was taken from the book Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. Garey and D. Johnson.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33519