|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Математические основы информатики и программирования
О генерической NP-полноте проблемы выполнимости булевых формул
А. Н. Рыбалов Омский государственный технический университет, г. Омск, Россия
Аннотация:
Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.
Ключевые слова:
генерическая сложность, проблема выполнимости, NP-полнота.
Образец цитирования:
А. Н. Рыбалов, “О генерической NP-полноте проблемы выполнимости булевых формул”, ПДМ, 2017, № 36, 106–112
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm582 https://www.mathnet.ru/rus/pdm/y2017/i2/p106
|
Статистика просмотров: |
Страница аннотации: | 213 | PDF полного текста: | 57 | Список литературы: | 39 |
|