ГлавнаяАрхивО некоторых свойствах образов трансформированных задач

О некоторых свойствах образов трансформированных задач | Прикладная дискретная математика. 2012. № 3(17).

Одним из способов доказательства NP-полноты задачи является полиномиальноесведение (трансформация) к ней задачи, NP-полнота которой уже установлена.При этом изучению свойств полученного образа, на наш взгляд, уделяется недостаточно внимания. В 1985 г. в работе Дж. Лагариаса и А. М. Одлыжко предложенметод решения NP-полной задачи о рюкзаке, дающий верное решение для «практически всех» рюкзаков, плотность которых не превышает 0,6463... В настоящейработе рассматривается вопрос о том, в какую область задач о рюкзаке (относительно плотности рюкзаков) при доказательстве NP-полноты попадают образыследующих задач: 3-ВЫП, Раскрашиваемость, Точное покрытие.
  • Title О некоторых свойствах образов трансформированных задач
  • Headline О некоторых свойствах образов трансформированных задач
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(17)
  • Date:
  • DOI
Ключевые слова
NP-полнота, метод Лагариаса - Одлыжко, задача о рюкзаке, NP-completeness, Lagarias - Odlyzko method, knapsack problem
Авторы
Ссылки
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 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 с.
О некоторых свойствах образов трансформированных задач | Прикладная дискретная математика. 2012. № 3(17).
О некоторых свойствах образов трансформированных задач | Прикладная дискретная математика. 2012. № 3(17).
Полнотекстовая версия