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

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

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

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

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

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

Существует несколько частных случаев проблемы булевой выполнимости, в которых требуется, чтобы формулы имели определенную структуру. Буквальным либо переменная, называется положительным буквальным , или отрицание переменной, называется отрицательной буквальным . Раздел является дизъюнкция литералов (или одного буквальным). Предложение называется предложением 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 переменных, последняя состоит из 2 n клозов n переменных.

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

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

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

СБ был первым известным NP-полной проблемой, как доказано Стивен Кук в Университете Торонто в 1971 году [8] и независимо друг от друга Леонида Левина в Национальной академии наук в 1973 г. [9] До этого времени понятие 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 раза длиннее оригинальной, т. Е. Рост длины полиномиален. [10]

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

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

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

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

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 был доказан как NP-полный Томас Джером Шефер как частный случай теоремы Шефера о дихотомии , которая утверждает, что любая проблема, обобщающая булеву выполнимость определенным образом, либо принадлежит классу P, либо является NP- полный. [14]

Шефер дает конструкцию, позволяющую легко за полиномиальное время сократить 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 переменными. [15] Другая редукция включает только четыре свежие переменные и три предложения: R(¬ x , a , b ) ∧ R ( b , y , c ) ∧ R ( c , d , ¬ z ), см. Рисунок (справа).

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

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

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

Линейный SAT [ править ]

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

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

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

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

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

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

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

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

Обобщением класса формул Хорна являются формулы переименовываемого Горна, которые представляют собой набор формул, которые могут быть преобразованы в форму Хорна путем замены некоторых переменных их соответствующим отрицанием. Например, ( 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, поскольку ее можно решить, сначала выполнив эту замену, а затем проверив выполнимость полученной формулы Хорна.

Формула с двумя предложениями может быть неудовлетворенной (красный), 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ЧАС
 
10000K = 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 и может быть решена в кубическом времени методом исключения Гаусса ; [18] см. Пример на рамке. Это преобразование основано на родстве булевых алгебр и булевых колец , а также на том факте, что арифметика по модулю два образует конечное поле . Так как 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 является частным случаем этой теоремы. [14]

В следующей таблице приведены некоторые распространенные варианты 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 ) , которые могут обогатить КНФ формулу с линейными ограничениями, массивами, все различными ограничениями, интерпретированными функциями , [19] и т.д. Такие расширения , как правило , остаются 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 могут быть решены за линейное время. [20]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Неудовлетворительное ядро
  • Выполнимость по модулю теорий
  • Подсчет 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 , который имеет значение ИСТИНА, только если 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. ^ Massacci, Фабио; Марраро, Лаура (1 февраля 2000 г.). «Логический криптоанализ как задача SAT» . Журнал автоматизированных рассуждений . 24 (1): 165–203. DOI : 10,1023 / A: 1006326723002 . ISSN 1573-0670 . 
  6. ^ Миронов, Илья; Чжан, Линтао (2006). Бир, Армин; Гомес, Карла П. (ред.). «Приложения SAT-решателей для криптоанализа хэш-функций» . Теория и приложения проверки выполнимости - SAT 2006 . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 102–115. DOI : 10.1007 / 11814948_13 . ISBN 978-3-540-37207-3.
  7. ^ Vizel, Y .; Weissenbacher, G .; Малик, С. (2015). "Решатели логической выполнимости и их приложения в проверке моделей". Труды IEEE . 103 (11): 2021–2035. DOI : 10.1109 / JPROC.2015.2455034 . S2CID 10190144 . 
  8. ^ Кук, Стивен А. (1971). "Сложность процедур доказательства теорем" (PDF) . Труды 3-го ежегодного симпозиума ACM по теории вычислений : 151–158. CiteSeerX 10.1.1.406.395 . DOI : 10,1145 / 800157.805047 . S2CID 7573663 .   
  9. ^ Левин, Леонид (1973). «Универсальные поисковые задачи». Проблемы передачи информации. Проблемы передачи информации . 9 (3): 115–116. (.pdf) (на русском языке ) , в переводе на английский язык Трахтенбротом, BA (1984). «Обзор российских подходов к алгоритмам перебора». Анналы истории вычислительной техники . 6 (4): 384–400. DOI : 10.1109 / MAHC.1984.10036 . S2CID 950581 . 
  10. ^ a b Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Ульман (1974). Дизайн и анализ компьютерных алгоритмов . Эддисон-Уэсли.; здесь: Thm.10.4
  11. ^ Ахо, Хопкрофт, Ульман [10] (1974); Thm.10.5
  12. ^ 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 .
  13. ^ Барт Селман; Дэвид Митчелл; Гектор Левеск (1996). «Создание сложных проблем выполнимости». Искусственный интеллект . 81 (1–2): 17–29. CiteSeerX 10.1.1.37.7362 . DOI : 10.1016 / 0004-3702 (95) 00045-3 . 
  14. ^ a b c Шефер, Томас Дж. (1978). «Сложность проблемы выполнимости» (PDF) . Материалы 10-го ежегодного симпозиума ACM по теории вычислений . Сан-Диего, Калифорния. С. 216–226.
  15. ^ (Schaefer, 1978), стр.222, лемма 3.5
  16. ^ Аркин, Эстер М .; Баник, Аритра; Карми, Пас; Цитовски, Гуй; Кац, Мэтью Дж .; Митчелл, Джозеф С.Б. Симаков, Марина (11.12.2018). «Выделение и закрытие цветных точек» . Дискретная прикладная математика . 250 : 75–86. DOI : 10.1016 / j.dam.2018.05.011 . ISSN 0166-218X . 
  17. ^ Buning, HK; Карпинский, Марек; Флогель, А. (1995). «Разрешение для количественных булевых формул». Информация и вычисления . Эльзевир. 117 (1): 12–18. DOI : 10.1006 / inco.1995.1025 .
  18. ^ Мур, Кристофер ; Мертенс, Стефан (2011), Природа вычислений , Oxford University Press, стр. 366, ISBN 9780199233212.
  19. ^ a b Р. Э. Брайант, С. М. Герман и М. Н. Велев, Верификация микропроцессоров с использованием эффективных процедур принятия решений для логики равенства с неинтерпретируемыми функциями , в аналитических таблицах и связанных с ними методах, стр. 1–13, 1999.
  20. ^ Alhazov, Артем; Мартин-Виде, Карлос; Пан, Линьцян (2003). «Решение проблемы PSPACE-Complete путем распознавания P-систем с ограниченными активными мембранами» . Fundamenta Informaticae . 58 : 67–77.
  21. ^ Бласс, Андреас; Гуревич, Юрий (1982-10-01). «О проблеме единственной выполнимости» . Информация и контроль . 55 (1): 80–88. DOI : 10.1016 / S0019-9958 (82) 90439-9 . ISSN 0019-9958 . 
  22. ^ "Зоопарк сложности: U - зоопарк сложности" . сложностьzoo.uwaterloo.ca . Проверено 5 декабря 2019 .
  23. Перейти ↑ Kozen, Dexter C. (2006). «Дополнительная лекция F: Уникальная выполнимость» . Теория вычислений . Тексты по информатике. Лондон: Springer-Verlag. п. 180. ISBN 9781846282973.
  24. ^ Valiant, L .; Вазирани, В. (1986). «NP - это просто найти уникальные решения» (PDF) . Теоретическая информатика . 47 : 85–93. DOI : 10.1016 / 0304-3975 (86) 90135-0 .
  25. ^ Булдас, Ахто; Ленин, Александр; Виллемсон, Ян; Чарнаморд, Антон (2017). Обана, Сатоши; Чида, Коджи (ред.). «Простые справки о невозможности атак на деревья». Достижения в области информационной и компьютерной безопасности . Конспект лекций по информатике. Издательство Springer International. 10418 : 39–55. DOI : 10.1007 / 978-3-319-64200-0_3 . ISBN 9783319642000.
  26. ^ Ги-Джун Нам; Сакаллах, штат Калифорния; Рутенбар, РА (2002). «Новый подход к подробной маршрутизации FPGA с помощью логической выполнимости на основе поиска» (PDF) . IEEE Transactions по автоматизированному проектированию интегральных схем и систем . 21 (6): 674. DOI : 10,1109 / TCAD.2002.1004311 .
  27. ^ Дэвис, М .; Патнэм, Х. (1960). «Вычислительная процедура для теории количественной оценки». Журнал ACM . 7 (3): 201. DOI : 10,1145 / 321033,321034 . S2CID 31888376 . 
  28. ^ Дэвис, М .; Logemann, G .; Лавленд, Д. (1962). "Машинная программа для доказательства теорем" (PDF) . Коммуникации ACM . 5 (7): 394–397. DOI : 10.1145 / 368273.368557 . hdl : 2027 / mdp.39015095248095 . S2CID 15866917 .  
  29. ^ a b c Чжан, Линтао; Малик, Шарад (2002), «Поиски эффективных решателей логической выполнимости», Компьютерная проверка , Springer Berlin Heidelberg, стр. 17–36, DOI : 10.1007 / 3-540-45657-0_2 , ISBN 978-3-540-43997-4
  30. ^ "Улучшенный алгоритм экспоненциального времени для k-SAT" , Патури, Пудлак, Сакс, Зани
  31. ^ "Более быстрые алгоритмы k-SAT с использованием предвзятого PPSZ" , Хансен, Каплан, Замир, Цвик
  32. ^ Vizel, Y .; Weissenbacher, G .; Малик, С. (2015). "Решатели логической выполнимости и их приложения в проверке моделей". Труды IEEE . 103 (11): 2021–2035. DOI : 10.1109 / JPROC.2015.2455034 . S2CID 10190144 . 
  33. ^ Moskewicz, МВт; Мэдиган, CF; Zhao, Y .; Zhang, L .; Малик, С. (2001). "Chaff: Разработка эффективного решателя SAT" (PDF) . Материалы 38-й конференции по автоматизации проектирования (DAC) . п. 530. DOI : 10,1145 / 378239,379017 . ISBN  1581132972. S2CID  9292941 .
  34. ^ Маркес-Сильва, JP; Сакаллах, К.А. (1999). «GRASP: алгоритм поиска пропозициональной выполнимости» (PDF) . Транзакции IEEE на компьютерах . 48 (5): 506. DOI : 10,1109 / 12,769433 . Архивировано из оригинального (PDF) 4 ноября 2016 года . Проверено 28 августа 2015 .
  35. ^ http://www.cril.univ-artois.fr/~jabbour/manysat.htm
  36. ^ "Интернет-страница международных соревнований SAT" . Проверено 15 ноября 2007 .
  37. ^ «SAT Competition 2016» . baldur.iti.kit.edu . Проверено 13 февраля 2020 .
  38. ^ "SAT Competition 2017" . baldur.iti.kit.edu . Проверено 13 февраля 2020 .
  39. ^ «SAT Competition 2018» . sat2018.forsyte.tuwien.ac.at . Проверено 13 февраля 2020 .
  40. ^ a b Балё, Томаш; Синц, Карстен (2018), «Параллельная выполнимость», Справочник по обоснованию параллельных ограничений , Springer International Publishing, стр. 3–29, DOI : 10.1007 / 978-3-319-63516-3_1 , ISBN 978-3-319-63515-6
  41. ^ Biere, Armin. «Lingeling, Plingeling, PicoSAT и PrecoSAT на SAT Race 2010» (PDF) . СБ-ГОНКИ 2010 .
  42. ^ "Решатель портфолио" . www.cril.univ-artois.fr . Проверено 29 декабря 2019 .
  43. ^ "Соревнование SAT 2011: трек 32 ядра: рейтинг решателей" . www.cril.univ-artois.fr . Проверено 13 февраля 2020 .
  44. ^ Бальо, Томаш; Сандерс, Питер; Синц, Карстен (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
  45. ^ «SAT Competition 2018» . sat2018.forsyte.tuwien.ac.at . Проверено 13 февраля 2020 .
  46. ^ 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
  47. ^ Heule, Marijn JH ; ван Маарен, Ханс (2009). «Предвидящие SAT-решатели» (PDF) . Справочник по выполнимости . IOS Press. С. 155–184. ISBN  978-1-58603-929-5.
  48. ^ 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
  49. ^ Роли, Андреа (2002), «Критичность и параллелизм в структурированных экземплярах SAT», Принципы и практика программирования с ограничениями - CP 2002 , Lecture Notes in Computer Science, 2470 , Springer Berlin Heidelberg, стр. 714–719, doi : 10.1007 / 3-540-46135-3_51 , ISBN 978-3-540-44120-5
  50. ^ Arbeláez, Алехандро; Хамади, Юсеф (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, подготовленной профессором Каремом Сакаллахом.
Оригинальный текст доступен здесь.