8
$\begingroup$

I found the P vs NP problem some time ago and I have recently worked on the subset sum problem. I have read Wikipedia article on the Subset Sum problem as well as the question Subset Sum Algorithm

I have looked at the problem and found some solutions but so far they seem to be NP, I believe I can make a sufficiently fast algorithm in NP time.

My problem is I am not good in theory so it doesn't help me much to talk about the Cook-Levin Theorem or Non-Deterministic Turing Machines.

What I would like is an explanation of the pseudo-polynomial time dynamic programming subset sum that on Wikipedia.

I have read it and I believe I understand the general concept of why it is NP instead of P (related to the size of the input rather than the operations with it), but I do not understand the algorithm.

I would appreciate if someone would put provide an example with some numbers and how it works. It would help me a lot because it would:

  • Give me ideas to improve my future algorithm
  • Help me understand intuitively when an algorithm is pseudo-polyonmial instead of NP.
Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ crab.rutgers.edu/~guyk/ex/part.pdf $\endgroup$
    – Robert Harvey
    Commented Dec 12, 2011 at 22:45
  • 1
    $\begingroup$ cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/… $\endgroup$
    – Robert Harvey
    Commented Dec 12, 2011 at 22:45
  • 2
    $\begingroup$ What is the question? Initially I thought you ask for an example of how the algorithm to which you link works, but I followed the link and there's already an example there. $\endgroup$
    – rgrig
    Commented May 6, 2012 at 15:10
  • 2
    $\begingroup$ I also have trouble understanding the posts, it is not clear what is being asked. btw, every problem in P is also in NP. I guess you mean NP-complete instead of NP in several places in your post. Finally, it doesn't make sense to say an algorithm is in NP, NP is a class of languages not algorithms. My guess is that you have the common misconception that NP means non-polynomial time (or exponential time) algorithm. $\endgroup$
    – Kaveh
    Commented May 6, 2012 at 18:59
  • 2
    $\begingroup$ If you bound the size the values in the input (bound the number of bits for each value to be logarithmic in the total number of bits of the input) then the problem can be solve in polynomial time using dynamic programming. If they are not bounded they can have values which are exponentially large and the size of the table for the dynamic programming would be exponential. $\endgroup$
    – Kaveh
    Commented May 6, 2012 at 19:06

1 Answer 1

Reset to default
5
$\begingroup$

Rephrasing Kaveh's comment as an answer:

If you bound the size the values in the input (bound the number of bits for each value to be logarithmic in the total number of bits of the input) then the problem can be solve in polynomial time using dynamic programming. If they are not bounded they can have values which are exponentially large and the size of the table for the dynamic programming would be exponential.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.