Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
«3SAT» перенаправляется сюда. Информацию о сети центральноевропейского телевидения см. На сайте 3sat .

В логике и информатике , то булева задача выполнимости (иногда называемая пропозициональной проблема выполнимости и сокращенная выполнимость , SAT или B-SAT ) является проблема определения , если существует интерпретацию , что удовлетворяет заданную булева формулу . Другими словами, он спрашивает, могут ли переменные данной логической формулы быть последовательно заменены значениями ИСТИНА или ЛОЖЬ таким образом, чтобы формула оценивалась как ИСТИНА . В этом случае формула называется выполнимой.. С другой стороны, если такого присваивания не существует, функция, выраженная формулой, будет ЛОЖНОЙ для всех возможных назначений переменных, и формула не выполнима . Например, формула « a AND NOT b » является выполнимой, потому что можно найти значения a  = TRUE и b  = FALSE, которые делают ( a AND NOT b ) = TRUE. В отличие от этого , « И НЕ » невыполнима.

SAT - первая проблема, NP-завершенность которой доказана ; см. теорему Кука – Левина . Это означает, что все проблемы класса сложности NP , который включает в себя широкий спектр естественных задач решения и оптимизации, труднее всего решить, как SAT. Не существует известного алгоритма, который бы эффективно решал каждую проблему SAT, и обычно считается, что такого алгоритма не существует; однако это убеждение не было доказано математически, и решение вопроса о том, имеет ли SAT алгоритм с полиномиальным временем , эквивалентно проблеме P против NP , которая является известной открытой проблемой в теории вычислений.

Тем не менее, по состоянию на 2007 год эвристические SAT-алгоритмы способны решать примеры проблем, включающие десятки тысяч переменных и формул, состоящих из миллионов символов [1], что достаточно для многих практических задач SAT, например, из искусственного интеллекта , проектирования схем. , [2] и автоматическое доказательство теорем .

Основные определения и терминология [ править ]

Логика высказываний формула , которая также называется логическое выражение , строится из переменных , операторов и ( совместно , также обозначаемой ∧) или ( дизъюнкции , ∨), НЕ ( отрицание , ¬), и круглые скобки. Формула считается выполнимой, если ее можно сделать ИСТИННОЙ путем присвоения соответствующих логических значений (т.е. ИСТИНА, ЛОЖЬ) ее переменным. Задача логической выполнимости (SAT) состоит в том, чтобы при наличии формулы проверить, выполнима ли она. Эта проблема принятия решения имеет центральное значение во многих областях информатики , включаятеоретическая информатика , теория сложности , [3] [4] алгоритмика , криптография и искусственный интеллект . [5] [ требуется дополнительное цитирование ]

Существует несколько частных случаев проблемы булевой выполнимости, в которых требуется, чтобы формулы имели определенную структуру. Буквальным либо переменная, называется положительным буквальным , или отрицание переменной, называется отрицательной буквальным . Раздел является дизъюнкция литералов (или одного буквальным). Предложение называется предложением Horn, если оно содержит не более одного положительного литерала. Формула имеет конъюнктивную нормальную форму (CNF), если она является соединением пунктов (или одним предложением). Например, x 1 - положительный литерал, ¬ x 2 - отрицательный литерал, x 1∨ ¬ x 2 - это пункт. Формула ( x 1 ∨ ¬ x 2 ) ∧ (¬ x 1 ∨ x 2 ∨ x 3 ) ∧ ¬ x 1 находится в конъюнктивной нормальной форме; его первое и третье предложения являются предложениями Хорна, а его второе предложение - нет. Формула выполняется при произвольном выборе x 1  = FALSE, x 2  = FALSE и x 3 , поскольку (FALSE ∨ ¬FALSE) ∧ (¬FALSE ∨ FALSE ∨ x 3 ) ∧ ¬FALSE оценивается как (FALSE ∨ TRUE) ∧ (ИСТИНА ∨ ЛОЖЬ ∨ x 3) ∧ ИСТИНА и, в свою очередь, ИСТИНА ∧ ИСТИНА ∧ ИСТИНА (т.е. ИСТИНА). Напротив, формула CNF a ∧ ¬ a , состоящая из двух частей одного литерала, является неудовлетворительной, поскольку для a = TRUE или a = FALSE она оценивается как TRUE ∧ ¬TRUE (т. Е. FALSE) или FALSE ∧ ¬FALSE (т.е. , снова FALSE) соответственно.

Для некоторых версий задачи SAT полезно определить понятие формулы обобщенной конъюнктивной нормальной формы , а именно. как конъюнкция произвольного числа обобщенных предложений , причем последнее имеет вид R ( l 1 , ..., l n ) для некоторого булевого оператора R и (обычных) литералов l i . Различные наборы допустимых логических операторов приводят к разным версиям проблемы. Например, R (¬ x , a , b ) является обобщенным предложением, а R (¬ x , a ,б ) ∧ R ( b , y , c ) ∧ R ( c , d , ¬ z ) - обобщенная конъюнктивная нормальная форма. Эта формула используется ниже , где R является тернарным оператором, который имеет значение ИСТИНА только тогда, когда имеет значение ровно один из его аргументов.

Используя законы булевой алгебры , любую формулу логики высказываний можно преобразовать в эквивалентную конъюнктивную нормальную форму, которая, однако, может быть экспоненциально длиннее. Например, преобразование формулы ( x 1 ∧ y 1 ) ∨ ( x 2 ∧ y 2 ) ∨ ... ∨ ( x n ∧ y n ) в конъюнктивную нормальную форму дает

( x 1  ∨  x 2  ∨… ∨  x n ) ∧
( y 1  ∨  x 2  ∨… ∨  x n ) ∧
( x 1  ∨  y 2  ∨… ∨  x n ) ∧
( y 1  ∨  y 2  ∨… ∨  x n ) ∧ ... ∧
( x 1  ∨  x 2  ∨… ∨  y n ) ∧
( y 1  ∨  x 2  ∨… ∨  y n ) ∧
( x 1  ∨  y 2  ∨… ∨  y n ) ∧
( y 1  ∨  y 2  ∨… ∨  y n ) ;

в то время как первая представляет собой дизъюнкцию n конъюнкций двух переменных, вторая состоит из 2 n частей n переменных.

Сложность и ограниченные версии [ править ]

Неограниченная выполнимость (SAT) [ править ]

Основная статья: теорема Кука – Левина

SAT была первой известной NP-полной проблемой, что было доказано Стивеном Куком из Университета Торонто в 1971 году [6] и независимо Леонидом Левиным из Национальной академии наук в 1973 году. [7] До этого времени концепция NP-полной проблемы даже не существовало. Доказательство показывает, как каждая проблема решения в классе сложности NP может быть сведена к задаче SAT для формул CNF [примечание 1] , иногда называемой CNFSAT.. Полезное свойство редукции Кука состоит в том, что она сохраняет количество принимаемых ответов. Например, определение того, имеет ли данный граф 3-раскраску, - еще одна проблема в NP; если график имеет 17 допустимых 3-раскрасок, формула SAT, полученная редукцией Кука – Левина, будет иметь 17 удовлетворительных назначений.

NP-полнота относится только к времени выполнения в наихудших случаях. Многие из проблем, возникающих в практических приложениях, можно решить гораздо быстрее. См. « Алгоритмы решения SAT» ниже.

SAT является тривиальным, если формулы ограничены формулами в дизъюнктивной нормальной форме , то есть они являются дизъюнкцией конъюнкций литералов. Такая формула действительно выполнима тогда и только тогда, когда выполнима хотя бы одна из ее конъюнкций, а конъюнкция выполнима тогда и только тогда, когда она не содержит одновременно x и НЕ x для некоторой переменной x . Это можно проверить за линейное время. Кроме того, если они ограничены полной дизъюнктивной нормальной формой, в котором каждая переменная появляется ровно один раз в каждом соединении, они могут быть проверены в постоянное время (каждое соединение представляет одно удовлетворительное присвоение). Но для преобразования общей задачи SAT в дизъюнктивную нормальную форму могут потребоваться экспоненциальные время и пространство; например, поменяйте местами «∧» и «∨» в приведенном выше примере экспоненциального расширения для конъюнктивных нормальных форм.

3-выполнимость [ править ]

Экземпляр 3-SAT ( x ∨ x ∨ y ) ∧ (¬ x ∨ ¬ y ∨ ¬ y ) ∧ (¬ x ∨ y ∨ y ) сведен к задаче клики . Зеленые вершины образуют 3-клику и соответствуют удовлетворяющему назначению x = FALSE, y = TRUE.

Как и проблема выполнимости для произвольных формул, определение выполнимости формулы в конъюнктивной нормальной форме, где каждое предложение ограничено не более чем тремя литералами, также является NP-полным; эта проблема называется 3-SAT , 3CNFSAT или 3-выполнимостью . Чтобы уменьшить неограниченную задачу SAT до 3-SAT, преобразуйте каждое предложение l 1 ∨ ⋯ ∨ l n в конъюнкцию из n - 2 предложений.

( l 1 ∨ l 2 ∨ x 2 ) ∧
(¬ x 2 ∨ l 3 ∨ x 3 ) ∧
(¬ x 3 ∨ l 4 ∨ x 4 ) ∧ ⋯ ∧
(¬ x n - 3 ∨ l n - 2 ∨ x n - 2 ) ∧
(¬ x n - 2 ∨ l n - 1 ∨ l n )

где x 2 , ⋯,  x n - 2 - новые переменные, нигде не встречающиеся. Хотя эти две формулы не являются логически эквивалентными , они одинаково выполнимы . Формула, полученная в результате преобразования всех клозов, не более чем в 3 раза длиннее оригинальной, т. Е. Рост длины полиномиален. [8]

3-SAT - одна из 21 NP-полных проблем Карпа , и она используется в качестве отправной точки для доказательства того, что другие проблемы также NP-трудны . [примечание 2] Это делается путем полиномиального сокращения от 3-SAT к другой задаче. Примером проблемы, в которой использовался этот метод, является проблема клики : учитывая формулу CNF, состоящую из c пунктов, соответствующий граф состоит из вершины для каждого литерала и ребра между каждыми двумя непротиворечивыми [примечание 3] литералами из разных статей, ср. рисунок. Граф имеет c -клику тогда и только тогда, когда формула выполнима. [9]

Существует простой рандомизированный алгоритм, созданный Шёнингом (1999), который выполняется за время (4/3) n, где n - количество переменных в предложении 3-SAT, и с высокой вероятностью успешно принимает правильное решение для 3-SAT. [10]

Гипотеза экспоненциального времени утверждает, что ни один алгоритм не может решить 3-SAT (или действительно k -SAT для любого k> 2 ) за время exp ( o ( n )) (т. Е. Существенно быстрее, чем экспоненциальный по n ).

Селман, Митчелл и Левеск (1996) приводят эмпирические данные о сложности случайно сгенерированных формул 3-SAT в зависимости от их параметров размера. Сложность измеряется количеством рекурсивных вызовов, сделанных алгоритмом DPLL . [11]

3-выполнимость может быть обобщена до k-выполнимости ( k-SAT , также k-CNF-SAT ), когда формулы в CNF рассматриваются с каждым предложением, содержащим до k литералов. [ необходима цитата ] Однако, поскольку для любого k ≥ 3 эта задача не может быть ни легче, чем 3-SAT, ни сложнее, чем SAT, а последние два являются NP-полными, поэтому должно быть k-SAT.

Некоторые авторы ограничивают k-SAT формулами CNF с ровно k литералами . [ необходима цитата ] Это также не приводит к другому классу сложности, поскольку каждое предложение l 1 ∨ ⋯ ∨ l j с литералами j < k может быть дополнено фиксированными фиктивными переменными до l 1 ∨ ⋯ ∨ l j ∨ d j + 1 ∨ ⋯ ∨ г к . После заполнения всех предложений необходимо добавить 2 k -1 дополнительных предложений [примечание 4] , чтобы гарантировать, что только d 1 = ⋯ =d k = FALSE может привести к удовлетворительному присвоению. Поскольку k не зависит от длины формулы, дополнительные предложения приводят к постоянному увеличению длины. По той же причине не имеет значения,разрешеныли повторяющиеся литералы в предложениях, как в ¬ x ∨ ¬ y ∨ ¬ y .

Точно-1 3-выполнимость [ править ]

Слева: сокращение Шефера предложения 3-SAT x ∨ y ∨ z . Результатом R является ИСТИНА (1), если ровно один из его аргументов ИСТИНА, и ЛОЖЬ (0) в противном случае. Проверяются все 8 комбинаций значений x , y , z , по одной в строке. Новые переменные a , ..., f могут быть выбраны так, чтобы удовлетворять всем предложениям (ровно один зеленый аргумент для каждого R ) во всех строках, кроме первой, где x ∨ y ∨ z - ЛОЖЬ. Правильно: Более простая редукция с такими же свойствами.

Вариантом проблемы 3-выполнимости является 3-SAT один из трех (также известный как 1-из-3-SAT и точно-1 3-SAT ). Учитывая конъюнктивную нормальную форму с тремя литералами на каждое предложение, проблема состоит в том, чтобы определить, существует ли истинное присвоение переменных, чтобы каждое предложение имело ровно один ИСТИННЫЙ литерал (и, следовательно, ровно два ЛОЖНЫХ литерала). Напротив, обычный 3-SAT требует, чтобы каждое предложение имело хотя бы один литерал TRUE. Формально, задача 3-SAT один из трех задается как обобщенная конъюнктивная нормальная форма со всеми обобщенными предложениями с использованием тернарного оператора Rэто ИСТИНА, если только один из его аргументов. Когда все литералы формулы 3-SAT "один из трех" положительны, проблема выполнимости называется положительным 3-SAT "один из трех" .

Один-в-три 3-СБ, вместе с его положительным случаем, перечислен как NP-полной задачей «ОС4» в стандартной ссылке, Компьютеры и труднорешаемое: Руководство по теории NP-полнота по Майкл Р. Garey и Давида С. Джонсон . Один из трех 3-SAT был доказан Томасом Джеромом Шефером как частный случай дихотомической теоремы Шефера , который утверждает, что любая проблема, обобщающая булеву выполнимость определенным образом, либо принадлежит классу P, либо является NP- полный. [12]

Шефер дает конструкцию, позволяющую легко за полиномиальное время сократить 3-SAT до 3-SAT один из трех. Пусть «( x или y или z )» будет предложением в формуле 3CNF. Добавьте шесть новых логических переменных a , b , c , d , e и f , которые будут использоваться для имитации этого предложения, а не другого. Тогда формула R ( x , a , d ) ∧ R ( y , b , d ) ∧ R ( a , b , e) ∧ R ( c , d , f ) ∧ R ( z , c , FALSE) выполнимо при некоторой установке новых переменных тогда и только тогда, когда хотя бы одно из x , y или z истинно, см. Рисунок (слева) . Таким образом, любой экземпляр 3-SAT с m разделами и n переменными может быть преобразован в равноправный экземпляр 3-SAT один из трех с 5 m разделами и n +6 m переменными. [13] Другая редукция включает только четыре свежие переменные и три предложения: R(¬ x , a , b ) ∧ R ( b , y , c ) ∧ R ( c , d , ¬ z ), см. Рисунок (справа).

Не все равно 3-выполнимость [ править ]

Основная статья: Не все равно 3-выполнимость

Другой вариант - проблема не-все-равной 3-выполнимости (также называемая NAE3SAT ). Учитывая конъюнктивную нормальную форму с тремя литералами на каждое предложение, проблема состоит в том, чтобы определить, существует ли такое присвоение переменным, что ни в одном предложении все три литерала имеют одинаковое значение истинности. Эта проблема тоже является NP-полной, даже если не допускаются символы отрицания, согласно теореме о дихотомии Шефера. [12]

Linear SAT [ править ]

Формула 3-SAT называется Linear SAT ( LSAT ), если каждое предложение (рассматриваемое как набор литералов) пересекает не более одного другого предложения, и, более того, если два предложения пересекаются, то они имеют ровно один общий литерал. Формулу LSAT можно представить в виде набора непересекающихся полузамкнутых интервалов на линии. Решение о том, является ли формула LSAT выполнимой или нет, является NP-полным. [14]

2-выполнимость [ править ]

Основная статья: 2-выполнимость

SAT проще, если количество литералов в предложении ограничено максимум 2, и в этом случае проблема называется 2-SAT . Эта проблема может быть решена за полиномиальное время и фактически является полной для класса сложности NL . Если дополнительно все или операции в литералов изменяются на XOR операций, результат называется исключительным или 2-выполнимости , что является проблемой в комплекте для класса сложности SL = L .

Роговая выполнимость [ править ]

Основная статья: выполнимость по рогу

Проблема определения выполнимости данной конъюнкции предложений Хорна называется выполнимостью по Хорну или HORN-SAT . Это может быть решено за полиномиальное время с помощью одного шага алгоритма распространения единиц , который производит единственную минимальную модель набора предложений Horn (относительно набора литералов, присвоенных TRUE). Роговая выполнимость P-полная . Это можно рассматривать как версию P проблемы логической выполнимости. Кроме того, определение истинности количественных формул Хорна может быть выполнено за полиномиальное время. [15]

Предложения Хорна интересны тем, что они могут выражать значение одной переменной из набора других переменных. Действительно, одна такая статья ¬ х 1 ∨ ... ∨ ¬ х п ∨ у можно переписать в виде х 1 ∧ ... ∧ х п → у , то есть, если х 1 , ..., х п все ИСТИНА , тогда y также должно быть TRUE.

Обобщением класса формул Хорна являются формулы переименовываемого Горна, которые представляют собой набор формул, которые могут быть преобразованы в форму Хорна путем замены некоторых переменных их соответствующим отрицанием. Например, ( x 1 ∨ ¬ x 2 ) ∧ (¬ x 1 ∨ x 2 ∨ x 3 ) ∧ ¬ x 1 не является формулой Хорна, но может быть переименовано в формулу Хорна ( x 1 ∨ ¬ x 2 ) ∧ (¬ x 1 ∨ x 2 ∨ ¬ y 3 ) ∧ ¬ x 1 , введяy 3 как отрицание x 3 . Напротив, никакое переименование ( x 1 ∨ ¬ x 2 ∨ ¬ x 3 ) ∧ (¬ x 1 ∨ x 2 ∨ x 3 ) ∧ ¬ x 1 приводит к формуле Хорна. Проверить наличие такой замены можно за линейное время; следовательно, выполнимость таких формул находится в P, поскольку ее можно решить, сначала выполнив эту замену, а затем проверив выполнимость полученной формулы Хорна.

Формула с 2 предложениями может быть неудовлетворенной (красный), 3-удовлетворенной (зеленый), xor-3-удовлетворенной (синий) или / и 1-из-3-удовлетворенной (желтой), в зависимости от количества ИСТИННЫХ буквальных значений в 1-е (гор.) и 2-е (верт.) предложения.

Выполнимость XOR [ править ]

Решение примера XOR-SAT
методом исключения Гаусса
Данная формула
(«⊕» означает XOR, красное предложение не обязательно)
( a ⊕ c ⊕ d ) ∧ ( b ⊕¬ c ⊕ d ) ∧ ( a ⊕ b ⊕¬ d ) ∧ ( a ⊕¬ b ⊕¬ c ) ∧ (¬ a ⊕ b ⊕ c )
Система уравнений
(«1» означает ИСТИНА, «0» означает ЛОЖЬ)
Каждое предложение приводит к одному уравнению.
а⊕c⊕d= 1
б⊕¬c⊕d= 1
а⊕б⊕¬d= 1
а⊕¬б⊕¬c= 1
¬а⊕б⊕c ≃ 1
Нормализованная система уравнений
используя свойства булевых колец (¬ x = 1⊕ x , x ⊕ x = 0)
а⊕c⊕d= 1
б⊕c⊕d= 0
а⊕б⊕d= 0
а⊕б⊕c= 1
а⊕б⊕c≃ 0
(Если красное уравнение присутствует, оно противоречит
последний черный, значит система неразрешима.
Следовательно, алгоритм Гаусса
используется только для черных уравнений.)
Матрица связанных коэффициентов
 
абcdлиния
 
10111А
01110B
11010C
11101D
Преобразование в форму эшелона
 
абcdоперация
 
10111А
11010C
11101D
01110B (поменяно местами)
 
10111А
01101E = C⊕A
01010F = D⊕A
01110B
 
10111А
01101E
00111G = F⊕E
00011H = B⊕E
Преобразование в диагональную форму
 
абcdоперация
 
10100I = A⊕H
01101E
00100J = G⊕H
00011ЧАС
 
10000К = I⊕J
01001L = E⊕J
00100J
00011ЧАС
Решение:
Если красное предложение присутствует:Неразрешимый
Еще:а = 0 = ЛОЖЬ
b = 1 = ИСТИНА
c = 0 = ЛОЖЬ
d = 1 = ИСТИНА
Как следствие:
R ( a , c , d ) ∧ R ( b , ¬ c , d ) ∧ R ( a , b , ¬ d ) ∧ R ( a , ¬ b , ¬ c ) ∧ R (¬ a , b , c )
не выполнимо 1 из 3,
в то время как ( a ∨ c ∨ d ) ∧ ( b ∨ ¬ c ∨ d ) ∧ ( a ∨ b ∨ ¬ d ) ∧ ( a ∨ ¬ b ∨ ¬ c )
3-выполнимо с a = c = FALSE и b = d = TRUE.

Другой частный случай - это класс проблем, где каждое предложение содержит операторы XOR (т.е. исключающее ИЛИ ), а не (простые) операторы ИЛИ. [примечание 5] Это в P , поскольку формула XOR-SAT также может рассматриваться как система линейных уравнений по модулю 2 и может быть решена в кубическом времени методом исключения Гаусса ; [16] см. Пример на рамке. Эта переработка основана на родстве булевых алгебр и булевых колец , а также на том факте, что арифметика по модулю два образует конечное поле . Так как XOR b XOR c оценивается как TRUE тогда и только тогда, когда ровно 1 или 3 члена { a ,b , c } истинны, каждое решение задачи 1-из-3-SAT для данной формулы CNF также является решением проблемы XOR-3-SAT, и, в свою очередь, каждое решение XOR-3-SAT является раствор 3-САТ, ср. рисунок. Как следствие, для каждой формулы CNF можно решить задачу XOR-3-SAT, определенную этой формулой, и на основе результата сделать вывод, что проблема 3-SAT разрешима или что 1-из-3- Проблема SAT неразрешима.

При условии, что классы сложности P и NP не равны , ни 2-, ни Horn-, ни XOR-выполнимость не является NP-полной, в отличие от SAT.

Теорема дихотомии Шефера [ править ]

Основная статья: теорема дихотомии Шефера

Приведенные выше ограничения (CNF, 2CNF, 3CNF, Horn, XOR-SAT) ограничивают рассматриваемые формулы как конъюнкции подформул; каждое ограничение устанавливает определенную форму для всех подформул: например, только двоичные предложения могут быть подформулами в 2CNF.

Теорема Шефера о дихотомии утверждает, что для любого ограничения на булевы операторы, которые могут быть использованы для формирования этих подформул, соответствующая проблема выполнимости находится в P или NP-полной. Принадлежность к P выполнимости формул 2CNF, Horn и XOR-SAT является частным случаем этой теоремы. [12]

В следующей таблице приведены некоторые распространенные варианты SAT.

КодИмяОграниченияТребованияУчебный класс
3СБ3-выполнимостьКаждое предложение содержит 3 литерала.По крайней мере, один литерал должен быть истинным.NPC
2СБ2-выполнимостьКаждое предложение содержит 2 литерала.По крайней мере, один литерал должен быть истинным.п
1-на-3-СБРовно-1 3-СБКаждое предложение содержит 3 литерала.Должен быть истинным ровно один литерал.NPC
1-на-3-СБ +Ровно-1 положительный 3-SATКаждое предложение содержит 3 положительных литерала.Должен быть истинным ровно один литерал.NPC
NAE3SATНе все равно 3-выполнимостьКаждое предложение содержит 3 литерала.Либо один, либо два литерала должны быть истинными.NPC
NAE3SAT +Не все равно положительный 3-SATКаждое предложение содержит 3 положительных литерала.Либо один, либо два литерала должны быть истинными.NPC
PL-SATПланар SATГраф инцидентности (граф условий-переменных) плоский .По крайней мере, один литерал должен быть истинным.NPC
L3SATЛинейный 3-SATКаждое предложение пересекает не более одного другого предложения, и пересечение составляет ровно один литерал.По крайней мере, один литерал должен быть истинным.NPC
HORN-SATРог выполнимостьПредложения Рога (не более одного положительного литерала).По крайней мере, один литерал должен быть истинным.п
XOR-SATXor выполнимостьКаждое предложение содержит операции XOR, а не OR.XOR всех литералов должен быть истинным.п

Расширения SAT [ править ]

Расширение , которое приобрело значительную популярность с 2003 года выполнимость по модулю теория ( SMT ) , которые могут обогатить КНФ формулу с линейными ограничениями, массивами, все различными ограничениями, интерпретированными функциями , [17] и т.д. Такие расширения , как правило , остаются NP-полными, но очень Теперь доступны эффективные решатели, которые могут обрабатывать многие ограничения такого рода.

Проблема выполнимости становится более сложной, если кванторам «для всех» ( ∀ ) и «существует» ( ∃ ) разрешено связывать логические переменные. Примером такого выражения может быть ∀ x ∀ y ∃ z ( x ∨ y ∨ z ) ∧ (¬ x ∨ ¬ y ∨ ¬ z ) ; это действительно, поскольку для всех значений x и y может быть найдено подходящее значение z , а именно. z = ИСТИНА, если и x, и yЛОЖЬ, а z = ЛОЖЬ в противном случае. Сам SAT (неявно) использует только ∃ кванторов. Если вместо этого разрешены только ∀ кванторов, получается так называемая проблема тавтологии , которая является ко-NP-полной . Если разрешены оба квантификатора, проблема называется проблемой квантифицированной логической формулы ( QBF ), которая, как можно показать, является PSPACE-полной . Широко распространено мнение, что PSPACE-полные задачи строго сложнее любых задач в NP, хотя это еще не доказано. Используя высокопараллельные P-системы , задачи QBF-SAT могут быть решены за линейное время. [18]

Обычный тест SAT спрашивает, существует ли хотя бы одно присвоение переменной, которое делает формулу истинной. С количеством таких заданий справляются самые разные варианты:

  • MAJ-SAT спрашивает, является ли формула ИСТИННОЙ в большинстве заданий. Он известен как полный для вероятностного класса PP .
  • #SAT , проблема подсчета количества присвоений переменных, удовлетворяющих формуле, является проблемой подсчета, а не проблемой решения, и является # P-полной .
  • UNIQUE SAT [19] - это проблема определения того, имеет ли формула ровно одно присвоение. Это полное для США , [20] класс сложности описания задач , решаемые недетерминированным полиномиального время машина Тьюринга , которая принимает , когда есть ровно один недетерминирован принимая путь и отбросы иначе.
  • UNAMBIGUOUS-SAT - это название проблемы выполнимости, когда ввод ограничен формулами, имеющими не более одного удовлетворительного присваивания. Проблема также называется USAT . [21] Алгоритм решения для UNAMBIGUOUS-SAT может демонстрировать любое поведение, включая бесконечный цикл, на формуле, имеющей несколько удовлетворительных назначений. Хотя эта проблема кажется более простой, Валиант и Вазирани показали [22], что если существует практический алгоритм (т.е. алгоритм с рандомизированным полиномиальным временем ) для ее решения, то все проблемы NP могут быть решены так же легко.
  • MAX-SAT , проблема максимальной выполнимости , является обобщением SAT с помощью FNP . Требуется максимальное количество предложений, которое может быть выполнено при любом назначении. У него есть эффективные алгоритмы аппроксимации , но точно решить его NP-сложно. Что еще хуже, это APX- полная, то есть для этой задачи не существует схемы полиномиального приближения (PTAS), если только P = NP.
  • WMSAT - это задача нахождения присвоения минимального веса, которое удовлетворяет монотонной булевой формуле (т.е. формуле без отрицания). Веса пропозициональных переменных задаются во входных данных задачи. Вес присвоения - это сумма весов истинных переменных. Эта задача является NP-полной (см. [23], Th. 1 ).

Другие обобщения включают выполнимость для логики первого и второго порядка , проблемы удовлетворения ограничений , целочисленное программирование 0-1 .

Самовосстановление [ править ]

Проблема SAT является самовосстанавливающейся , то есть каждый алгоритм, который правильно отвечает, если экземпляр SAT разрешим, можно использовать для поиска удовлетворительного назначения. Сначала задается вопрос о данной формуле Φ. Если ответ «нет», формула невыполнима. В противном случае задается вопрос о частично созданной формуле Φ { x 1 = TRUE} , т.е. Φ с первой переменной x 1, замененной на TRUE, и соответственно упрощается. Если ответ «да», то x 1 = TRUE, иначе x 1 = FALSE. Таким же образом впоследствии можно найти значения других переменных. Всего требуется n +1 запусков алгоритма, гдеn - количество различных переменных в Φ.

Это свойство самосводимости используется в нескольких теоремах теории сложности:

NP ⊆ P / poly ⇒ PH = Σ 2   ( теорема Карпа – Липтона )
NP ⊆ BPP ⇒ NP = RP
P = NP ⇒ FP = FNP

Алгоритмы решения SAT [ править ]

Поскольку задача SAT является NP-полной, для нее известны только алгоритмы с экспоненциальной сложностью наихудшего случая. Несмотря на это, в 2000-е годы были разработаны эффективные и масштабируемые алгоритмы для SAT, которые способствовали значительному прогрессу в нашей способности автоматически решать экземпляры проблем, включающие десятки тысяч переменных и миллионы ограничений (то есть предложений). [1] Примеры таких проблем в электронной автоматизации проектирования (EDA) включают в себя формальную проверку эквивалентности , проверку модели , формальную проверку на конвейерных микропроцессоров , [17] автоматическую генерацию тестового шаблона , маршрутизации из FPGAs, [24] планирование , задачи составления расписания и так далее. Механизм SAT-решения теперь считается важным компонентом в наборе инструментов EDA .

Решатель DPLL SAT использует процедуру систематического поиска с возвратом для исследования (экспоненциального размера) пространства назначений переменных в поисках подходящих назначений. Базовая процедура поиска была предложена в двух основополагающих статьях в начале 1960-х (см. Ссылки ниже) и сейчас обычно называется алгоритмом Дэвиса – Патнэма – Логеманна – Ловленда («DPLL» или «DLL»). [25] [26] Многие современные подходы к практическому решению SAT основаны на алгоритме DPLL и имеют ту же структуру. Часто они повышают эффективность только определенных классов проблем SAT, таких как экземпляры, которые появляются в промышленных приложениях или случайно сгенерированные экземпляры. [27] Теоретически были доказаны экспоненциальные нижние оценки для семейства алгоритмов DPLL.[ необходима цитата ]

Алгоритмы, не входящие в семейство DPLL, включают алгоритмы стохастического локального поиска . Одним из примеров является WalkSAT . Стохастические методы пытаются найти удовлетворительную интерпретацию, но не могут сделать вывод, что экземпляр SAT неудовлетворителен, в отличие от полных алгоритмов, таких как DPLL. [27]

Напротив, рандомизированные алгоритмы, такие как алгоритм PPSZ Патури, Пудлака, Сакса и Зейна, устанавливают переменные в случайном порядке в соответствии с некоторыми эвристиками, например, с разрешением ограниченной ширины . Если эвристика не может найти правильную настройку, переменная назначается случайным образом. Алгоритм PPSZ имеет время выполнения [ уточнить ] в течение 3-SAT. Это была самая известная среда выполнения для этой проблемы до недавнего улучшения, сделанного Хансеном, Капланом, Замиром и Цвиком, которая имеет время выполнения для 3-SAT и в настоящее время является самой известной средой выполнения для k-SAT для всех значений k. В условиях с множеством удовлетворительных назначений рандомизированный алгоритм Шёнинга имеет лучшую оценку. [10] [28] [29]

Современные решатели SAT (разработанные в 2000-х годах) бывают двух видов: «управляемые конфликтом» и «упреждающие». Оба подхода происходят от DPLL. [27] Управляемые конфликтами решатели, такие как обучение по разделам, управляемое конфликтами (CDCL), дополняют базовый алгоритм поиска DPLL эффективным анализом конфликтов, обучением по разделам , нехронологическим обратным прослеживанием (также известным как обратный переход ), а также «двойным наблюдением- литералы » , адаптивное ветвление и случайные перезапуски. Эти «дополнения» к основному систематическому поиску, как было эмпирически показано, необходимы для обработки больших экземпляров SAT, которые возникают при автоматизации проектирования электронных устройств (EDA). [30]Хорошо известные реализации включают Chaff [31] и GRASP . [32] Упреждающие решатели особенно усилили редукцию (выходящую за рамки распространения единичных предложений) и эвристику, и они, как правило, сильнее, чем решатели, управляемые конфликтами, в жестких экземплярах (в то время как решатели, управляемые конфликтами, могут быть намного лучше в больших экземплярах, которые на самом деле есть легкий экземпляр внутри).

Современные решатели SAT также оказывают значительное влияние на области проверки программного обеспечения, решения ограничений в искусственном интеллекте и исследования операций, среди прочего. Мощные решатели доступны в виде бесплатного программного обеспечения с открытым исходным кодом . В частности, управляемый конфликтом MiniSAT , который был относительно успешным на конкурсе SAT 2005 года , содержит всего около 600 строк кода. Современный решатель Parallel SAT - ManySAT. [33] Он может обеспечить сверхлинейное ускорение на важных классах задач. Примером упреждающего решателя является march_dl , выигравший приз на конкурсе SAT 2007 года .

Определенные типы больших случайных выполнимых экземпляров SAT могут быть решены путем распространения обзора (SP). В частности, в приложениях для проектирования и проверки аппаратных средств выполнимость и другие логические свойства данной пропозициональной формулы иногда определяются на основе представления формулы в виде диаграммы двоичных решений (BDD).

Почти все решатели SAT включают тайм-ауты, поэтому они завершают работу в разумные сроки, даже если не могут найти решение. Разные решатели SAT найдут разные примеры легкими или сложными, и некоторые из них преуспевают в доказательстве неудовлетворенности, а другие в поиске решений. Все это можно увидеть в соревнованиях по решению SAT. [34]

Параллельное решение SAT [ править ]

Параллельные решатели SAT делятся на три категории: портфолио, алгоритмы « разделяй и властвуй» и параллельные алгоритмы локального поиска . В параллельных портфелях одновременно работают несколько различных решателей SAT. Каждый из них решает копию экземпляра SAT, тогда как алгоритмы «разделяй и властвуй» разделяют проблему между процессорами. Существуют разные подходы к распараллеливанию алгоритмов локального поиска.

Международный конкурс Solver СБ имеет параллельный трек , отражающий последние достижения в области параллельного решения SAT. В 2016, [35], 2017 [36] и 2018, [37] тестах выполнялись в системе с общей памятью с 24 ядрами обработки , поэтому решатели, предназначенные для распределенной памяти или многоядерных процессоров, могли не работать .

Портфолио [ править ]

Как правило, не существует решателя SAT, который лучше всех других решает все задачи SAT. Алгоритм может хорошо работать для проблемных экземпляров, с которыми другие борются, но хуже с другими экземплярами. Кроме того, для данного экземпляра SAT нет надежного способа предсказать, какой алгоритм решит этот экземпляр особенно быстро. Эти ограничения мотивируют подход параллельного портфеля. Портфолио - это набор разных алгоритмов или разных конфигураций одного и того же алгоритма. Все решатели в параллельном портфеле работают на разных процессорах для решения одной и той же задачи. Если одна решающая программа завершается, решающая программа портфеля сообщает, что проблема является выполнимой или неудовлетворительной в соответствии с этим решателем. Все остальные решатели прекращают работу. Диверсификация портфелей за счет включения различных решателей,каждая из них хорошо справляется с различным набором задач, что увеличивает надежность решателя.[38]

Многие решатели внутренне используют генератор случайных чисел . Диверсификация семян - простой способ разнообразить портфель. Другие стратегии диверсификации включают включение, отключение или диверсификацию определенных эвристик в последовательном решателе. [39]

Одним из недостатков параллельных портфелей является количество повторяющейся работы. Если в последовательных решателях используется изучение предложений, совместное использование изученных предложений между параллельно работающими решателями может уменьшить дублирование работы и повысить производительность. Тем не менее, даже простой параллельный запуск портфеля лучших решателей делает его конкурентоспособным. Примером такого решателя является PPfolio. [40] [41] Он был разработан, чтобы найти нижнюю границу производительности, которую должен обеспечить параллельный решатель SAT. Несмотря на большой объем повторяющейся работы из-за отсутствия оптимизаций, он хорошо работал на машине с общей памятью. HordeSat [42]- это программа для решения параллельных портфелей для больших кластеров вычислительных узлов. В своей основе он использует по-разному настроенные экземпляры одного и того же последовательного решателя. В частности, для жестких экземпляров SAT HordeSat может обеспечить линейное ускорение и, следовательно, значительно сократить время работы.

В последние годы параллельные портфолио SAT-решателей доминируют в параллельных соревнованиях International SAT Solver Competitions . Известные примеры таких решающих программ включают Plingeling и безболезненные решения. [43]

Разделяй и властвуй [ править ]

В отличие от параллельных портфелей, параллельный принцип разделения и владения пытается разделить пространство поиска между элементами обработки. Алгоритмы «разделяй и властвуй», такие как последовательный DPLL, уже применяют технику разделения пространства поиска, поэтому их расширение в сторону параллельного алгоритма является прямым. Однако из-за таких методов, как распространение единиц, после разделения частичные проблемы могут значительно отличаться по сложности. Таким образом, алгоритм DPLL обычно не обрабатывает каждую часть пространства поиска за одно и то же время, что приводит к сложной проблеме балансировки нагрузки . [38]

Фаза куба для формулы . Эвристика принятия решений выбирает, какие переменные (кружки) назначить. После того, как эвристика отсечения решает прекратить дальнейшее ветвление, частичные проблемы (прямоугольники) решаются независимо с помощью CDCL.

Из-за не хронологического поиска с возвратом распараллеливание обучения по конфликтным предложениям сложнее. Один из способов преодолеть это - парадигма Cube-and-Conquer . [44] Предлагается решение в два этапа. На этапе «куб» Задача разбивается на многие тысячи, до миллионов разделов. Это делается упреждающим решателем, который находит набор частичных конфигураций, называемых «кубами». Куб также можно рассматривать как соединение подмножества переменных исходной формулы. В сочетании с формулой каждый кубик образует новую формулу. Эти формулы могут быть решены независимо и одновременно с помощью решателей, управляемых конфликтами. Поскольку дизъюнкция этих формул эквивалентнак исходной формуле, проблема считается выполнимой, если выполняется одна из формул. Упреждающий решатель подходит для небольших, но сложных задач [45]поэтому он используется для постепенного разделения проблемы на несколько подзадач. Эти подзадачи проще, но все же большие, что является идеальной формой для решателя, управляемого конфликтами. Более того, упреждающие решатели рассматривают всю проблему, тогда как решающие программы, управляемые конфликтами, принимают решения на основе гораздо более локальной информации. В фазе куба задействованы три эвристики. Переменные в кубах выбираются эвристикой принятия решения. Эвристика направления решает, какое присвоение переменной (истинное или ложное) исследовать в первую очередь. В удовлетворительных проблемных случаях полезно сначала выбрать подходящую ветвь. Эвристика отсечения решает, когда прекратить расширение куба и вместо этого перенаправить его последовательному решателю, управляемому конфликтами. Желательно, чтобы кубики были так же сложны для решения. [44]

Treengeling - это пример параллельного решателя, который применяет парадигму Cube-and-Conquer. С момента своего появления в 2012 году он добился множества успехов на Международном конкурсе SAT Solver Competition . Cube-and-Conquer использовался для решения проблемы булевых троек Пифагора . [46]

Локальный поиск [ править ]

Одна из стратегий параллельного алгоритма локального поиска для решения SAT - это одновременное выполнение нескольких переворотов переменных на разных процессорах. [47] Другой вариант - применить вышеупомянутый портфельный подход, однако совместное использование разделов невозможно, поскольку решатели локального поиска не создают разделы. В качестве альтернативы можно совместно использовать конфигурации, произведенные локально. Эти конфигурации могут использоваться для создания новой начальной конфигурации, когда локальный решатель решает перезапустить свой поиск. [48]

См. Также [ править ]

  • Неудовлетворительное ядро
  • Выполнимость по модулю теорий
  • Подсчет SAT
  • Планар SAT
  • Алгоритм Карлоффа-Цвика
  • Выполнимость схемы

Примечания [ править ]

  1. ^ Задача SAT для произвольных формул также является NP-полной, поскольку легко показать, что она находится в NP, и она не может быть проще, чем SAT для формул CNF.
  2. ^ то есть по крайней мере так же сложно, как и любая другая проблема в NP. Проблема решения является NP-полной тогда и только тогда, когда она находится в NP и является NP-сложной.
  3. ^ т.е. такой, что один литерал не является отрицанием другого
  4. ^ а именно. все maxterms, которые могут быть построены с d 1 , ⋯, d k , кроме d 1 ∨ ⋯ ∨ d k
  5. ^ Формально обобщенные конъюнктивные нормальные формы с трехкомпонентной булева оператора R используются, который является TRUEесли только 1 или 3 из его аргументов. Предложение input с более чем 3 литералами может быть преобразовано в равно удовлетворяемое соединение предложений á 3 литерала, аналогичное приведенному выше ; т.е. XOR-SAT может быть сокращен до XOR-3-SAT.

Ссылки [ править ]

  1. ^ a b Охрименко, Ольга; Стаки, Питер Дж .; Кодиш, Майкл (2007), «Распространение = создание ленивых предложений», Принципы и практика программирования с ограничениями - CP 2007 , Lecture Notes in Computer Science, 4741 , pp. 544–558, CiteSeerX  10.1.1.70.5471 , doi : 10.1007 / 978-3-540-74970-7_39 , современные решатели SAT часто могут решать проблемы с миллионами ограничений и сотнями тысяч переменных..
  2. ^ Хонг, Тед; Ли, Яньцзин; Пак, Сунг-Боэм; Муи, Диана; Лин, Дэвид; Калек, Зияд Абдель; Хаким, Нагиб; Наэйми, Хелия; Гарднер, Дональд С .; Митра, Субхасиш (ноябрь 2010 г.). «QED: тесты быстрого обнаружения ошибок для эффективной проверки после кристаллизации». Международная тестовая конференция IEEE 2010 : 1–10. DOI : 10.1109 / TEST.2010.5699215 . ISBN 978-1-4244-7206-2. S2CID  7909084 .
  3. ^ Карп, Ричард М. (1972). «Сводимость среди комбинаторных проблем» (PDF) . В Раймонде Э. Миллере; Джеймс У. Тэтчер (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. С. 85–103. ISBN  0-306-30707-3. Здесь: стр.86
  4. ^ Альфред В. Ахо и Джон Э. Хопкрофт и Джеффри Д. Ульман (1974). Дизайн и анализ компьютерных алгоритмов . Ридинг / МА: Эддисон-Уэсли. ISBN 0-201-00029-6. Здесь: с.403
  5. ^ Vizel, Y .; Weissenbacher, G .; Малик, С. (2015). "Решатели логической выполнимости и их приложения в проверке моделей". Труды IEEE . 103 (11): 2021–2035. DOI : 10.1109 / JPROC.2015.2455034 . S2CID 10190144 . 
  6. ^ Кук, Стивен А. (1971). "Сложность процедур доказательства теорем" (PDF) . Труды 3-го ежегодного симпозиума ACM по теории вычислений : 151–158. CiteSeerX 10.1.1.406.395 . DOI : 10,1145 / 800157.805047 . S2CID 7573663 .   
  7. ^ Левин, Леонид (1973). «Универсальные задачи перебора, Универсальные переборные задачи». Проблемы передачи информации (Русский: Проблемы передачи информации, Проблемы передачи информации) . 9 (3): 115–116. (.pdf) (на русском языке ) , в переводе на английский язык Трахтенбротом, BA (1984). «Обзор российских подходов к алгоритмам перебора». Анналы истории вычислительной техники . 6 (4): 384–400. DOI : 10.1109 / MAHC.1984.10036 . S2CID 950581 . 
  8. ^ a b Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Уллман (1974). Дизайн и анализ компьютерных алгоритмов . Эддисон-Уэсли.; здесь: Thm.10.4
  9. ^ Ахо, Хопкрофт, Ульман [8] (1974); Thm.10.5
  10. ^ a b Шёнинг, Уве (октябрь 1999 г.). «Вероятностный алгоритм для k -SAT и задач удовлетворения ограничений» (PDF) . Proc. 40-я Ann. Symp. Основы компьютерных наук . С. 410–414. DOI : 10,1109 / SFFCS.1999.814612 . ISBN  0-7695-0409-4. S2CID  123177576 .
  11. ↑ Барт Селман; Дэвид Митчелл; Гектор Левеск (1996). «Создание сложных проблем выполнимости». Искусственный интеллект . 81 (1–2): 17–29. CiteSeerX 10.1.1.37.7362 . DOI : 10.1016 / 0004-3702 (95) 00045-3 . 
  12. ^ a b c Шефер, Томас Дж. (1978). «Сложность проблемы выполнимости» (PDF) . Материалы 10-го ежегодного симпозиума ACM по теории вычислений . Сан-Диего, Калифорния. С. 216–226.
  13. ^ (Schaefer, 1978), стр.222, лемма 3.5
  14. ^ Аркин, Эстер М .; Баник, Аритра; Карми, Пас; Цитовски, Гуй; Кац, Мэтью Дж .; Митчелл, Джозеф С.Б. Симаков, Марина (11.12.2018). «Выделение и закрытие цветных точек» . Дискретная прикладная математика . 250 : 75–86. DOI : 10.1016 / j.dam.2018.05.011 . ISSN 0166-218X . 
  15. ^ Бунинг, Гонконг; Карпинский, Марек; Флогель, А. (1995). «Разрешение для количественных булевых формул». Информация и вычисления . Эльзевир. 117 (1): 12–18. DOI : 10.1006 / inco.1995.1025 .
  16. ^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 366, ISBN 9780199233212.
  17. ^ a b Р. Э. Брайант, С. М. Герман и М. Н. Велев, Верификация микропроцессоров с использованием эффективных процедур принятия решений для логики равенства с неинтерпретируемыми функциями , в аналитических таблицах и связанных с ними методах, стр. 1–13, 1999.
  18. ^ Alhazov, Артем; Мартин-Виде, Карлос; Пан, Линьцян (2003). «Решение проблемы PSPACE-Complete путем распознавания P-систем с ограниченными активными мембранами» . Fundamenta Informaticae . 58 : 67–77.
  19. ^ Бласс, Андреас; Гуревич, Юрий (1982-10-01). «О проблеме единственной выполнимости» . Информация и контроль . 55 (1): 80–88. DOI : 10.1016 / S0019-9958 (82) 90439-9 . ISSN 0019-9958 . 
  20. ^ "Зоопарк сложности: U - зоопарк сложности" . сложностьzoo.uwaterloo.ca . Проверено 5 декабря 2019 .
  21. Перейти ↑ Kozen, Dexter C. (2006). «Дополнительная лекция F: Уникальная выполнимость» . Теория вычислений . Тексты по информатике. Лондон: Springer-Verlag. п. 180. ISBN 9781846282973.
  22. ^ Valiant, L .; Вазирани, В. (1986). «NP - это просто найти уникальные решения» (PDF) . Теоретическая информатика . 47 : 85–93. DOI : 10.1016 / 0304-3975 (86) 90135-0 .
  23. ^ Булдас, Ахто; Ленин, Александр; Виллемсон, Ян; Чарнаморд, Антон (2017). Обана, Сатоши; Чида, Коджи (ред.). «Простые справки о невозможности деревьев атак». Достижения в области информационной и компьютерной безопасности . Конспект лекций по информатике. Издательство Springer International. 10418 : 39–55. DOI : 10.1007 / 978-3-319-64200-0_3 . ISBN 9783319642000.
  24. ^ Ги-Джун Нам; Сакаллах, штат Калифорния; Рутенбар, РА (2002). «Новый подход к подробной маршрутизации FPGA с помощью логической выполнимости на основе поиска» (PDF) . IEEE Transactions по автоматизированному проектированию интегральных схем и систем . 21 (6): 674. DOI : 10,1109 / TCAD.2002.1004311 .
  25. ^ Дэвис, М .; Патнэм, Х. (1960). «Вычислительная процедура для теории количественной оценки». Журнал ACM . 7 (3): 201. DOI : 10,1145 / 321033,321034 . S2CID 31888376 . 
  26. ^ Дэвис, М .; Logemann, G .; Лавленд, Д. (1962). "Машинная программа для доказательства теорем" (PDF) . Коммуникации ACM . 5 (7): 394–397. DOI : 10.1145 / 368273.368557 . hdl : 2027 / mdp.39015095248095 . S2CID 15866917 .  
  27. ^ a b c Чжан, Линтао; Малик, Шарад (2002), «Поиски эффективных решателей логической выполнимости», Компьютерная проверка , Springer Berlin Heidelberg, стр. 17–36, DOI : 10.1007 / 3-540-45657-0_2 , ISBN 978-3-540-43997-4
  28. ^ "Улучшенный алгоритм экспоненциального времени для k-SAT" , Патури, Пудлак, Сакс, Зани
  29. ^ "Более быстрые алгоритмы k-SAT с использованием предвзятого PPSZ" , Хансен, Каплан, Замир, Цвик
  30. ^ Vizel, Y .; Weissenbacher, G .; Малик, С. (2015). "Решатели логической выполнимости и их приложения в проверке моделей". Труды IEEE . 103 (11): 2021–2035. DOI : 10.1109 / JPROC.2015.2455034 . S2CID 10190144 . 
  31. ^ Moskewicz, МВт; Мэдиган, CF; Zhao, Y .; Zhang, L .; Малик, С. (2001). "Chaff: Разработка эффективного решателя SAT" (PDF) . Материалы 38-й конференции по автоматизации проектирования (ЦАП) . п. 530. DOI : 10,1145 / 378239,379017 . ISBN  1581132972. S2CID  9292941 .
  32. ^ Маркес-Сильва, JP; Сакаллах, К.А. (1999). «GRASP: алгоритм поиска пропозициональной выполнимости» (PDF) . Транзакции IEEE на компьютерах . 48 (5): 506. DOI : 10,1109 / 12,769433 . Архивировано из оригинального (PDF) 4 ноября 2016 года . Проверено 28 августа 2015 .
  33. ^ http://www.cril.univ-artois.fr/~jabbour/manysat.htm
  34. ^ "Интернет-страница международных соревнований SAT" . Проверено 15 ноября 2007 .
  35. ^ "SAT Competition 2016" . baldur.iti.kit.edu . Проверено 13 февраля 2020 .
  36. ^ "SAT Competition 2017" . baldur.iti.kit.edu . Проверено 13 февраля 2020 .
  37. ^ «SAT Competition 2018» . sat2018.forsyte.tuwien.ac.at . Проверено 13 февраля 2020 .
  38. ^ a b Балё, Томаш; Синц, Карстен (2018), «Параллельная выполнимость», Справочник по обоснованию параллельных ограничений , Springer International Publishing, стр. 3–29, DOI : 10.1007 / 978-3-319-63516-3_1 , ISBN 978-3-319-63515-6
  39. ^ Biere, Armin. «Lingeling, Plingeling, PicoSAT и PrecoSAT на SAT Race 2010» (PDF) . СБ-ГОНКИ 2010 .
  40. ^ "Решатель портфолио" . www.cril.univ-artois.fr . Проверено 29 декабря 2019 .
  41. ^ "Соревнование SAT 2011: трек 32 ядра: рейтинг решателей" . www.cril.univ-artois.fr . Проверено 13 февраля 2020 .
  42. ^ Бальо, Томаш; Сандерс, Питер; Синц, Карстен (2015), «HordeSat: средство решения SAT для массивно параллельных портфелей», конспект лекций по информатике , Springer International Publishing, стр. 156–172, arXiv : 1505.03340 , doi : 10.1007 / 978-3-319-24318- 4_12 , ISBN 978-3-319-24317-7, S2CID  11507540
  43. ^ «SAT Competition 2018» . sat2018.forsyte.tuwien.ac.at . Проверено 13 февраля 2020 .
  44. ^ a b Heule, Marijn JH; Куллманн, Оливер; Wieringa, Siert; Биэр, Армин (2012), «Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads», Hardware and Software: Verification and Testing , Springer Berlin Heidelberg, pp. 50–65, doi : 10.1007 / 978-3-642-34188- 5_8 , ISBN 978-3-642-34187-8
  45. ^ Heule, Marijn JH; ван Маарен, Ханс (2009). "SAT-решатели с упреждением" (PDF) . Справочник по выполнимости . IOS Press. С. 155–184. ISBN  978-1-58603-929-5.
  46. ^ Heule, Marijn JH; Куллманн, Оливер; Марек, Виктор В. (2016), «Решение и проверка булевой проблемы троек Пифагора с помощью куба и завоевания», Теория и приложения проверки выполнимости - SAT 2016 , Springer International Publishing, стр. 228–245, arXiv : 1605.00723 , DOI : 10.1007 / 978-3-319-40970-2_15 , ISBN 978-3-319-40969-6, S2CID  7912943
  47. ^ Roli, Андреа (2002), "Критичность и параллелизм в Structured экземпляров SAT", Принципы и практика программирования в ограничениях - CP 2002 , Lecture Notes в области компьютерных наук, 2470 , Springer Berlin Heidelberg, стр 714-719,. DOI : 10.1007 / 3-540-46135-3_51 , ISBN 978-3-540-44120-5
  48. ^ Arbelaez, Алехандро; Хамади, Юсеф (2011 г.), «Улучшение параллельного локального поиска для SAT», конспект лекций по компьютерным наукам , Springer Berlin Heidelberg, стр. 46–60, DOI : 10.1007 / 978-3-642-25566-3_4 , ISBN 978-3-642-25565-6

Список литературы отсортирован по дате публикации:

  • Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5. A9.1: LO1 - LO7, стр. 259 - 260.
  • Marques-Silva, J .; Гласс, Т. (1999). «Комбинационная проверка эквивалентности с использованием выполнимости и рекурсивного обучения» (PDF) . Конференция и выставка «Дизайн, автоматизация и испытания в Европе», 1999 г. Труды (Кат. № PR00078) (PDF) . п. 145. doi : 10.1109 / DATE.1999.761110 . ISBN 0-7695-0078-1.
  • Clarke, E .; Biere, A .; Raimi, R .; Чжу, Ю. (2001). «Ограниченная проверка модели с использованием решения по выполнимости». Формальные методы в системном дизайне . 19 : 7–34. DOI : 10,1023 / A: 1011276507260 . S2CID  2484208 .
  • Giunchiglia, E .; Такчелла, А. (2004). Джунчилья, Энрико; Такчелла, Армандо (ред.). Теория и приложения проверки выполнимости . Конспект лекций по информатике. 2919 . DOI : 10.1007 / b95238 . ISBN 978-3-540-20851-8. S2CID  31129008 .
  • Бабич, Д .; Bingham, J .; Ху, AJ (2006). «B-Cubing: новые возможности для эффективного решения SAT» (PDF) . Транзакции IEEE на компьютерах . 55 (11): 1315. DOI : 10,1109 / TC.2006.175 . S2CID  14819050 .
  • Rodriguez, C .; Villagra, M .; Баран Б. (2007). «Асинхронные командные алгоритмы для логической выполнимости» (PDF) . 2007 2-е био-модели сетевых, информационных и вычислительных систем . С. 66–69. DOI : 10.1109 / BIMNICS.2007.4610083 . S2CID  15185219 .
  • Карла П. Гомес ; Генри Каутц; Ашиш Сабхарвал; Барт Селман (2008). «Решатели выполнимости». У Фрэнка Ван Хармелена; Владимир Лифшиц; Брюс Портер (ред.). Справочник по представлению знаний . Основы искусственного интеллекта. 3 . Эльзевир. С. 89–134. DOI : 10.1016 / S1574-6526 (07) 03002-7 . ISBN 978-0-444-52211-5.
  • Визель, Ю .; Weissenbacher, G .; Малик, С. (2015). "Решатели логической выполнимости и их приложения в проверке моделей". Труды IEEE . 103 (11): 2021–2035. DOI : 10.1109 / JPROC.2015.2455034 . S2CID  10190144 .

Внешние ссылки [ править ]

  • SAT Game - попробуйте сами решить задачу логической выполнимости

Формат задачи SAT [ править ]

Проблема SAT часто описывается в формате DIMACS-CNF : входном файле, в котором каждая строка представляет собой единственную дизъюнкцию. Например, файл с двумя строками

1-5 4 0-1 5 3 4 0

представляет формулу «( x 1 ∨ ¬ x 5 ∨ x 4 ) ∧ (¬ x 1 ∨ x 5 ∨ x 3 ∨ x 4 )».

Другой распространенный формат этой формулы - это 7-битное представление ASCII "(x1 | ~ x5 | x4) & (~ x1 | x5 | x3 | x4)".

  • BCSAT - это инструмент, который преобразует входные файлы из удобочитаемого формата в формат DIMACS-CNF.

Онлайн-решатели SAT [ править ]

  • BoolSAT - решает формулы в формате DIMACS-CNF или в более удобном для человека формате: «a, а не b или a». Работает на сервере.
  • Logictools - предоставляет различные решатели на JavaScript для обучения, сравнения и взлома. Работает в браузере.
  • minisat-in-your-browser - решает формулы в формате DIMACS-CNF. Работает в браузере.
  • SATRennesPA - решает формулы, написанные в удобной для пользователя форме. Работает на сервере.
  • somerby.net/mack/logic - решает формулы, написанные в символьной логике. Работает в браузере.

Автономные решатели SAT [ править ]

  • MiniSAT - формат DIMACS-CNF и формат OPB для его сопутствующей программы решения псевдобулевых ограничений MiniSat +
  • Лингелинг - выиграл золотую медаль на соревнованиях SAT 2011.
    • PicoSAT - более ранний решатель из группы Lingeling.
  • Sat4j - формат DIMACS-CNF. Доступен исходный код Java.
  • Глюкоза - формат DIMACS-CNF.
  • RSat - выиграл золотую медаль на конкурсе SAT 2007 года.
  • UBCSAT . Поддерживает невзвешенные и взвешенные предложения как в формате DIMACS-CNF. Исходный код C размещен на GitHub .
  • CryptoMiniSat - выиграл золотую медаль в конкурсе SAT 2011 года. Исходный код C ++ размещен на GitHub . Пытается объединить множество полезных функций ядра MiniSat 2.0, PrecoSat ver 236 и Gluosis в один пакет, добавляя множество новых функций.
  • Spear - поддерживает арифметику с битовыми векторами. Может использовать формат DIMACS-CNF или формат Spear .
    • HyperSAT - Создан для экспериментов с сокращением пространства поиска в B-кубах. Занял 3-е место в конкурсе SAT 2005 года. Более ранний и более медленный решатель от разработчиков Spear.
  • BASolver
  • АргоСАТ
  • Fast SAT Solver - основан на генетических алгоритмах .
  • zChaff - больше не поддерживается.
  • BCSAT - удобочитаемый формат логической схемы (также преобразует этот формат в формат DIMACS-CNF и автоматически связывается с MiniSAT или zChaff).
  • gini - язык SAT-решателя Go со связанными инструментами.
  • gophersat - программа SAT-решения на языке Go, которая также может решать проблемы с псевдобулевыми значениями и MAXSAT.
  • CLP (B) - логическое программирование с ограничениями, например SWI-Prolog .

Заявки на SAT [ править ]

  • WinSAT v2.04 : приложение SAT для Windows, созданное специально для исследователей.

Конференции [ править ]

  • Международная конференция по теории и приложениям проверки выполнимости

Публикации [ править ]

  • Журнал по выполнимости, логическому моделированию и вычислениям
  • Распространение обзора

Контрольные показатели [ править ]

  • Принудительные удовлетворительные тесты SAT
  • Тесты проверки программного обеспечения
  • Тесты Fadi Aloul SAT

Решение SAT в целом:

  • http://www.satlive.org
  • http://www.satisfiability.org

Оценка решателей SAT [ править ]

  • Ежегодная оценка решателей SAT
  • Результаты оценки SAT-решателей за 2008 год
  • Международные соревнования SAT
  • История

Дополнительная информация о SAT:

  • SAT и MAX-SAT для непрофессионалов
  • SAT / SMT на примере

В эту статью включены материалы из колонки электронного информационного бюллетеня ACM SIGDA, подготовленной профессором Каремом Сакаллахом.
Оригинальный текст доступен здесь.