Мы знаем, что основанные на DPLL SAT-решатели не могут правильно ответить на неудовлетворительных экземплярах (принцип "голубиной дыры"), например, "существует инъективное отображение от к ": n + 1 n
Я ищу результаты о том, как они работают на удовлетворительных экземплярах , например, на "есть инъективное отображение от n до n ". n n
Находят ли они быстро удовлетворительное назначение в таких случаях?
Ответы:
На удовлетворительных экземплярах решатели SAT на основе DPLL будут обеспечивать удовлетворительное назначение за линейное время.пЧАСп
Чтобы понять почему, посмотрите, как кодирование CNF неудовлетворительного экземпляра с дырами и голубями синтаксически идентично экземпляру раскраски графов, где входной граф представляет собой клику из вершин.n n + 1пЧАСп N n + 1 n + 1k = n n + 1
Точно так же кодирование CNF выполнимого экземпляра с дырами и голубями синтаксически идентично экземпляру раскраски графов, где входной граф представляет собой клику из вершин. n nпЧАСп N N nk = n N
Теперь раскрасить клику из вершин с помощью цветов просто: отсканируйте вершины и назначьте каждому из них один из оставшихся цветов (уже назначенные цвета автоматически исключаются кликой графа, используя распространение единиц) , Какой бы из оставшихся цветов вы ни выбрали, это будет хорошо и приведет вас к удовлетворительному заданию.нN N
С точки зрения решателя DPLL: каждый раз, когда он будет пытаться угадать логическое значение переменной , такое значение будет правильным (каким бы оно ни было), потому что, безусловно, будет удовлетворительное присваивание, в котором переменная имеет предполагаемое значение. , Распространение модулей выполнит остальную часть работы, направляя решатель вдоль удовлетворительного пути (другими словами: предотвращая угадывание неправильных значений).V Ivя vя
Поиск затем продолжается одна переменная за другой, линейно, каждый раз делая правильное предположение.
источник