Geodesic
About the coNP-complete ``Injective knapsack'' problem
Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 85-92.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that the “Injective knapsack” problem is coNP-complete.
Keywords: NP-complete and coNP-complete problems, injective knapsack, $m$-injective knapsack. 
@article{PDM_2016_3_a6,
     author = {V. G. Durnev and O. V. Zetkina and A. I. Zetkina and D. M. Murin},
     title = {About the {coNP-complete} {``Injective} knapsack'' problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {85--92},
     publisher = {mathdoc},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_3_a6/}
}
TY  - JOUR
AU  - V. G. Durnev
AU  - O. V. Zetkina
AU  - A. I. Zetkina
AU  - D. M. Murin
TI  - About the coNP-complete ``Injective knapsack'' problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 85
EP  - 92
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_3_a6/
LA  - ru
ID  - PDM_2016_3_a6
ER  - 
%0 Journal Article
%A V. G. Durnev
%A O. V. Zetkina
%A A. I. Zetkina
%A D. M. Murin
%T About the coNP-complete ``Injective knapsack'' problem
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 85-92
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_3_a6/
%G ru
%F PDM_2016_3_a6
V. G. Durnev; O. V. Zetkina; A. I. Zetkina; D. M. Murin. About the coNP-complete ``Injective knapsack'' problem. Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 85-92. http://geodesic.mathdoc.fr/item/PDM_2016_3_a6/

[1] Karp R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, Plenum Press, N.Y., 1972, 85–103 | DOI | MR

[2] Garey R., Johnson D., Computers and Intractability, W. H. Freeman Co, N.Y., USA, 1979 | MR | MR | Zbl

[3] Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982 | MR | MR | Zbl

[4] Merkle R., Hellman M., “Hiding information and signature in trapdoor knapsacks”, IEEE Trans. Inform. Theory, 24:5 (1978), 525–530 | DOI

[5] Niederreiter H., “Knapsack-type cryptosystems and algebraic coding theory”, Problems Control Inform. Theory, 15:2 (1986), 159–166 | MR | Zbl

[6] Chor B., Rivest R., “A knapsack-type public key cryptosystem based on arithmetic in finite fields”, CRYPTO'84, LNCS, 196, 1985, 54–65 | MR | Zbl

[7] Osipyan V. O., “About cryptosystems with a given knapsack”, Proc. VI Int. Conf. “Information security”, TRTU Publ., Taganrog, 2004, 269–271 (in Russian)

[8] Osipyan V. O., “Information protection system based on the knapsack problem”, Bull. TPU, 309:2 (2006), 209–212 (in Russian)

[9] Woeginger G. J., Yu Z., “On the equal-subset-sum problem”, Inform. Proc. Lett., 42 (1992), 299–302 | DOI | MR | Zbl

[10] Murin D. M., “The order in the growth of the injective and super-increasing vectors knapsacks quantity”, Modelirovanie i Analiz Informatsionnykh Sistem, 19:3 (2012), 124–135 (in Russian)

[11] Murin D. M., “About the order of the increasing in the number of the injective and super-increasing vectors and some particularities in the strong modular multiplying”, Prikladnaya diskretnaya matematika. Prilozhenie, 2012, no. 5, 19–21 (in Russian)