RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive
Prikl. Diskr. Mat., 2016 Number 3(33), Pages 85–92 (Mi pdm550)
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.

UDC: 512.54

DOI: 10.17223/20710410/33/7



Bibliographic databases:

© Steklov Math. Inst. of RAS, 2024