I am learning Computational Complexity.

Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that value >= a number) known to be NP-complete?

For the Knapsack-search problem to be NP-complete, should I have assumed that all weight, value are integer?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.