Programming #8: Knapsack Problem

In computer science, complexity classes help us talk about the difficulty of a problem. If there is a fast way to the find the solution of a problem (search), the problem is said to be Polynomial-time (P). If there is a fast way to check the solution of a problem (verification), the problem is said to be Nondeterministic Polynomial-time (NP).

For example, there exists a fast way to solve the sorting problem and a fast way to verify that the sort is correct. The sorting problem is thus both P and NP. For a problem like finding the solution in Sudoku, it is easy to check if a solution is correct, just see if the numbers add up, but hard to search for the solution in the first place, try every combination? The Sudoku problem NP, until it can otherwise be proved that a quick solution exists.

NP-hard is another class of problems that may or may not be in NP, but if solved would give us the answer to every NP problem. NP-complete is another class of problems that consist of problems that are both NP and NP-hard. Solving an NP-complete problem in a reasonable amount of time would be world-changing. The Knapsack problem is an NP-complete problem.

Continue reading “Programming #8: Knapsack Problem”

Advertisements