HomeIssuesAbout some features of the transformed problems images

About some features of the transformed problems images | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 3(17).

One of the way to prove the NP-completeness of a problem is to transformin it polynomially a problem the NP-completeness of which we can prove. Herewithwe pay less attention to the research of the received image features. In 1985 Lagarias andOdlyzko offered a method for solving knapsack NP-complete problem that gives a truedecision for "near all" knapsacks with the density less than 0.6463... In this paper, weconsider the following question: in which knapsack problems area (with regard to the knapsacksdensity) we can place, while proving the NP-completeness, the images of the problemssuch as 3-SAT, Colouring, Exact cover.
Download file
Counter downloads: 69
  • Title About some features of the transformed problems images
  • Headline About some features of the transformed problems images
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(17)
  • Date:
  • DOI
Keywords
NP-полнота, метод Лагариаса - Одлыжко, задача о рюкзаке, NP-completeness, Lagarias - Odlyzko method, knapsack problem
Authors
References
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.
Копсон Э. Т. Асимптотические разложения. М.: Мир, 1966. 159 с.
Karp R. M. Reducibility among combinatorial problems / / Complexity of Computer Computations: Proc. of a Symp. on the Complexity of Computer Computations, the IBM Research Symposia Series. NY: Plenum Press, 1972. P. 85-103.
Coster M. J., Joux A., LaMacchia B. A., et al. Improved low-density subset sum algorithms / / Computational Complexity. 1992. No. 2. P. 111-128.
Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2006. 336 с.
Odlyzko A. M. and Lagarias J. C. Solving Low-Density Subset Sum Problems / / J. Association Computing Machinery. 1985. V.32. No. 1. P. 229-246.
Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987. 288 с.
About some features of the transformed problems images | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 3(17).
About some features of the transformed problems images | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 3(17).
Download full-text version
Counter downloads: 248
Download file