I found the P vs NP problem some time ago and I have recently worked on the subs

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.