|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Оптимизация, системный анализ и исследование операций
Усовершенствованный генератор 3-КНФ формул
С. И. Уваров Институт проблем управления им. В.А. Трапезникова РАН, Москва
Аннотация:
Рассматривается задача выполнимости (SAT-problem) булевых формул, заданных в конъюнктивной нормальной форме с ограничением, что каждый дизъюнкт содержит по три литерала переменных (3-КНФ). В эмпирических исследованиях широко используется генерация случайных формул с фиксированной длиной дизъюнкта. Феноменом этого метода является многократно подтвержденная линейная зависимость числа дизъюнктов формулы от числа булевых переменных в точке «фазового перехода» — от статуса выполнимых к статусу невыполнимых (когда доля невыполнимых формул становится превалирующей). Предложен и исследован метод генерации случайных формул, имеющий меньший коэффициент (3,49) пропорциональности между числом дизъюнктов и числом переменных в точке «фазового перехода» (для известного метода генерации этот коэффициент равен 4,23).
Ключевые слова:
задача выполнимости (SAT-problem), конъюнктивная нормальная форма (КНФ), дизъюнкт, литерал, булевы переменные.
Образец цитирования:
С. И. Уваров, “Усовершенствованный генератор 3-КНФ формул”, Автомат. и телемех., 2020, № 1, 161–172; Autom. Remote Control, 81:1 (2020), 130–138
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at15421 https://www.mathnet.ru/rus/at/y2020/i1/p161
|
Статистика просмотров: |
Страница аннотации: | 258 | PDF полного текста: | 42 | Список литературы: | 28 | Первая страница: | 10 |
|