ГлавнаяАрхивО генерической NP-полноте проблемы выполнимости булевых формул

О генерической NP-полноте проблемы выполнимости булевых формул | Прикладная дискретная математика. 2017. № 36. DOI: 10.17223/20710410/36/8

Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.
  • Title О генерической NP-полноте проблемы выполнимости булевых формул
  • Headline О генерической NP-полноте проблемы выполнимости булевых формул
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 36
  • Date:
  • DOI 10.17223/20710410/36/8
Ключевые слова
генерическая сложность, проблема выполнимости, NP-полнота, generic complexity, Boolean satisfiability problem, NP-completeness
Авторы
Ссылки
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 419 с.
Levin L. Average case complete problems // SIAM J. Computing. 1987. V. 15. P. 285-286.
Gurevich Y. Average case completeness // J. Computer System Sciences. 1991. V. 42. P. 346398.
Kapovichl., Miasnikov A, Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P. 665-694.
Gilman R., Miasnikov A. G., Myasnikov A. D., and Ushakov A. Report on generic case complexity // Herald of Omsk University. 2007. Special Issue. P. 103-110.
Impagliazzo R. and Wigderson A. P = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma // Proc. 29th STOC. El Paso: ACM, 1997. P. 220-229.
Cook S. A. The complexity of theorem proving procedures // Proc. 3d Annual ACM Symposium on Theory of Computing. N. Y., USA, 1971. P. 151-158.
Рыбалов А. О генерической сложности проблемы общезначимости булевых формул // Прикладная дискретная математика. 2016. №2(32). С. 119-126.
О генерической NP-полноте проблемы выполнимости булевых формул | Прикладная дискретная математика. 2017. № 36. DOI: 10.17223/20710410/36/8
О генерической NP-полноте проблемы выполнимости булевых формул | Прикладная дискретная математика. 2017. № 36. DOI: 10.17223/20710410/36/8