>>86349426Well, I am a different guy but here goes.
NP means, Non-Deterministic Polynomial time.
NP-Complete means a problem belongs to a class of problems that have no known deterministic polynomial time algorithm, it means some other stuff too, but that's the basics.
This tends to mean that the time to solve a problem grows exponentially or worse as the problem set grows.
For instance, imagine sorting a list of 100 integers, the simplest algorithm to sort it, of searching through and finding the smallest, putting it at the beginning, finding the next smallest... etc. Will look at 100+99+98...+1 numbers or so to perform.
Through something called Big-O notation we will say this has a runtime of of O(n^2). This is polynomial in terms of the input size.
Now, NP-Hard/NP-Complete problems have no known polynomial time algorithms to discover. For instance, the traveling salesman problem mentioned in that comic. This problem says, given N cities, what is the shortest path to visit all of the cities exactly once, and then return to the origin. The naive algorithm of checking every possible combination of paths is N!, so, N * N-1 * N - 2...
This means that the runtime gets quick very quickly, and even for small values of N it is computationally infeasible to find the answer. For instance, we can sort 1,000,000 pretty quickly. Doing TSM for even 100 cities would take longer than the life of the universe.
Finally, his problem is not actually the knapsack problem. It's the subset sum problem. Which is related but a little different.
