2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ What algorithm do you propose? Why do you think it is (in)correct? Why do you give any weight to the Bianchini paper, which if it were correct would have been widely recognized by now? $\endgroup$ – Tom van der Zanden Nov 25 '14 at 19:59
  • $\begingroup$ I think this paper is correct, but I think it is in a restricted area that I don't understand. My algorithm is a binary algorithm inspired by quantum physic... I don't think I have find important something, and it's for this reason I ask this question. $\endgroup$ – csblo Nov 25 '14 at 20:12
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you have an example of unary approach ? Yes I'm sure I don't have settled P/NP $\endgroup$ – csblo Nov 25 '14 at 20:07
  • 1
    $\begingroup$ @Niels I edited the answer accordingly. Notice that the algorithms are the same, it's just that the input size differs exponentially, hence the runtime is also exponentially different. $\endgroup$ – john_leo Nov 25 '14 at 20:19

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.