Editing Knapsack problem (section)

== Computational complexity ==
The knapsack problem is interesting from the perspective of computer science for many reasons:
* The [[decision problem]] form of the knapsack problem (''Can a value of at least ''V'' be achieved without exceeding the weight ''W''?'') is [[NP-complete]], thus there is no known algorithm that is both correct and fast (polynomial-time) in all cases.
* There is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger ''V''). This problem is [[co-NP-complete]].
* There is a [[pseudo-polynomial time]] algorithm using [[dynamic programming]].
* There is a [[Polynomial-time approximation scheme|fully polynomial-time approximation scheme]], which uses the pseudo-polynomial time algorithm as a subroutine, described below.
* Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly.

There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the  "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k. On the other hand, if an algorithm finds the optimal value of the optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k. Thus, both versions of the problem are of similar difficulty.

One theme in research literature is to identify what the "hard" instances of the knapsack problem look like,<ref name="pisinger200308">Pisinger, D. 2003. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.7431&rep=rep1&type=pdf Where are the hard knapsack problems?] Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark.</ref><ref name="Cacetta2001">{{cite journal | last1 = Caccetta | first1 = L. | last2 = Kulanoot | first2 = A. | year = 2001 | title = Computational Aspects of Hard Knapsack Problems | journal = Nonlinear Analysis | volume = 47 | issue = 8| pages = 5547–5558 | doi=10.1016/s0362-546x(01)00658-7}}</ref> or viewed another way, to identify what properties of instances in practice might make them more amenable than their worst-case NP-complete behaviour suggests.<ref name="poirriez_et_all_2009">{{cite journal|last1=Poirriez|first1=Vincent|last2=Yanev|first2=Nicola|last3=Andonov|first3=Rumen|title=A hybrid algorithm for the unbounded knapsack problem|journal=Discrete Optimization|volume=6|issue=1|year=2009|pages=110–124|issn=1572-5286|doi=10.1016/j.disopt.2008.09.004|s2cid=8820628 |doi-access=free}}</ref> The goal in finding these "hard" instances is for their use in [[public-key cryptography]] systems, such as the [[Merkle–Hellman knapsack cryptosystem]]. More generally, better understanding of the structure of the space of instances of an optimization problem helps to advance the study of the particular problem and can improve algorithm selection.

Furthermore, notable is the fact that the hardness of the knapsack problem depends on the form of the input. If the weights and profits are given as integers, it is [[weakly NP-complete]], while it is [[strongly NP-complete]] if the weights and profits are given as rational numbers.<ref name="Wojtczak18">{{cite book|last1=Wojtczak|first1=Dominik|title=Computer Science – Theory and Applications |chapter=On Strong NP-Completeness of Rational Problems |volume=10846|year=2018|pages=308–320|doi=10.1007/978-3-319-90530-3_26|arxiv=1802.09465|isbn=978-3-319-90529-7|series=Lecture Notes in Computer Science|s2cid=3637366}}</ref> However, in the case of rational weights and profits it still admits a [[Polynomial-time approximation scheme|fully polynomial-time approximation scheme]].

===Unit-cost models===
The NP-hardness of the Knapsack problem relates to computational models in which the size of integers matters (such as the [[Turing machine]]). In contrast, [[decision tree model|decision trees]] count each decision as a single step. Dobkin and Lipton<ref>{{Cite journal|last1=Dobkin|first1=David|last2=Lipton|first2=Richard J.|year=1978|title=A lower bound of ½''n''<sup>2</sup> on linear search programs for the Knapsack problem|url=https://dx.doi.org/10.1016/0022-0000%2878%2990026-0|journal=Journal of Computer and System Sciences|volume=16|issue=3|pages=413–417|doi=10.1016/0022-0000(78)90026-0}}</ref> show an <math>{1\over 2}n^2</math> lower bound on linear decision trees for the knapsack problem, that is, trees where decision nodes test the sign of [[affine function]]s.<ref>In fact, the lower bound applies to the subset sum problem, which is a special case of Knapsack.</ref> This was generalized to algebraic decision trees by Steele and Yao.<ref>{{Cite journal|last1=Michael Steele|first1=J|last2=Yao|first2=Andrew C|date=1982-03-01|title=Lower bounds for algebraic decision trees|url=https://dx.doi.org/10.1016%2F0196-6774%2882%2990002-5|journal=Journal of Algorithms|language=en|volume=3|issue=1|pages=1–8|doi=10.1016/0196-6774(82)90002-5|issn=0196-6774}}</ref>
If the elements in the problem are [[real number]]s or [[rationals]], the decision-tree lower bound extends to the [[real RAM|real random-access machine]] model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor").<ref>{{citation|doi=10.1137/S0097539797329397|title=Topological Lower Bounds on Algebraic Random Access Machines|year=2001|last1=Ben-Amram|first1=Amir M.|journal=SIAM Journal on Computing|volume=31|issue=3|pages=722–761|last2=Galil|first2=Zvi|author2-link=Zvi Galil}}.</ref> This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions.
An ''upper bound'' for a decision-tree model was given by Meyer auf der Heide<ref>{{citation|doi=10.1145/828.322450|title=A Polynomial Linear Search Algorithm for the ''n''-Dimensional Knapsack Problem|year=1984|last1=auf der Heide|first1=Meyer|journal=Journal of the ACM|volume=31|issue=3|pages=668–676}}</ref> who showed that for every ''n'' there exists an {{math|''O''(''n''<sup>4</sup>)}}-deep linear decision tree that solves the [[#Subset-sum_problem|subset-sum problem]] with ''n'' items. Note that this does not imply any upper bound for an algorithm that should solve the problem for ''any given n''.