4446
правок
Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида: различия между версиями
Материал из WEGA
Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида (посмотреть исходный код)
Версия от 15:48, 7 апреля 2021
, 7 апреля 2021→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 147: | Строка 147: | ||
Основными нерешенными вопросами в данной области остаются доказательство наличия постоянной верхней границы на <math>\alpha < 2</math>, а также гипотетическое существование алгоритмов с временем выполнения <math>(1 + \varepsilon)^l</math> для произвольного малого <math>\varepsilon > 0</math>. | Основными нерешенными вопросами в данной области остаются доказательство наличия постоянной верхней границы на <math>\alpha < 2</math>, а также гипотетическое существование алгоритмов с временем выполнения <math>(1 + \varepsilon)^l</math> для произвольного малого <math>\varepsilon > 0</math>. | ||
Можно провести анализ алгоритма «разделяй и властвуй» и даже автоматически генерировать правила упрощения [10]. Однако пока такой подход позволил получить новые границы только для (NP-полной) версии оптимизации | Можно провести анализ алгоритма «разделяй и властвуй» и даже автоматически генерировать правила упрощения [10]. Однако пока такой подход позволил получить новые границы только для (NP-полной) версии оптимизации 2-КНФ [9]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
