Conference paper
Program equivalence and context-free grammars
Barry K. Rosen
SWAT 1972
The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed n > 2, the knapsack problem with n variables can be solved in polynomial time. © 1976, ACM. All rights reserved.
Barry K. Rosen
SWAT 1972
Miao Guo, Yong Tao Pei, et al.
WCITS 2011
Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM