HomeIssuesAbout the coNP- complete "Injective knapsack" problem

About the coNP- complete "Injective knapsack" problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 3(33). DOI: 10.17223/20710410/33/7

It is proved that the "Injective knapsack" problem is coNP-complete.
Download file
Counter downloads: 204
  • Title About the coNP- complete "Injective knapsack" problem
  • Headline About the coNP- complete "Injective knapsack" problem
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(33)
  • Date:
  • DOI 10.17223/20710410/33/7
Keywords
NP-полные и coNP-полные задачи, инъективный 'рюкзак, т-инъективный рюкзак, NP-complete and coNP-complete problems, injective knapsack, m-injec-tive knapsack
Authors
References
Karp R.M. Reducibility among combinatorial problems // Complexity of Computer Computations. N.Y.: Plenum Press, 1972. P. 85-103.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984.
Merkle R. and Hellman M. Hiding information and signature in trapdoor knapsacks // IEEE Trans. Inform. Theory. 1978. V. 24. No. 5. P. 525-530.
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problems Control Inform. Theory. 1986. No. 15(2). P. 159-166.
Chor B. and Rivest R. A knapsack-type public key cryptosystem based on arithmetic in finite fields // CRYPTO'84. LNCS. 1985. V. 196. P. 54-65.
Осипян В. О. О криптосистемах с заданным рюкзаком // Материалы VI Междунар. науч.-практич. конф. «Информационная безопасность». Таганрог: Изд-во ТРТУ, 2004. С.269-271.
Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета. 2006. Т. 309. №2. С. 209-212.
Woeginger G. J. and Yu Z. On the equal-subset-sum problem // Inform. Proc. Lett. 1992. V. 42. P. 299-302.
Мурин Д. М. О порядке роста числа инъективных и сверхрастущих рюкзачных векторов // Моделирование и анализ информационных систем. 2012. Т. 19. №3. С. 124-135.
Мурин Д. М. О порядке роста числа инъективных и сверхрастущих векторов и некоторых особенностях сильного модульного умножения // Прикладная дискретная математика. Приложение. 2012. №5. С. 19-21.
About the coNP- complete
About the coNP- complete "Injective knapsack" problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 3(33). DOI: 10.17223/20710410/33/7
Download full-text version
Counter downloads: 1057