Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида: различия между версиями

Основными нерешенными вопросами в данной области остаются доказательство наличия постоянной верхней границы на a < 2, а также гипотетическое существование алгоритмов с временем выполнения (1 + ") для произвольного малого " > 0. Можно провести анализ алгоритма «разделяй и властвуй» и даже автоматически генерировать правила упрощения [10]. Однако пока такой подход позволил получить новые границы только для (NP-полной) версии оптимизации 3-КНФ [9].