|
Mathematical Foundations of Informatics and Programming
About the coNP-complete “Injective knapsack” problem
V. G. Durnev, O. V. Zetkina, A. I. Zetkina, D. M. Murin P. G. Demidov Yaroslavl State University, Yaroslavl, Russia
Abstract:
It is proved that the “Injective knapsack” problem is coNP-complete.
Keywords:
NP-complete and coNP-complete problems, injective knapsack, $m$-injective knapsack.
Citation:
V. G. Durnev, O. V. Zetkina, A. I. Zetkina, D. M. Murin, “About the coNP-complete “Injective knapsack” problem”, Prikl. Diskr. Mat., 2016, no. 3(33), 85–92
Linking options:
https://www.mathnet.ru/eng/pdm550 https://www.mathnet.ru/eng/pdm/y2016/i3/p85
|
Statistics & downloads: |
Abstract page: | 269 | Full-text PDF : | 88 | References: | 53 |
|