Problem spełnialności obwodu - Circuit satisfiability problem

Obwód po lewej stronie jest zadowalający, ale obwód po prawej nie.

W teoretycznej informatyki The Problem spełnialności obwód (znany również jako obwód-SAT , CircuitSAT , CSAT itp) to problem decyzyjny ustalania, czy dany obwód logiczny ma przypisanie jej wejść sprawia, że wyjście prawda. Innymi słowy, pyta, czy dane wejściowe danego obwodu logicznego mogą być konsekwentnie ustawione na 1 lub 0 tak, że obwód wyjściowy 1 . Jeśli tak jest, obwód nazywa się satisfiable . W przeciwnym razie obwód nazywany jest niezadowalającym. Na rysunku po prawej stronie lewy obwód można zaspokoić ustawiając oba wejścia na 1 , ale prawy obwód jest niezadowalający.

CircuitSAT jest ściśle związany z problemem spełnialności logicznej (SAT) i podobnie okazał się NP-zupełny . Jest to problem prototypowy NP-zupełny; Twierdzenie Cooka-Levina jest czasem okazało na CircuitSAT zamiast na SAT, a następnie zmniejsza się do innych problemów spełnialności udowodnić swoją Problem NP-zupełny. O spełnialności obwodu zawierającego arbitralne bramki binarne można decydować w czasie . ${\ Displaystyle m}$${\ Displaystyle O (2 ^ {0,4058 m})}$

Dowód NP-kompletności

Mając obwód i zadowalający zestaw wejść, można obliczyć wyjście każdej bramki w stałym czasie. Stąd wyjście obwodu jest weryfikowalne w czasie wielomianowym. Zatem Circuit SAT należy do klasy złożoności NP. Aby pokazać twardość NP , można skonstruować redukcję z 3SAT do Circuit SAT.

Załóżmy, że oryginalna formuła 3SAT zawiera zmienne i operatory (AND, OR, NOT) . Zaprojektuj obwód tak, aby posiadał wejście odpowiadające każdej zmiennej i bramkę odpowiadającą każdemu operatorowi. Połącz bramki zgodnie ze wzorem 3SAT. Na przykład, jeśli formuła 3SAT jest taka, że ​​obwód będzie miał 3 wejścia, jedno AND, jedno OR i jedną bramkę NOT. Wejście odpowiadające zostanie odwrócone przed wysłaniem do bramki AND z, a wyjście bramki AND zostanie wysłane do bramki OR z${\displaystyle x_{1},x_{2},\kropki,x_{n}}$${\ Displaystyle y_ {1}, y_ {2}, \ kropki , y_ {k}}$${\displaystyle (\nie x_{1}\land x_{2})\lub x_{3}}$${\displaystyle x_{1}}$${\displaystyle x_{2},}$${\displaystyle x_{3}.}$

Zauważ, że formuła 3SAT jest równoważna z obwodem zaprojektowanym powyżej, stąd ich wyjście jest takie samo dla tego samego wejścia. W związku z tym, jeśli formuła 3SAT ma satysfakcjonujące przypisanie, odpowiedni obwód wyprowadzi 1 i na odwrót. Jest to więc poprawna redukcja, a Circuit SAT jest NP-trudny.

To kończy dowód, że Circuit SAT jest NP-Complete.

Ograniczone warianty i powiązane problemy

Obwód planarny SAT

Załóżmy, że otrzymujemy planarny obwód logiczny (tj. obwód logiczny, którego bazowy wykres jest planarny ) zawierający tylko bramki NAND z dokładnie dwoma wejściami. Planar Circuit SAT to problem decyzyjny określający, czy ten obwód ma przypisanie swoich wejść, które sprawia, że ​​wyjście jest prawdziwe. Ten problem jest NP-zupełny. W rzeczywistości, jeśli ograniczenia zostaną zmienione tak, że jakakolwiek bramka w obwodzie jest bramką NOR , powstały problem pozostaje NP-zupełny.

Obwód UNSAT

Układ UNSAT to problem decyzyjny polegający na ustaleniu, czy dany obwód logiczny generuje fałsz dla wszystkich możliwych przypisań jego wejść. Jest to uzupełnienie problemu Circuit SAT, a zatem jest Co-NP-zupełne .

Redukcja z CircuitSAT

Redukcja z CircuitSAT lub jej wariantów może być wykorzystana do wykazania NP-twardości pewnych problemów i zapewnia nam alternatywę dla redukcji dwutorowych i logicznych binarnych. Gadżety, które taka redukcja musi zbudować to:

• Gadżet z drutu. Ten gadżet symuluje przewody w obwodzie.
• Podzielony gadżet. Ten gadżet gwarantuje, że wszystkie przewody wyjściowe mają taką samą wartość jak przewód wejściowy.
• Gadżety symulujące bramki obwodu.
• Gadżet z prawdziwym terminatorem. Ten gadżet służy do wymuszenia na wyjściu całego obwodu True.
• Gadżet skrętu. Ten gadżet pozwala nam w razie potrzeby przekierować przewody we właściwym kierunku.
• Gadżet crossovera. Ten gadżet pozwala nam na skrzyżowanie dwóch przewodów bez interakcji.

Problem wnioskowania Sapera

Ten problem pyta, czy możliwe jest zlokalizowanie wszystkich bomb na planszy Sapera . Udowodniono, że jest to CoNP-Complete dzięki redukcji problemu z Circuit UNSAT. Gadżety skonstruowane dla tej redukcji to: drut, split, bramki AND i NOT oraz terminator. Istnieją trzy kluczowe spostrzeżenia dotyczące tych gadżetów. Po pierwsze, podzielony gadżet może być również używany jako gadżet NIE i gadżet do obracania. Po drugie, wystarczy skonstruowanie gadżetów AND i NOT, ponieważ razem mogą symulować uniwersalną bramkę NAND. Wreszcie, ponieważ możemy symulować XOR za pomocą trzech NAND, a XOR jest wystarczający do zbudowania zwrotnicy, daje nam to potrzebny gadżet zwrotnicy.

Transformacja Tseytina

Transformacja Tseytin jest prosta redukcja z obwodu-SAT do SAT . Transformacja jest łatwa do opisania, jeśli obwód jest w całości zbudowany z 2-wejściowych bramek NAND ( funkcjonalnie kompletny zbiór operatorów logicznych): przypisz każdej sieci w obwodzie zmienną, a następnie dla każdej bramki NAND skonstruuj spójną postać normalną klauzule ( v ₁ ∨ v ₃ ) ∧ ( v ₂ ∨ v ₃ ) ∧ (¬ v ₁ ∨ ¬ v ₂ ∨ ¬ v ₃ ), gdzie v ₁ i v ₂ to wejścia bramki NAND, a v ₃ to wyjście . Klauzule te całkowicie opisują związek między trzema zmiennymi. Połączenie klauzul ze wszystkich bramek z dodatkową klauzulą ​​ograniczającą zmienną wyjściową obwodu jako prawdziwą kończy redukcję; przypisanie zmiennych spełniających wszystkie ograniczenia istnieje wtedy i tylko wtedy, gdy pierwotny obwód jest satysfakcjonujący, a każde rozwiązanie jest rozwiązaniem pierwotnego problemu znalezienia danych wejściowych, które tworzą wyjście obwodu 1. Odwrotność — SAT można zredukować do obwodu -SAT — następuje trywialnie, przepisując formułę Boole'a na obwód i rozwiązując go.

Zobacz też

• Problem z wartością obwodu
• Spełnialność obwodów strukturalnych
• Problem z satysfakcją

Bibliografia