3.2. Lipton kísérlete

Adleman kísérlete után Lipton 1995-ben publikálta a SAT megoldására szolgáló kísérletét. A SAT probléma is NP-teljes, sőt a leggyakrabban vizsgált, a legnépszerűbb NP-teljes probléma.

3.2.1. A SAT probléma

A SAT probléma alapvető szerepet játszik a bonyolultságelméletben, ugyanis ez az egyik legismertebb NP-teljes probléma.

A feladat maga röviden a következő: adott egy propozicionális (vagy más néven ítélet-, vagy Boole-) logikai formula, döntsük el, hogy kielégíthető-e, vagyis lehet-e a propozicionális változóknak (ítéletváltozók, Boole-változók) értéket adni úgy, hogy a formula igaz legyen.

A feladatnak többféle speciális megfogalmazása is létezik, és használt mind az elméletben, mind a gyakorlatban. Az első speciális alak, amikor a formula konjunktív normál formában adott. Az ítéletváltozókat, illetve negáltjaikat (pozitív, illetve negatív) literáloknak hívjuk. Literálok diszjunkcióját elemi diszjunkciónak (vagy klóznak) nevezzük. Elemi diszjunkciók konjunkciója adja a konjunktív normálformájú formulát. Közismert tény, hogy minden propozicionális logikai formulához van vele ekvivalens konjunktív normálformájú formula. A feladat maga így is NP-teljes. A következő, még speciálisabb alak, amikor a konjunktív normál forma mellett az is adott, hogy az egyes elemi diszjunkciók hány literált tartalmaz(hat)nak. A feladat ilyen megszorítással történő megfogalmazását nevezik n-SAT problémának. Az n-SAT n ≥ 3 esetén NP-teljes, míg a 2-SAT probléma P-beli.

A tömör bizonyíték ez esetben egy kielégítő kiértékelés, amely megadja mely Boole-változó értéke legyen igaz és melyek legyenek hamisak.

Itt említjük meg, hogy diszjunktív normál formájú formulák esetén a SAT probléma megoldása triviális. Literálok konjunkcióját elemi konjunkciónak hívjuk. Elemi konjunkciók diszjunkciója adja a diszjunktív normál formát. Minden ítéletlogikai formulával van ekvivalens diszjunktív normálformájú formula is. A kiértékelő algoritmus egyszerű: tekintsük az első elemi konjunkciót: legyenek a benne szereplő pozitív literálok igazak, a negatív literálok változói pedig hamisak. Mivel a formula többi része diszjunkcióval kapcsolódik, nem érdekes az igazságértéke, a diszjunkció egyik tagjának igazsága az egész formulát igazzá teszi. Egyetlen egy esetben nem sikeres az értékadás: ha az elemi konjunkcióban van olyan ítéletváltozó, ami pozitív és negatív literálként is szerepel. Ekkor az adott elemi konjunkció nem kielégíthető, az algoritmusnak a következőt is ellenőriznie kell. Ha találunk kielégíthető elemi konjunkciót (az előbbi módon igazságértékeket rendelhetünk a Boole változókhoz), a formula kielégíthető. Ha egyik elemi konjunkció sem kielégíthető, akkor a formula sem. Ez tehát egy lineáris (sőt valós-idejű, real-time, ami ráadásul sokszor már az input véges előtt megadja a pozitív választ) algoritmus, vagyis a leghatékonyabb algoritmusok egyike. Hol van akkor a bökkenő, hogy lehet mégis nehéz a SAT? Hiszen köztudottan konjunktív normálformájú formulát egyszerűen átkonvertálhatunk diszjunktív normálformájúvá a disztributív azonosságok segítségével. Gondoljunk csak bele, hogyan változik a formula hossza ezzel a transzformációval... A diszjunktív normálformájú formulákra annak eldöntése nehéz, hogy a formula logikai törvény-e (vagyis, hogy minden lehetséges kiértékelés esetén igaz lesz-e). Ez a kérdés a konjunktív normálformájú formulák esetén oldható meg egyszerűen.

3.2.2. A SAT megoldása DNS molekulákkal

Most nézzük a SAT megoldását DNS-ek segítségével.

Legyen adott az alábbi formula (konjunktív normál formában):

A megoldás során először tekintsük a 3.3. ábrán látható gráfot. Minden ebben a gráfban levő maximális hosszúságú út (ezek az s kezdőponttól a t végpontig vezetnek) minden egyes változóra pontosan vagy a változót, vagy a negáltját tartalmazza.

3.3. ábra - A három változóval rendelkező formulákhoz használható kiindulási gráf SAT problémához.

A három változóval rendelkező formulákhoz használható kiindulási gráf SAT problémához.

Nézzük, hogyan használhatjuk a DNS molekulákat: A változóknak és a negáltjaiknak (mint a gráf csúcsainak) egyszálú DNS láncokat feleltetünk meg, hasonlóan ahhoz, mint ahogy a Hamilton-út problémánál tettük az előző alfejezetben. Ebből, ahogy Adleman kísérletében is láttuk, létrehozhatunk egy olyan oldatot, amiben a gráfban található utak vannak kódolva.

A 3.3. ábrán látható gráfban az összes maximális hosszúságú út (a gráf speciális szerkezet miatt azt is mondhatjuk, hogy az összes s-ből induló és t-be vezető út) egy-egy kiértékelésnek felel meg. Ha egy változónak a pozitív literáljának megfelelő csúcsot tartalmazza, akkor az adott változó értékét igaznak (1) tekintjük ebben a kiértékelésben, ellenkező esetben padig, ha a negatív literálnak megfelelő csúcs szerepel, akkor az adott változót hamisnak (0) tekintjük e kiértékelésben.

9. Példa. Például egy ilyen maximális út ami az a igaz, a b és c változók hamis értékét kódolja.

Mivel az s és a t minden úton szereplenek, valójában őket nem tekintjük a kód részének (a 3.3. ábrán kékkel jelzett csúcsok és élek, csak technikai jellegű szerepet játszanak, ők adják pl. az ismert láncvégeket, ami pl. sokszorosítás esetén kell. Ennek megfelelően elméleti modellekben nem is mindig tekintjük őket a kód részének. Tehát a 9. példában megadott utat írhatjuk az rövidebb formába, illetve az általa reprezentált kiértékelést az abc változósorrendet rögzítve 100 alakba.

Az eredeti, tetszőleges utakat tartalmazó oldatból pl. hosszmérés alapján kiválaszthatjuk a maximális hosszúakat (n változós formulához készített gráf esetén n+2 csúcs hosszúak, a +2 a gráf két végpontja, s és t kódja miatt). Alternatívaként a két végpontot jelentő csúcsra s-re, majd t-re pecázva is megkaphatjuk az összes olyan utat tartalmazó oldatot, amik a lehetséges kiértékeléseket kódolják. A lehetséges kiértékelések száma 2n, esetünkben 8.

Ez a leves lesz a kiindulási halmazunk.

12. Feladat. Sorolja fel a kiindulási halmazban szereplő utakat, és adja meg az általuk reprezentált kiértékeléseket.

Vegyük észre, hogy szemben Adleman kísérletével, ahol az input gráf kódja volt a levesben, itt az input formulát még nem használtuk fel. Ennek megfelelően a kiindulási halmaz másolata (megfelelő sokszorosító műveleteket elvégezve, és szétöntve az oldatot) eltehető más ugyanennyi változós formula vizsgálatához.

Folytassuk, most Lipton kísérletének bemutatását, az input formulának megfelelő műveletek végrehajtásával.

Tekintsük tehát sorban a formula klózjait, és keressük azokat az értékeléseket, amelyekre minden klózban van igaz literál. Ezt a DNS-ekkel a következőképpen tehetjük meg.

Eredetileg tehát mindenféle értékelésünk ott van a levesben. Ezután sorra vesszük a klózokat, és minden egyes klózra a következő lépéseket végezzük el. Először is annyi másolatot készítünk a lombikból (a benne levő DNS szálakról) amennyi literál alkotja az adott klózt. Vagyis a sokszorosítás műveletét is felhasználva szétosztjuk a lombik tartalmát ennyi részre. Minden ilyen lombikhoz hozzárendeljük az adott klóz egy literálját. Ezután, mindegyik lombikban a hozzárendelt literáloknak megfelelő komplementerek molekulákkal pecázunk, mindegyik levesből kiválasztjuk azokat a láncokat amikben az adott literál igaz (vagyis a kód tartalmazza részszóként az adott literál kódját). Ezután összeöntve a lombikok tartalmát pontosan azok a molekulák lesznek ebben, amelyekben az adott klóz igaz. Tekintsük az így létrejött levest a további vizsgálat alapjául.

Az eljárást megismételve a több klózra is, mindig kiesnek azok a molekulák, így azok a kiértékelések, amik az adott klózt nem elégítik ki. Végül, az utolsó klózra is elvégezve a lépéseket, csak azok a láncok maradnak az oldatban, amelyek kielégítik az egész formulát. Már csak azt kell ellenőriznünk, hogy maradt-e DNS láncunk az oldatban.

A megadott példa esetén az algoritmust a 3.4. ábra mutatja.

3.4. ábra - A példában megadott klózok literáljai szerint szűrünk.

A példában megadott klózok literáljai szerint szűrünk.

10. Példa. A formula esetén az első klóznál történő szűrés a következőképpen megy végbe:

Először mindhárom lombikban megtalálható, mind a 8 lehetséges kiértékelés:

Lombik 'a' Lombik Lombik
000 000 000
001 001 001
010 010 010
011 011 011
100 100 100
101 101 101
110 110 110
111 111 111

A szűrés műveletének elvégzése után:

Lombik 'a' Lombik Lombik
100 000 000
101 001 010
110 100 100
111 101 110

Az összeöntött lombik tartalma:

000, 001, 010, 100, 101, 110, 111.

(Láthatjuk, hogy a 011 az egyetlen kiértékelés, ami eltávolításra került.)

Folytassuk az algoritmus végrehajtását, kielégítő-e a B formula?

13. Feladat. Szimulálja a Lipton-féle algoritmust az

formulákon. (Használja a leírásban a reprezentált bitsztringeket.)

Melyik formula esetén milyen lépésekből áll az algoritmus?

Melyik lépésben mely molekulák szűrődnek ki, és melyek maradnak benn a rendszerben?

Melyik formula kielégíthető és melyik nem?