Problem spełnialności logicznej - Boolean satisfiability problem

W logiki oraz informatyce The problem spełnialności (czasami nazywane propositional problemem spełnialności i skrócona spełnialności , SAT lub B-SAT ) jest Problem określenia, czy istnieje interpretację , że spełnia dany logiczny wzór . Innymi słowy, pyta, czy zmienne danej formuły logicznej mogą być konsekwentnie zastępowane wartościami PRAWDA lub FAŁSZ w taki sposób, aby formuła dała wynik PRAWDA . W takim przypadku formuła nazywa się satisfiable. Z drugiej strony, jeśli takie przypisanie nie istnieje, funkcja wyrażona przez formułę ma wartość FAŁSZ dla wszystkich możliwych przypisań zmiennych, a formuła jest niezaspokojona . Na przykład formuła „ a AND NOT b ” jest spełniona, ponieważ można znaleźć wartości a  = TRUE i b  = FALSE, które sprawiają, że ( a AND NOT b ) = TRUE. Natomiast „ a AND NOT a ” jest niezadowalające.

SAT jest pierwszym problemem, który okazał się NP-zupełny ; zobacz Twierdzenie Cooka-Levina . Oznacza to, że wszystkie problemy w klasie złożoności NP , która obejmuje szeroki zakres naturalnych problemów decyzyjnych i optymalizacyjnych, są co najwyżej tak trudne do rozwiązania jak SAT. Nie ma znanego algorytmu, który skutecznie rozwiązuje każdy problem SAT i ogólnie uważa się, że taki algorytm nie istnieje; jednak przekonanie to nie zostało udowodnione matematycznie, a rozwiązanie kwestii, czy SAT ma algorytm wielomianowy , jest równoważne z problemem P versus NP , który jest znanym otwartym problemem w teorii obliczeń.

Niemniej jednak od 2007 r. heurystyczne algorytmy SAT są w stanie rozwiązywać przypadki problemów obejmujące dziesiątki tysięcy zmiennych i formuł składających się z milionów symboli, co jest wystarczające dla wielu praktycznych problemów SAT, takich jak np. sztuczna inteligencja , projektowanie obwodów i automatyka. dowodzenie twierdzenia .

Podstawowe definicje i terminologia

Propositional logiczny wzór , zwany także logicznego, jest zbudowany z zmiennych , operatorów i ( wspólnie , również oznaczony ∧) lub ( alternatywy , ∨) nie ( negacji , Ź) i nawiasy. Mówi się, że formuła jest spełnialna, jeśli można ją uczynić PRAWDA poprzez przypisanie odpowiednich wartości logicznych (tj. PRAWDA, FAŁSZ) do jej zmiennych. Problem spełnialności (SAT) jest, biorąc pod uwagę wzór, w celu sprawdzenia, czy jest obsłużenia. Ten problem decyzyjny ma kluczowe znaczenie w wielu dziedzinach informatyki , w tym w informatyce teoretycznej , teorii złożoności , algorytmice , kryptografii i sztucznej inteligencji .

Istnieje kilka szczególnych przypadków problemu spełnialności logicznej, w których formuły muszą mieć określoną strukturę. Dosłowny jest albo zmienna, zwany dodatni dosłowny lub negacją zmiennej, zwany negatywny dosłowny . Punkt jest alternatywą literałach (lub jedno dosłownym). Klauzula nazywana jest klauzulą ​​Horn, jeśli zawiera co najwyżej jeden pozytywny literał. Formuła ma postać koniunkcji normalnej (CNF), jeśli jest połączeniem klauzul (lub pojedynczej klauzuli). Na przykład x ₁ to literał dodatni, ¬ x ₂ to literał ujemny, x ₁ ∨ ¬ x ₂ to zdanie. Formuła ( x ₁ ∨ ¬ x ₂ ) ∧ (¬ x ₁ ∨ x ₂ ∨ x ₃ ) ∧ ¬ x ₁ jest w postaci normalnej koniunkcji; jego pierwsza i trzecia klauzula są klauzulami Horn, ale druga klauzula nie. Formuła jest spełnialna, wybierając x ₁  = FAŁSZ, x ₂  = FAŁSZ i x ₃ arbitralnie, ponieważ (FAŁSZ ∨ ¬FAŁSZ) ∧ (¬FAŁSZ ∨ FAŁSZ ∨ x ₃ ) ∧ ¬FAŁSZ daje (FAŁSZ ∨ PRAWDA) ∧ (PRAWDA ∨ FAŁSZ ∨ x ₃ ) ∧ PRAWDA, a następnie na PRAWDA ∧ PRAWDA ∧ PRAWDA (tzn. na PRAWDA). W odróżnieniu od tego wzór CNF ∧ Kontakty , składający się z dwóch punktach jednego dosłownym jest unsatisfiable, ponieważ dla = PRAWDA lub = False wartość TRUE ∧ ¬TRUE (tj FAŁSZ) lub fałszywe ∧ ¬FALSE (tj , ponownie FAŁSZ).

W przypadku niektórych wersji problemu SAT przydatne jest zdefiniowanie pojęcia uogólnionej formuły spójnej postaci normalnej , a mianowicie. w połączeniu z dowolnie wielu punktach ogólny , przy czym ten ostatni w postaci R ( l ₁ , ..., l _n ) dla jakiegoś logicznego funkcyjnej R oraz (zwykłe) literałami l _i . Różne zestawy dozwolonych funkcji logicznych prowadzą do różnych wersji problemów. Na przykład R (¬ x , a , b ) jest klauzulą ​​uogólnioną, a R (¬ x , a , b ) ∧ R ( b , y , c ) ∧ R ( c , d ,¬ z ) jest uogólnionym spójna forma normalna. Ta formuła jest używana poniżej , gdzie R jest operatorem trójskładnikowym, który ma wartość TRUE tylko wtedy, gdy jest dokładnie jeden z jego argumentów.

Korzystając z praw algebry Boole'a , każda formuła logiki zdaniowej może zostać przekształcona w równoważną spójną postać normalną, która może być jednak wykładniczo dłuższa. Na przykład, przekształcenie wzoru ( x ₁ ∧ y ₁ ) ∨ ( x ₂ ∧ y ₂ ) ∨ ... ∨ ( x _n ∧ y _n ) na spójną formę normalną daje

( x ₁  ∨  x ₂  ∨ … ∨  x _n ) ∧

( y ₁  ∨  x ₂  ∨ … ∨  x _n ) ∧

( x ₁  ∨  y ₂  ∨ … ∨  x _n ) ∧

( y ₁  ∨  y ₂  ∨ … ∨  x _n ) ∧ ... ∧

( x ₁  ∨  x ₂  ∨ … ∨  y _n ) ∧

( y ₁  ∨  x ₂  ∨ … ∨  y _n ) ∧

( x ₁  ∨  y ₂  ∨ … ∨  y _n ) ∧

( Y ₁  ∨  Y ₂  ∨ ... ∨  y _n ) ;

podczas gdy pierwsza jest alternatywą n koniunkcji 2 zmiennych, druga składa się z 2 ⁿ klauzul n zmiennych.

Złożoność i ograniczone wersje

Nieograniczona satysfakcja (SAT)

SAT był pierwszym znanym problemem NP-zupełnym , co udowodnił Stephen Cook na Uniwersytecie w Toronto w 1971 roku i niezależnie Leonid Levin z Narodowej Akademii Nauk w 1973 roku. Do tego czasu koncepcja problemu NP-zupełnego nie była nawet istnieją. Dowód pokazuje, jak każdy problem decyzyjny w klasie złożoności NP można sprowadzić do problemu SAT dla formuł CNF, czasami nazywanego CNFSAT . Przydatną właściwością redukcji Cooka jest to, że zachowuje liczbę akceptujących odpowiedzi. Na przykład rozstrzygnięcie, czy dany wykres ma trójkolorowe, to kolejny problem w NP; jeśli wykres ma 17 prawidłowych 3-kolorowań, formuła SAT uzyskana przez redukcję Cooka-Levina będzie miała 17 satysfakcjonujących przypisań.

Kompletność NP odnosi się tylko do czasu wykonywania najgorszych przypadków. Wiele przypadków występujących w praktycznych zastosowaniach można rozwiązać znacznie szybciej. Zobacz Algorytmy rozwiązywania SAT poniżej.

SAT jest trywialny, jeśli formuły są ograniczone do tych w rozłącznej formie normalnej , to znaczy są rozłączeniem koniunkcji literałów. Taka formuła jest rzeczywiście spełnialna wtedy i tylko wtedy, gdy przynajmniej jedna z jej koniunkcji jest spełnialna, a koniunkcja jest spełnialna wtedy i tylko wtedy, gdy nie zawiera zarówno x, jak i NIE x dla jakiejś zmiennej x . Można to sprawdzić w czasie liniowym. Ponadto, jeśli są ograniczone do bycia w pełnej rozłącznej postaci normalnej , w której każda zmienna pojawia się dokładnie raz w każdej koniunkcji, mogą być sprawdzane w stałym czasie (każda koniunkcja reprezentuje jedno satysfakcjonujące przypisanie). Ale przekształcenie ogólnego problemu SAT w rozłączną formę normalną może zająć wykładnicze czas i przestrzeń; na przykład zamień "∧" i "∨" w powyższym przykładzie wykładniczym dla spójnych form normalnych.

3-satysfakcja

Instancja 3-SAT ( x ∨ x ∨ y ) ∧ ( ¬ x ∨ ¬ y ∨ ¬ y ) ∧ ( ¬ x ∨ y ∨ y ) zredukowana do problemu kliki . Zielone wierzchołki tworzą 3-klikę i odpowiadają satysfakcjonującemu przypisaniu x =FALSE, y =TRUE.

Podobnie jak problem spełnialności dla dowolnych formuł, określanie spełnialności formuły w spójnej postaci normalnej, gdzie każda klauzula jest ograniczona do co najwyżej trzech literałów, również jest NP-zupełne; ten problem nazywa się 3-SAT , 3CNFSAT lub 3-satisfiability . Aby zredukować nieograniczony problem SAT do 3-SAT, przekształć każdą klauzulę l ₁ ∨ ⋯ ∨ l _n w koniunkcję n - 2 klauzul

( l ₁ ∨ l ₂ ∨ x ₂ ) ∧

(¬ x ₂ ∨ l ₃ ∨ x ₃ ) ∧

(¬ x ₃ ∨ l ₄ ∨ x ₄ ) ∧ ⋯ ∧

(¬ x _{n − 3} ∨ l _{n − 2} ∨ x _{n − 2} ) ∧

(¬ x _{n − 2} ∨ l _{n − 1} ∨ l _n )

gdzie x ₂ , ⋯ ,  x _{n − 2} są świeżymi zmiennymi nie występującymi gdzie indziej. Chociaż te dwie formuły nie są logicznie równoważne , są równoważne . Formuła wynikająca z przekształcenia wszystkich klauzul jest najwyżej 3 razy dłuższa od jej oryginału, tzn. przyrost długości jest wielomianowy.

3-SAT jest jednym z 21 problemów NP-zupełnych Karpa i jest używany jako punkt wyjścia do wykazania, że ​​inne problemy również są NP-trudne . Odbywa się to poprzez redukcję czasu wielomianowego z 3-SAT do innego problemu. Przykładem problemu, w którym zastosowano tę metodę, jest problem kliki : biorąc pod uwagę formułę CNF składającą się z c klauzul, odpowiadający graf składa się z wierzchołka dla każdego literału i krawędzi między każdym z dwóch niesprzecznych literałów z różnych klauzul, por. zdjęcie. Wykres ma klikę c wtedy i tylko wtedy, gdy formuła jest spełnialna.

Istnieje prosty algorytm losowy, dzięki Schöningowi (1999), który działa w czasie (4/3) ^n, gdzie n jest liczbą zmiennych w propozycji 3-SAT i z dużym prawdopodobieństwem skutecznie decyduje o 3-SAT.

Wykładniczy hipoteza czasu zapewnia, że żaden algorytm może rozwiązać 3-SAT (lub nawet k -sat dla każdego ) w exp ( O ( n )), czas (tj zasadniczo szybciej niż wykładniczy w N ). ${\displaystyle k>2}$

Selman, Mitchell i Levesque (1996) podają dane empiryczne dotyczące trudności losowo generowanych formuł 3-SAT, w zależności od ich parametrów wielkości. Trudność mierzona jest liczbą wywołań rekurencyjnych wykonywanych przez algorytm DPLL .

3-satisfiability można uogólnić na k-satisfiability ( k-SAT , również k-CNF-SAT ), gdy formuły w CNF są brane pod uwagę z każdą klauzulą ​​zawierającą do k literałów. Jednakże, ponieważ dla dowolnego k ≥ 3, ten problem nie może być ani łatwiejszy niż 3-SAT, ani trudniejszy niż SAT, a dwa ostatnie są NP-zupełne, więc musi być k-SAT.

Niektórzy autorzy ograniczają k-SAT do formuł CNF z dokładnie k literałami . Nie prowadzi to również do innej klasy złożoności, ponieważ każda klauzula l ₁ ∨ ⋯ ∨ l _j z literałami j < k może być uzupełniona stałymi fikcyjnymi zmiennymi do l ₁ ∨ ⋯ ∨ l _j ∨ d _{j +1} ∨ ⋯ ∨ d _k . Po uzupełnieniu wszystkich klauzul należy dołączyć dodatkowe klauzule 2 ^k -1, aby zapewnić, że tylko d ₁ = ⋯ = d _k = FALSE może prowadzić do satysfakcjonującego przypisania. Ponieważ k nie zależy od długości formuły, dodatkowe klauzule prowadzą do stałego wzrostu długości. Z tego samego powodu nie ma znaczenia, czy zduplikowane literały są dozwolone w klauzulach, jak w ¬ x ∨ ¬ y ∨ ¬ y .

Dokładnie-1 3-spełnialność

Po lewej: redukcja Schaefera klauzuli 3-SAT x ∨ y ∨ z . Wynikiem R jest PRAWDA (1), jeśli dokładnie jeden z jego argumentów ma wartość PRAWDA, a FAŁSZ (0) w przeciwnym razie. Wszystkie 8 kombinacji wartości x , y , z są sprawdzane, po jednej w wierszu. Świeże zmienne a ,..., f mogą być wybrane tak, aby spełniały wszystkie klauzule (dokładnie jeden zielony argument dla każdego R ) we wszystkich wierszach z wyjątkiem pierwszego, gdzie x ∨ y ∨ z jest FAŁSZ. Po prawej: prostsza redukcja z tymi samymi właściwościami.

Wariantem problemu 3 spełnialności jest jeden na trzy 3-SAT (znany również jako 1-w-3-SAT i dokładnie-1 3-SAT ). Mając spójną postać normalną z trzema literałami na klauzulę, problem polega na ustaleniu, czy istnieje przypisanie prawdy do zmiennych, tak aby każda klauzula miała dokładnie jeden literał PRAWDA (a zatem dokładnie dwa literały FAŁSZ). W przeciwieństwie do tego, zwykły 3-SAT wymaga, aby każda klauzula miała co najmniej jeden literał TRUE. Formalnie, problem 3-SAT jeden na trzy jest podany jako uogólniona spójna forma normalna ze wszystkimi uogólnionymi klauzulami przy użyciu operatora trójskładnikowego R, który jest PRAWDA, jeśli dokładnie jeden z jego argumentów jest. Gdy wszystkie literały formuły jeden na trzy 3-SAT są dodatnie, problem spełnialności jest nazywany dodatnim 3-SAT jeden na trzy .

Jeden na trzy 3-SAT, wraz z jego pozytywnym przypadkiem, jest wymieniony jako problem NP-zupełny „LO4” w standardowym odnośniku Computers and Intractability: A Guide to the Theory of NP-Completeness autorstwa Michaela R. Gareya i Davida S. Johnsona . Jeden na trzy 3-SAT okazał się NP-zupełny przez Thomasa Jerome'a ​​Schaefera jako szczególny przypadek twierdzenia o dychotomii Schaefera , które twierdzi, że każdy problem uogólniający w pewien sposób spełnialność Boole'a należy albo do klasy P, albo jest NP- kompletny.

Schaefer daje konstrukcję umożliwiającą łatwą redukcję czasu wielomianowego z 3-SAT do jednego na trzy 3-SAT. Niech „( x lub y lub z )” będzie klauzulą ​​we wzorze 3CNF. Dodaj sześć świeżych zmiennych logicznych a , b , c , d , e i f , które będą używane do symulowania tej klauzuli, a nie innych. Wtedy wzór R ( x , a , d ) ∧ R ( y , b , d ) ∧ R ( a , b , e ) ∧ R ( c , d , f ) ∧ R ( z , c , FALSE ) jest spełniony przez pewne ustawienie świeżych zmiennych wtedy i tylko wtedy, gdy co najmniej jedna z wartości x , y lub z ma wartość TRUE, patrz rysunek (po lewej). W ten sposób każde wystąpienie 3-SAT z klauzulami m i n zmiennymi może zostać przekonwertowane na równoważne wystąpienie 3-SAT z 5 m i n +6 m zmiennymi. Dalsze obniżenie obejmuje jedynie cztery świeże zmienne i trzy punktach: R (Ź x , , b ) ∧ R ( b , r , c ) ∧ R ( c , d , Ź oo ), patrz rysunek (po prawej).

Nie wszystkie równe 3-spełnialność

Innym wariantem jest problem 3-spełnialności „nie wszystkie równe” (zwany również NAE3SAT ). Mając spójną formę normalną z trzema literałami w klauzuli, problem polega na ustaleniu, czy przypisanie do zmiennych istnieje w taki sposób, że w żadnej klauzuli wszystkie trzy literały mają tę samą wartość logiczną. Ten problem jest również NP-zupełny, nawet jeśli nie są dopuszczone żadne symbole negacji, zgodnie z twierdzeniem o dychotomii Schaefera.

Liniowy SAT

Formuła 3-SAT to Linear SAT ( LSAT ), jeśli każda klauzula (traktowana jako zbiór literałów) przecina co najwyżej jedną inną klauzulę, a ponadto, jeśli dwie klauzule przecinają się, mają one dokładnie jeden wspólny literał. Formuła LSAT może być przedstawiona jako zbiór rozłącznych półzamkniętych przedziałów na linii. Decyzja, czy formuła LSAT jest satysfakcjonująca, czy nie, jest NP-zupełna.

2-satysfakcja

SAT jest łatwiejsze, jeśli liczba literałów w klauzuli jest ograniczona do co najwyżej 2, w którym to przypadku problem nazywa się 2-SAT . Problem ten można rozwiązać w czasie wielomianowym iw rzeczywistości jest kompletny dla klasy złożoności NL . Jeśli dodatkowo wszystkie operacje OR w literałach zostaną zmienione na operacje XOR , wynik zostanie nazwany exclusive-or 2-satisfiability , co jest problemem kompletnym dla klasy złożoności SL = L .

Horn-spełnialność

Problem rozstrzygnięcia spełnialności danej koniunkcji klauzul Horna nazywa się Horn-satisfiability lub HORN-SAT . Można go rozwiązać w czasie wielomianowym za pomocą pojedynczego kroku algorytmu propagacji jednostek , który tworzy pojedynczy minimalny model zbioru klauzul Horna (wrt zbioru literałów przypisanych do TRUE). Spełnialność rogów jest P-zupełna . Można to postrzegać jako wersję P problemu spełnialności logicznej. Ponadto, decydowanie o prawdziwości kwantyfikowanych wzorów Horna można przeprowadzić w czasie wielomianowym.

Klauzule Horn są interesujące, ponieważ są w stanie wyrazić implikację jednej zmiennej ze zbioru innych zmiennych. Rzeczywiście, jedną taką klauzulę ¬ x ₁ ∨ ... ∨ ¬ x _n ∨ y można przepisać jako x ₁ ∧ ... ∧ x _n → y , to znaczy, jeśli x ₁ ,..., x _n są PRAWDĄ , to y również musi być PRAWDA.

Uogólnienie klasy formuł Horna to formuły z możliwością zmiany nazwy, które są zbiorem formuł, które można umieścić w formie Horna, zastępując niektóre zmienne ich odpowiednią negacją. Na przykład ( x ₁ ∨ ¬ x ₂ ) ∧ (¬ x ₁ ∨ x ₂ ∨ x ₃ ) ∧ ¬ x ₁ nie jest formułą Horn, ale można ją zmienić na formułę Horn ( x ₁ ∨ ¬ x ₂ ) ∧ (¬ x ₁ ∨ x ₂ ∨ ¬ y ₃ ) ∧ ¬ x ₁ wprowadzając y ₃ jako negację x ₃ . W przeciwieństwie do tego, brak zmiany nazwy ( x ₁ ∨ ¬ x ₂ ∨ ¬ x ₃ ) ∧ (¬ x ₁ ∨ x ₂ ∨ x ₃ ) ¬ ¬ x ₁ prowadzi do formuły Horn. Sprawdzenie istnienia takiej zamiany można przeprowadzić w czasie liniowym; dlatego spełnialność takich formuł jest w P, ponieważ można ją rozwiązać, najpierw wykonując to zastąpienie, a następnie sprawdzając spełnialność otrzymanego wzoru Horna.

Formuła z 2 klauzulami może być niezadowolona (czerwona), 3-spełniona (zielona), xor-3-satisfied (niebieski) lub/i 1-w-3-satisfied (żółty), w zależności od liczby PRAWDZIWYCH liter w zdanie 1 (hor) i 2 (vert).

XOR-spełnialność

Innym szczególnym przypadkiem jest klasa problemów, w której każda klauzula zawiera operatory XOR (tj. wykluczające lub ) zamiast (zwykłych) operatorów OR. To jest w P , ponieważ wzór XOR-SAT może być również postrzegany jako układ równań liniowych mod 2 i może być rozwiązany w czasie sześciennym przez eliminację Gaussa ; zobacz ramkę na przykład. Przekształcenie to opiera się na pokrewieństwie między algebrami Boole'a a pierścieniami Boole'a oraz na fakcie, że arytmetyczne modulo dwa tworzy ciało skończone . Ponieważ a XOR b XOR c ma wartość TRUE wtedy i tylko wtedy, gdy dokładnie 1 lub 3 elementy { a , b , c } są PRAWDZIWE, każde rozwiązanie problemu 1-w-3-SAT dla danej formuły CNF jest również rozwiązaniem problemu XOR-3-SAT, a z kolei każde rozwiązanie XOR-3-SAT jest rozwiązaniem 3-SAT, por. zdjęcie. W konsekwencji, dla każdej formuły CNF, możliwe jest rozwiązanie problemu XOR-3-SAT zdefiniowanego wzorem i na podstawie wyniku wywnioskować, że problem 3-SAT jest rozwiązywalny lub że 1-w-3- Problem SAT jest nie do rozwiązania.

Zakładając, że klasy złożoności P i NP nie są równe , ani 2-, ani Horn-, ani XOR-spełnialność nie jest NP-zupełna, w przeciwieństwie do SAT.

Twierdzenie o dychotomii Schaefera

Powyższe ograniczenia (CNF, 2CNF, 3CNF, Horn, XOR-SAT) wiążą rozważane formuły jako koniunkcje podformuł; każde ograniczenie stanowi określoną formę dla wszystkich podformuł: na przykład tylko klauzule binarne mogą być podformułami w 2CNF.

Twierdzenie o dychotomii Schaefera stwierdza, że ​​dla każdego ograniczenia funkcji logicznych, które można wykorzystać do utworzenia tych podformułów, odpowiedni problem spełnialności występuje w P lub NP-zupełnym. Członkostwo w P spełnialności formuł 2CNF, Horn i XOR-SAT są szczególnymi przypadkami tego twierdzenia.

Poniższa tabela podsumowuje niektóre typowe warianty SAT.

Rozszerzenia SAT

Rozszerzenie który zyskał znaczną popularność od 2003 roku jest teorie spełnialności modulo ( SMT ), które mogą wzbogacić formuły CNF z ograniczeniami liniowymi, tablic, wszystko różnych ograniczeń, funkcji zinterpretowane , etc. Takie rozszerzenia zwykle pozostają NP-zupełny, ale bardzo wydajne rozwiązują są teraz dostępny, który może obsługiwać wiele takich rodzajów ograniczeń.

Problem spełnialności staje się trudniejszy, jeśli zarówno kwantyfikatory „dla wszystkich” ( ∀ ) jak i „istnieje” ( ∃ ) mogą wiązać zmienne logiczne. Przykładem takiego wyrażenia byłoby ∀ x ∀ y ∃ z ( x ∨ y ∨ z ) ∧ ( ¬ x ∨ ¬ y ∨ ¬ z ) ; jest poprawny, ponieważ dla wszystkich wartości x i y można znaleźć odpowiednią wartość z , mianowicie. z =PRAWDA, jeśli zarówno x, jak i y są FAŁSZ, a z =FAŁSZ w przeciwnym razie. Sam SAT (po cichu) używa tylko kwantyfikatorów ∃. Jeśli zamiast tego dozwolone są tylko kwantyfikatory ∀, uzyskuje się tak zwany problem tautologiczny , który jest współ-NP-zupełny . Jeśli oba kwantyfikatory są dozwolone, problem nazywa się kwantyfikowanym problemem ze wzorem logicznym ( QBF ), który można wykazać, że jest zupełny PSPACE . Powszechnie uważa się, że problemy z całkowitym PSPACE są ściśle trudniejsze niż jakikolwiek problem w NP, chociaż nie zostało to jeszcze udowodnione. Używając wysoce równoległych systemów P , problemy QBF-SAT można rozwiązywać w czasie liniowym.

Zwykła SAT pyta, czy istnieje co najmniej jedno przypisanie zmiennej, które sprawia, że ​​formuła jest prawdziwa. Różne warianty radzą sobie z liczbą takich zadań:

• MAJ-SAT pyta, czy większość wszystkich zadań sprawia, że ​​formuła jest PRAWDA. Wiadomo, że jest kompletny dla PP , klasy probabilistycznej.
• #SAT , problem liczenia, ile przypisań zmiennych spełnia formułę, jest problemem liczenia, a nie problemem decyzyjnym i jest #P-zupełne .
• UNIQUE SAT to problem określenia, czy formuła ma dokładnie jedno przypisanie. Jest kompletny dla US , klasy złożoności opisującej problemy rozwiązywalne przez niedeterministyczną wielomianową maszynę Turinga, która akceptuje, gdy istnieje dokładnie jedna niedeterministyczna ścieżka akceptacji, a odrzuca w przeciwnym razie.
• UNAMBIGUOUS-SAT to nazwa nadana problemowi spełnialności, gdy dane wejściowe są ograniczone do formuł mających co najwyżej jedno satysfakcjonujące przypisanie. Problem nazywa się również USAT . Algorytm rozwiązywania dla UNAMBIGUOUS-SAT może wykazywać dowolne zachowanie, w tym niekończące się pętle, na formule mającej kilka satysfakcjonujących przypisań. Chociaż ten problem wydaje się prostszy, Valiant i Vazirani pokazali, że jeśli istnieje praktyczny (tj. losowy algorytm wielomianu ) do jego rozwiązania, to wszystkie problemy w NP można rozwiązać równie łatwo.
• MAX-SAT , problem maksymalnej spełnialności , jest uogólnieniem SAT FNP . Pyta o maksymalną liczbę klauzul, które może spełnić dowolne przypisanie. Ma wydajne algorytmy aproksymacyjne , ale jest NP-trudny do dokładnego rozwiązania. Co gorsza, jest to APX -complete, co oznacza, że ​​nie istnieje schemat aproksymacji wielomianowej (PTAS) dla tego problemu, chyba że P=NP.
• WMSAT jest problemem znalezienia przypisania minimalnej wagi, które spełnia jednostajną formułę Boole'a (tj. formułę bez żadnej negacji). Wagi zmiennych zdaniowych są podane na wejściu problemu. Waga przypisania to suma wag prawdziwych zmiennych. Ten problem jest NP-zupełny (patrz Th. 1 z ).

Inne uogólnienia obejmują spełnialność dla logiki pierwszego i drugiego rzędu , problemy spełnienia ograniczeń , programowanie liczb całkowitych 0-1 .

Samoredukcja

Problem SAT jest samoredukowalny , co oznacza, że ​​każdy algorytm, który poprawnie odpowiada, jeśli instancja SAT jest rozwiązywalna, może zostać użyty do znalezienia satysfakcjonującego przypisania. Najpierw zadawane jest pytanie o daną formułę Φ. Jeśli odpowiedź brzmi „nie”, formuła jest niezadowalająca. W przeciwnym razie pytanie jest zadawane na podstawie częściowo skonkretyzowanej formuły Φ { x ₁ = PRAWDA} , tj. Φ z pierwszą zmienną x ₁ zastąpioną przez PRAWDA i odpowiednio uproszczoną. Jeśli odpowiedź brzmi "tak", to x ₁ =PRAWDA, w przeciwnym razie x ₁ =FAŁSZ. Wartości innych zmiennych można następnie znaleźć w ten sam sposób. W sumie wymagane jest n +1 przebiegów algorytmu, gdzie n jest liczbą różnych zmiennych w Φ.

Ta właściwość samoredukowalności jest wykorzystywana w kilku twierdzeniach teorii złożoności:

NP ⊆ P/poli ⇒ PH = Σ ₂   ( twierdzenie Karpa–Liptona )

NP ⊆ BPP ⇒ NP = RP

P = NP ⇒ FP = FNP

Algorytmy rozwiązywania SAT

Ponieważ problem SAT jest NP-zupełny, znane są tylko algorytmy o wykładniczej złożoności najgorszego przypadku. Mimo to wydajne i skalowalne algorytmy SAT zostały opracowane w 2000 roku i przyczyniły się do dramatycznego postępu w naszej zdolności do automatycznego rozwiązywania problemów obejmujących dziesiątki tysięcy zmiennych i miliony ograniczeń (tj. klauzul). Przykłady takich problemów automatyzacji projektowania elektronicznego (EDA) obejmują formalne sprawdzanie równoważności , modelu kontroli , weryfikacji formalnej z potokowym mikroprocesorów , automatycznego generowania wzór testu , routingu z FPGA , planowania i problemów szeregowania zadań , i tak dalej. Silnik rozwiązywania SAT jest obecnie uważany za niezbędny element zestawu narzędzi EDA .

Solver DPLL SAT wykorzystuje systematyczną procedurę wyszukiwania z wycofywaniem, aby zbadać (o wielkości wykładniczej) przestrzeń przypisań zmiennych w poszukiwaniu satysfakcjonujących przypisań. Podstawowa procedura wyszukiwania została zaproponowana w dwóch przełomowych artykułach na początku lat sześćdziesiątych (patrz odnośniki poniżej) i jest obecnie powszechnie określana jako algorytm Davisa-Putnama-Logemanna-Lovelanda ("DPLL" lub "DLL"). Wiele nowoczesnych podejść do praktycznego rozwiązywania SAT wywodzi się z algorytmu DPLL i ma tę samą strukturę. Często poprawiają one tylko wydajność niektórych klas problemów SAT, takich jak instancje pojawiające się w aplikacjach przemysłowych lub instancje generowane losowo. Teoretycznie dolne granice wykładnicze zostały udowodnione dla rodziny algorytmów DPLL.

Algorytmy, które nie są częścią rodziny DPLL, obejmują stochastyczne algorytmy wyszukiwania lokalnego . Jednym z przykładów jest WalkSAT . Metody stochastyczne próbują znaleźć satysfakcjonującą interpretację, ale nie mogą wywnioskować, że instancja SAT jest niezadowalająca, w przeciwieństwie do kompletnych algorytmów, takich jak DPLL.

W przeciwieństwie do tego algorytmy randomizowane, takie jak algorytm PPSZ autorstwa Paturi, Pudlak, Saks i Zane, ustawiają zmienne w kolejności losowej zgodnie z niektórymi heurystykami, na przykład rozdzielczością o ograniczonej szerokości . Jeśli heurystyka nie może znaleźć właściwego ustawienia, zmienna jest przypisywana losowo. Algorytm PPSZ ma czas działania 3 SAT. To było najbardziej znane środowisko wykonawcze tego problemu, aż do niedawnej poprawy autorstwa Hansena, Kaplana, Zamira i Zwicka, która ma czas wykonywania dla 3-SAT i obecnie najbardziej znany czas wykonywania dla k-SAT, dla wszystkich wartości k. W środowisku z wieloma zadowalającymi zadaniami algorytm randomizowany Schöninga ma lepsze ograniczenie. ${\ Displaystyle O (1,308 ^ {n})}$${\ Displaystyle O (1,307 ^ {n})}$

Współczesne solwery SAT (opracowane w latach 2000) występują w dwóch wersjach: „oparte na konflikcie” i „spojrzenie w przyszłość”. Oba podejścia wywodzą się od DPLL. Rozwiązania oparte na konfliktach , takie jak uczenie klauzul opartych na konfliktach (CDCL), rozszerzają podstawowy algorytm wyszukiwania DPLL o wydajną analizę konfliktów, uczenie się klauzul, niechronologiczne śledzenie wstecz (inaczej backjumping ), a także jednostkę „dwóch obserwowanych literałów” propagacja , adaptacyjne rozgałęzienie i losowe restarty. Te "dodatki" do podstawowego systematycznego wyszukiwania okazały się empirycznie niezbędne do obsługi dużych instancji SAT, które pojawiają się w automatyzacji projektowania elektronicznego (EDA). Dobrze znane implementacje to Chaff i GRASP . Solwery antycypacyjne mają szczególnie wzmocnione redukcje (wykraczające poza propagację klauzul jednostkowych) i heurystykę, i generalnie są silniejsze niż solvery oparte na konfliktach na twardych instancjach (podczas gdy solvery oparte na konfliktach mogą być znacznie lepsze na dużych instancjach, które faktycznie mają łatwa instancja w środku).

Współczesne solvery SAT mają również istotny wpływ m.in. na weryfikację oprogramowania, rozwiązywanie ograniczeń w sztucznej inteligencji oraz badania operacyjne. Zaawansowane solwery są łatwo dostępne jako darmowe oprogramowanie o otwartym kodzie źródłowym . W szczególności oparty na konfliktach MiniSAT , który odniósł stosunkowo duży sukces w konkursie SAT 2005 , ma tylko około 600 linii kodu. Nowoczesnym solverem Parallel SAT jest ManySAT. Może osiągnąć superliniowe przyspieszenie w ważnych klasach problemów. Przykładem solwerów z wyprzedzeniem jest march_dl , który zdobył nagrodę w konkursie SAT 2007 .

Niektóre typy dużych losowych satysfakcjonujących przypadków SAT można rozwiązać przez propagację ankiety (SP). Szczególnie w aplikacjach do projektowania i weryfikacji sprzętu , spełnialność i inne właściwości logiczne danej formuły zdań są czasami określane na podstawie reprezentacji formuły jako binarnego diagramu decyzyjnego (BDD).

Prawie wszystkie solvery SAT zawierają limity czasu, więc kończą się w rozsądnym czasie, nawet jeśli nie mogą znaleźć rozwiązania. Różne osoby rozwiązujące SAT znajdą różne instancje jako łatwe lub trudne, a niektóre doskonale sprawdzają się w udowadnianiu niezadowalania, a inne w znajdowaniu rozwiązań. Wszystkie te zachowania można zobaczyć w konkursach rozwiązywania SAT.

Równoległe rozwiązywanie SAT

Solvery Parallel SAT dzielą się na trzy kategorie: algorytmy portfolio, dziel i zwyciężaj oraz równoległe algorytmy wyszukiwania lokalnego . W przypadku portfeli równoległych wiele różnych solwerów SAT działa jednocześnie. Każdy z nich rozwiązuje kopię instancji SAT, podczas gdy algorytmy dziel i zwyciężaj dzielą problem między procesory. Istnieją różne podejścia do zrównoleglania lokalnych algorytmów wyszukiwania.

Międzynarodowy SAT Solver Konkurencja ma równoległą ścieżkę odzwierciedlające najnowsze postępy w równoległym rozwiązywaniem SAT. W latach 2016, 2017 i 2018 testy porównawcze zostały przeprowadzone na systemie z pamięcią współdzieloną z 24 rdzeniami przetwarzającymi , w związku z czym solvery przeznaczone dla pamięci rozproszonej lub procesorów wielordzeniowych mogły się nie sprawdzić.

Portfele

Ogólnie rzecz biorąc, nie ma solvera SAT, który działa lepiej niż wszystkie inne solvery we wszystkich problemach SAT. Algorytm może działać dobrze w przypadku problemów, z którymi inni się borykają, ale będzie gorzej radzić sobie w innych przypadkach. Co więcej, biorąc pod uwagę instancję SAT, nie ma niezawodnego sposobu przewidzenia, który algorytm rozwiąże tę instancję szczególnie szybko. Te ograniczenia motywują podejście portfela równoległego. Portfel to zestaw różnych algorytmów lub różnych konfiguracji tego samego algorytmu. Wszystkie solvery w portfelu równoległym działają na różnych procesorach, aby rozwiązać ten sam problem. Jeśli jeden solwer zakończy działanie, solwer portfela zgłasza problem jako satysfakcjonujący lub niesatysfakcjonujący zgodnie z tym jednym solwerem. Wszystkie inne solvery są zakończone. Dywersyfikacja portfeli poprzez uwzględnienie różnych solverów, z których każdy dobrze radzi sobie z innym zestawem problemów, zwiększa niezawodność solvera.

Wiele solwerów używa wewnętrznie generatora liczb losowych . Dywersyfikacja ich nasion to prosty sposób na dywersyfikację portfela. Inne strategie dywersyfikacji obejmują włączanie, wyłączanie lub różnicowanie pewnych heurystyk w solwerze sekwencyjnym.

Jedną z wad portfeli równoległych jest ilość duplikatów pracy. Jeśli uczenie się klauzul jest używane w solwerach sekwencyjnych, udostępnianie wyuczonych klauzul między solwerami działającymi równolegle może zmniejszyć ilość powielanej pracy i zwiększyć wydajność. Jednak nawet samo uruchomienie portfela najlepszych solwerów równolegle tworzy konkurencyjny solwer równoległy. Przykładem takiego solvera jest PPfolio. Został zaprojektowany, aby znaleźć dolną granicę wydajności, jaką powinien być w stanie zapewnić równoległy solver SAT. Pomimo dużej ilości duplikatów pracy ze względu na brak optymalizacji, działał dobrze na maszynie z pamięcią współdzieloną. HordeSat to równoległy solwer portfela dla dużych klastrów węzłów obliczeniowych. W swoim rdzeniu wykorzystuje różnie skonfigurowane instancje tego samego solwera sekwencyjnego. Szczególnie w przypadku twardych instancji SAT, HordeSat może generować liniowe przyspieszenia, a tym samym znacznie skrócić czas działania.

W ostatnich latach równoległe solwery SAT zdominowały równoległy tor Międzynarodowych Konkursów SAT Solver . Godne uwagi przykłady takich solwerów obejmują Plingeling i bezbolesne mcomsps.

Dziel i rządź

W przeciwieństwie do portfeli równoległych, równoległy podział i zwyciężanie próbuje podzielić przestrzeń wyszukiwania między elementy przetwarzania. Algorytmy typu dziel i zwyciężaj, takie jak sekwencyjny DPLL, już wykorzystują technikę dzielenia przestrzeni poszukiwań, stąd ich rozszerzenie w kierunku algorytmu równoległego jest proste. Jednak ze względu na techniki, takie jak propagacja jednostkowa, po podziale, problemy cząstkowe mogą znacznie różnić się złożonością. Tak więc algorytm DPLL zazwyczaj nie przetwarza każdej części przestrzeni poszukiwań w tym samym czasie, co stwarza trudny problem równoważenia obciążenia .

Faza kostki dla formuły . Heurystyka decyzyjna wybiera zmienne (okręgi) do przypisania. Po tym, jak heurystyka odcięcia zdecyduje o zaprzestaniu dalszego rozgałęzienia, problemy częściowe (prostokąty) są rozwiązywane niezależnie przy użyciu CDCL.${\ Displaystyle F}$

Z powodu niechronologicznego cofania się, zrównoleglanie uczenia się klauzuli opartego na konfliktach jest trudniejsze. Jednym ze sposobów przezwyciężenia tego jest paradygmat sześcianu i zwyciężania . Sugeruje rozwiązywanie w dwóch fazach. W fazie „kostki” Problem jest podzielony na wiele tysięcy, a nawet miliony części. Odbywa się to za pomocą solwera z wyprzedzeniem, który znajduje zestaw konfiguracji częściowych zwanych „kostkami”. Kostka może być również postrzegana jako połączenie podzbioru zmiennych oryginalnej formuły. W połączeniu z formułą każda z kostek tworzy nową formułę. Te formuły mogą być rozwiązywane niezależnie i jednocześnie przez solvery oparte na konfliktach. Ponieważ alternatywa tych formuł jest równoważna z formułą pierwotną, problem jest zgłaszany jako satysfakcjonujący, jeśli jedna z formuł jest satysfakcjonująca. Solver z wyprzedzeniem jest korzystny dla małych, ale trudnych problemów, dlatego jest używany do stopniowego podziału problemu na wiele podproblemów. Te podproblemy są łatwiejsze, ale wciąż duże, co jest idealną formą dla rozwiązywania opartego na konfliktach. Ponadto osoby rozwiązujące z wyprzedzeniem uwzględniają cały problem, podczas gdy osoby rozwiązujące oparte na konfliktach podejmują decyzje w oparciu o informacje, które są znacznie bardziej lokalne. Faza kostki obejmuje trzy heurystyki. Zmienne w kostkach są wybierane przez heurystykę decyzyjną. Heurystyka kierunku decyduje, które przypisanie zmiennej (prawda lub fałsz) należy zbadać jako pierwsze. W satysfakcjonujących przypadkach problemowych, korzystne jest wybranie najpierw spełniającej wymagania gałęzi. Heurystyka odcięcia decyduje, kiedy przestać rozszerzać kostkę i zamiast tego przekazać ją do sekwencyjnego rozwiązywania opartego na konfliktach. Korzystnie kostki są podobnie złożone do rozwiązania.

Treengeling jest przykładem równoległego solwera, który stosuje paradygmat Cube-and-Conquer. Od momentu wprowadzenia w 2012 roku odniosła wiele sukcesów na Międzynarodowym Konkursie Solverów SAT . Cube-and-Conquer został użyty do rozwiązania problemu trójek Boole'a Pitagorasa .

Wyszukiwanie lokalne

Jedną ze strategii w kierunku równoległego lokalnego algorytmu wyszukiwania do rozwiązywania SAT jest próbowanie wielu zmiennych przerzutów jednocześnie na różnych jednostkach przetwarzania. Innym jest zastosowanie wyżej wspomnianego podejścia portfelowego, jednak współdzielenie klauzul nie jest możliwe, ponieważ lokalne rozwiązania wyszukiwania nie tworzą klauzul. Alternatywnie możliwe jest współdzielenie konfiguracji, które są produkowane lokalnie. Te konfiguracje mogą służyć do kierowania tworzeniem nowej konfiguracji początkowej, gdy lokalny solwer zdecyduje się na ponowne uruchomienie wyszukiwania.

Zobacz też

• Niezadowalający rdzeń
• Teorie modulo spełnialności
• Liczenie SAT
• Planarne SAT
• Algorytm Karloffa-Zwicka
• Zgodność obwodu

Uwagi

Bibliografia

Referencje są uporządkowane według daty publikacji:

Zewnętrzne linki

• SAT Game - spróbuj samodzielnie rozwiązać problem satisfiability Boole'a

Format problemu SAT

Problem SAT jest często opisywany w formacie DIMACS-CNF : plik wejściowy, w którym każda linia reprezentuje pojedynczą alternatywę. Na przykład plik z dwoma wierszami

1 -5 4 0
-1 5 3 4 0

reprezentuje formułę „( x ₁ ∨ ¬ x ₅ ∨ x ₄ ) ∧ (¬ x ₁ ∨ x ₅ ∨ x ₃ ∨ x ₄ )”.

Innym popularnym formatem tej formuły jest 7-bitowa reprezentacja ASCII „(x1 | ~x5 | x4) & (~x1 | x5 | x3 | x4)”.

• BCSAT to narzędzie, które konwertuje pliki wejściowe w formacie czytelnym dla człowieka na format DIMACS-CNF.

Solvery SAT online

• BoolSAT – Rozwiązuje formuły w formacie DIMACS-CNF lub w bardziej przyjaznym dla człowieka formacie: „a and not b or a”. Działa na serwerze.
• Logictools – zapewnia różne solvery w javascript do nauki, porównywania i hakowania. Działa w przeglądarce.
• minisat-in-your-browser – Rozwiązuje formuły w formacie DIMACS-CNF. Działa w przeglądarce.
• SATRennesPA – Rozwiązuje formuły napisane w sposób przyjazny dla użytkownika. Działa na serwerze.
• somerby.net/mack/logic – Rozwiązuje formuły napisane w logice symbolicznej. Działa w przeglądarce.

Solvery SAT offline

• MiniSAT — format DIMACS-CNF i format OPB dla towarzyszącego mu Pseudo-Boolean narzędzia do rozwiązywania ograniczeń MiniSat+
• Lingeling – zdobył złoty medal w konkursie SAT 2011.
  • PicoSAT – wcześniejszy solver z grupy Lingeling.
• Sat4j – format DIMACS-CNF. Dostępny kod źródłowy Java.
• Glukoza – format DIMACS-CNF.
• RSat – zdobył złoty medal w zawodach SAT 2007.
• UBCSAT . Obsługuje klauzule nieważone i ważone, zarówno w formacie DIMACS-CNF. Kod źródłowy C hostowany na GitHub .
• CryptoMiniSat – zdobył złoty medal w konkursie SAT 2011. Kod źródłowy C++ hostowany na GitHub . Próbuje umieścić wiele przydatnych funkcji rdzenia MiniSat 2.0, PrecoSat ver 236 i Glucose w jednym pakiecie, dodając wiele nowych funkcji
• Włócznia — obsługuje arytmetykę wektorów bitowych. Może używać formatu DIMACS-CNF lub formatu Spear .
  • HyperSAT – Napisany w celu eksperymentowania z przycinaniem przestrzeni wyszukiwania z kostkami B. Zdobył 3 miejsce w konkursie SAT 2005. Wcześniejszy i wolniejszy solver od twórców Spear.
• BASolver
• ArgoSAT
• Fast SAT Solver – oparty na algorytmach genetycznych .
• zChaff – nie jest już obsługiwany.
• BCSAT – czytelny dla człowieka format obwodu logicznego (konwertuje również ten format na format DIMACS-CNF i automatycznie łączy się z MiniSAT lub zChaff).
• gini – solver języka Go SAT z powiązanymi narzędziami.
• gophersat – solwer SAT w języku Go, który radzi sobie również z problemami pseudo-boolean i MAXSAT.
• CLP(B) – Programowanie logiki z ograniczeniami boolowskimi, np. SWI-Prolog .

Aplikacje SAT

• WinSAT v2.04 : aplikacja SAT oparta na systemie Windows, stworzona specjalnie dla naukowców.

Konferencje

• Międzynarodowa konferencja nt. teorii i zastosowań badania spełnialności

Publikacje

• Czasopismo o spełnialności, modelowaniu boolowskim i obliczeniach
• Propagacja ankiet

Benchmarki

• Wymuszone satysfakcjonujące testy SAT
• Testy porównawcze weryfikacji oprogramowania
• Fadi Aloul SAT Benchmarki

Ogólne rozwiązywanie SAT:

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

Ocena solwerów SAT

• Roczna ocena solwerów SAT
• Wyniki oceny solwerów SAT za rok 2008
• Międzynarodowe Zawody SAT
• Historia

Więcej informacji o SAT:

• SAT i MAX-SAT dla laika
• SAT/SMT według przykładu

Ten artykuł zawiera materiał z kolumny biuletynu elektronicznego ACM SIGDA autorstwa prof. Karema Sakallaha
Tekst oryginalny jest dostępny tutaj