Неудовлетворительное ядро - Unsatisfiable core
В математическая логика, учитывая неудовлетворительный Булево пропозициональная формула в конъюнктивная нормальная форма, подмножество предложений, конъюнкция которых все еще невыполнима, называется неудовлетворительное ядро исходной формулы.
Много SAT решатели может произвести график разрешения что доказывает невыполнимость исходной задачи. Это можно проанализировать, чтобы получить меньшее неудовлетворительное ядро.
Неудовлетворительное ядро называется минимальное неудовлетворительное ядро, если каждое собственное подмножество (позволяющее удалить любые произвольные предложения) из него выполнимо. Таким образом, такое ядро является местный минимум, хотя и не обязательно глобальный. Существует несколько практических методов вычисления минимальных неудовлетворительных ядер.[1][2]
А минимальное неудовлетворительное ядро содержит наименьшее количество исходных пунктов, которые должны оставаться невыполнимыми. Практические алгоритмы вычисления минимального ядра не известны.[3] Обратите внимание на терминологию: тогда как минимальное неудовлетворительное ядро была локальной проблемой с простым решением, минимальное неудовлетворительное ядро это глобальная проблема, для которой нет простого решения.
Рекомендации
- ^ Н. Дершовиц, З. Ханна и А. Надель, Масштабируемый алгоритм минимального невыполнимого извлечения керна
- ^ Стефан Зейдер, Минимальные невыполнимые формулы с ограниченной разностью разделительных переменных допускают обработку с фиксированным параметром
- ^ Алгоритмы вычисления минимальных невыполнимых подмножеств
 | Этот логика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |