Timeline for Knapsack Problem Specifics
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2011 at 19:20 | comment | added | user17007 | From the wiki : Pseudo-polynomial time : "In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input – its number of digits)." So am I reading this wrong in thinking it says that such a classification's running time depends on the number of digits, or size of values, or ... Further stating instances can run in pseudo-polynomial if the values of its digits are small enough, but nondeterministic polynomial time if the values have many digits? | |
| Aug 8, 2011 at 19:07 | vote | accept | user17007 | ||
| Aug 8, 2011 at 10:22 | comment | added | user17007 | Thanks Bruno, my lingering question I suppose is what criteria needs to be met to give an instance of the Knapsack Problem the complexity class NP-Complete? | |
| Aug 8, 2011 at 9:06 | history | answered | Bruno | CC BY-SA 3.0 |