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 that you have read and understand our privacy policy and code of conduct.