3 ms·

Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.

by Zezima 11y ago

truncate 11y ago
I studied this topic mainly from Algorithms text by Kleinberg/Tardos[1]. Like everything else, if you interested in proving problems NPC, read few examples from book and practice some on your own. Proving problems NPC of some common problems isn't very hard once you get hang of it. http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358 http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321...
justifier 11y ago
i talk about karp's paper: reducibility among combinatorial problems(i); in another thread and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii) do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables does your algorithm still work on these other inputs? can you rewrite the algorithm to give the correct answers for these other inputs? can you develop enough coverage to prove all possible inputs return correct values? if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm? for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii) this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21 (i) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (ii) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html (iii) http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00031000000000000000 http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00...

Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.

by Zezima 11y ago

Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.

truncate 11y ago

I studied this topic mainly from Algorithms text by Kleinberg/Tardos[1]. Like everything else, if you interested in proving problems NPC, read few examples from book and practice some on your own. Proving problems NPC of some common problems isn't very hard once you get hang of it. http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358 http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321...

justifier 11y ago

i talk about karp's paper: reducibility among combinatorial problems(i); in another thread and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii) do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables does your algorithm still work on these other inputs? can you rewrite the algorithm to give the correct answers for these other inputs? can you develop enough coverage to prove all possible inputs return correct values? if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm? for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii) this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21 (i) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (ii) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html (iii) http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00031000000000000000 http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00...