Bonyelm gyakjegyzet 2014, 2. gyak

A félév túlnyomó részében egymáshoz fogunk problémákat viszonyítani, és szeretnénk olyat mondani, hogy pl az $A$ probléma "könnyebb", mint a $B$ probléma (vagy legalábbis, "legfeljebb olyan nehéz" - ez megint a $<$ vs. $\leq$ különbségre emlékeztet. Maradunk a "legfeljebb olyan nehéz"-nél, mert sokszor a problémák "egyforma" nehezek lesznek majd.).

Adja magát, hogy pl. akkor mondanánk az $A$-t könnyebbnek, mint a $B$-t, ha az optimális algoritmus $A$-ra gyorsabb, mint $B$-re. Ezzel csak egy a baj: néhány triviális esettől eltekintve nem szoktuk azt tudni, hogy ami algoritmusunk nekünk van, az tényleg az optimális-e vagy sem. Emiatt ez nem egy járható út.

Ami a másik szóbajövő lehetőség: ha $B$-t meg tudnánk oldani, akkor az őt megoldó algoritmus segítségével az $A$-t is. Ezt a megközelítést használja a visszavezethetőség fogalma: azt mondjuk, hogy az $A$ probléma visszavezethető $B$-re, ha van olyan $f$ inputkonverzió (ez lesz maga a visszavezetés), mely

• $A$ inputjaiból $B$ inputjait készíti;
• tartja a választ, azaz $A(x)=B(f(x))$ tetszőleges $x$ inputjára $A$-nak (azaz $A$ "igen" példányaiból $B$ "igen" példányait készíti, "nem" példányokból pedig "nem" példányokat);
• és hatékony, azaz polinomidőben kiszámítható.

A definíció oké abból a szempontból, hogy ha $f$ egy visszavezetés $A$-ból $B$-re és $B$-re van megoldó algoritmusunk, akkor onnan kezdve $A$-ra is van: az input $x$-et át kell konvertálni $f$-fel $B$ egy $f(x)$ inputjára, erre meghívni a $B$-t megoldó algoritmust és a választ visszaadni, az megválaszolja, hogy az $x$ input az $A$ problémának "igen" példánya-e vagy sem.

Például, a SAT probléma a következő: input egy CNF (konjunktív normálforma), output, hogy kielégíthető-e. A FORMSAT pedig ugyanez, csak inputja tetszőleges Boole-formula lehet, nem feltétlen CNF-ben.

Az világos, hogy a SAT legfeljebb olyan nehéz, mint a FORMSAT: ehhez egy visszavezetést kell találjunk SAT-ról FORMSAT-ra. Azaz egy olyan $f$ konverziót, ami

• SAT inputjából (azaz egy CNF-ből) készíti
• FORMSAT egy inputját (azaz egy akármilyen Boole-formulát) úgy, hogy
• ha az input $F$ kielégíthető, akkor a generált $f(F)$ is kielégíthető lesz és csak akkor, továbbá
• $f$ polinomidőben (azaz gyorsan) kiszámítható legyen.

Ebbe az irányba az $f$ lehet az identikus függvény is, azaz nem bántjuk az inputot, csak visszaadjuk, hogy tess, ez a konvertálás eredménye. Jó lesz: egy CNF formula is egyben, a kielégíthetősége nem változik (nyilván), kész. (Ez a módszer mindig alkalmazható, ha az $A$ probléma inputja speciális esete a $B$ problémáénak és a kérdés ugyanaz.)

Visszafelé is igaz, hogy a FORMSAT legfeljebb olyan nehéz, mint a SAT, azaz FORMSAT $\leq$ SAT. Itt vigyázunk kell egy kicsit, it's a trap! Kell adni egy olyan $f$ konverziót, ami

• input tetszőleges formulából készít
• CNF-et úgy, hogy
• ha az input $F$ formula kielégíthető, akkor a generált $f(F)$ CNF is az lesz, és csak akkor, továbbá
• $f$ polinomidőben kiszámítható.

Az első ép ötlet, ami az ember eszébe jut, hogy hát hozzuk CNF-re az input formulát és kész is vagyunk! A szokásos módszer ugye a $\to,\leftrightarrow$ nyilak eliminálása, majd a deMorgan-azonosságok alkalmazása, aztán a disztributivitással megjavítani az $\vee,\wedge$ sorrendjét. Ez persze egy ekvivalens formulát készít, tehát a kielégíthetőséget nem bántja, az output CNF, szóval...

mégis rossz az egész

meeert ez a CNF-re hozó algoritmus bizony nem polinomidejű, sőt.

Több sebből vérzik a dolog, például ha az input formula

$(x_1\wedge y_1)\vee(x_2\wedge y_2)\vee\ldots\vee(x_n\wedge y_n)$

(igen, ez egy DNF), akkor az ezzel ekvivalens CNF, amit disztributivitással kapunk, kb ilyen:

$(x_1\vee x_2\vee\ldots\vee x_n)\wedge(x_1\vee\ldots\vee x_{n-1}\vee y_n)\wedge\ldots\wedge(x_1\vee y_2\vee x_3\vee y_4\vee\ldots\vee x_n)\wedge\ldots\wedge(y_1\vee y_2\vee\ldots y_n)$.

Olyan hosszú, hogy nem fér ki. Ez minimum gyanús. Tehát egy klózban $x_i$-k vannak és $y_i$-k, minden $i$-re pontosan az egyik a kettő közül; ilyen klóz $2^n$-féle van, mindegyik $n$ hosszú, emiatt a teljes generált CNF $n\cdot 2^n$ hosszú lesz. Exponenciális hosszú outputot pedig nem lehet polinomidőben generálni, emiatt

a standard CNF-re hozó algoritmus nem polinomidejű.

sőt.

nincs is polinomidejű CNF-re hozó algoritmus.

Ettől persze még vissza akarjuk vezetni a FORMSAT-ot a SAT-ra, egy afféle apróság, hogy nem lehet tetszőleges formulából ekvivalens CNF-et készíteni polinomidőben, nem szabad, hogy kedvünket szegje. Megnézve a specifikációt, arról egy szó nincs, hogy ekvivalens is legyen a két formula, csak annyi a kérés, hogy kielégíthetőből kielégíthetőt, kielégíthetetlenből pedig kielégíthetetlent készítsünk (ezt hívtuk logikából $s$-ekvivalens formuláknak, $s$ mint satisfiability).

A módszer pedig az lesz, hogy minden egyes $F$ részformulához társítunk egy új $x_F$ változót és annak az értékét egy-egy $\leftrightarrow$ ekvivalenciával kényszerítjük, hogy vegye fel azt az értéket, mint amit az $F$ venne, az eredeti változók tetszőleges kiértékelése mellett. Azaz, a következő rekurzív átírást csináljuk:

$x \mapsto x$, $(F\vee G) \mapsto x_{(F\vee G)}\leftrightarrow(x_F\vee x_G)$, $(F\wedge G)\mapsto x_{(F\wedge G)}\leftrightarrow (x_F\wedge x_G)$, stb. Egy példán keresztül, ha az input formula $y\wedge\neg (z\vee \neg w)$, akkor a $\neg w$ részformula helyett bevezetünk egy $x_{\neg w}$ fedőnevű változót, és azt mondjuk, hogy $x_{\neg w}\leftrightarrow \neg w$, a $(z\vee \neg w)$ részformula helyett bevezetünk egy $x_{z\vee\neg w}$ nevű változót, és azt mondjuk, hogy $x_{z\vee\neg w}\leftrightarrow(z\vee x_{\neg w})$, aztán a $\neg (z\vee\neg w)$ részformula helyett bejön egy $x_{\neg(z\vee\neg w)}$ változó, amiről azt mondjuk, hogy $x_{\neg(z\vee\neg w)}\leftrightarrow(\neg x_{z\vee\neg w})$, és az egész formula helyett bevezetünk egy $x_{y\wedge\neg(z\vee\neg w)}$ (eek) nevű változót, amiről pedig azt mondjuk, hogy $x_{y\wedge\neg(z\vee\neg w)}\leftrightarrow(y\wedge x_{\neg(z\vee\neg w)})$. Ezzel megoldottuk, hogy minden részformulának az értékét "letároljuk" egy változóban, már csak azt kell mondjuk, hogy a formula még ráadásul igaz is, ezt pedig úgy tesszük, hogy hozzáéseljük az $x_{y\wedge\neg(z\vee\neg w)}$ változót is a fenti összes "értékadás" éseléséhez.

Az eredményként kapott formulánk ez lenne:

$(x_{\neg w}\leftrightarrow \neg w)\wedge$

$(x_{z\vee\neg w}\leftrightarrow(z\vee x_{\neg w}))\wedge$

$(x_{\neg(z\vee\neg w)}\leftrightarrow(\neg x_{z\vee\neg w}))\wedge$

$(x_{y\wedge\neg(z\vee\neg w)}\leftrightarrow(y\wedge x_{\neg(z\vee\neg w)}))\wedge$

$x_{y\wedge\neg(z\vee\neg w)}$.

Hiába látszik hosszúnak ez a formula, ez csak azért van, mert a változók neve hosszú, bevezethettem volna $x_0$, $x_1$, stb változókat is $x_{z\vee\neg w}$ stb. nevek helyett.

Egy jogos észrevétel, hogy ez még nem is CNF, de könnyen azzá tehető, ekvivalenciánként, a végeredmény pedig:

$(\neg x_{\neg w}\vee\neg w)\wedge(x_{\neg w}\vee w)\wedge$

$(\neg x_{z\vee\neg w}\vee z\vee x_{\neg w})\wedge(x_{z\vee\neg w}\vee\neg z)\wedge(x_{z\vee\neg w}\vee\neg x_{\neg w})\wedge$

$(\neg x_{\neg(z\vee\neg w)}\vee\neg x_{z\vee\neg w})\wedge(x_{\neg(z\vee\neg w)}\vee x_{z\vee\neg w})\wedge$

$(\neg x_{y\wedge\neg(z\vee\neg w)}\vee y)\wedge (\neg x_{y\wedge\neg(z\vee\neg w)}\vee x_{\neg(z\vee\neg w)})\wedge(x_{y\wedge\neg(z\vee\neg w)}\vee\neg y\vee\neg x_{\neg(z\vee\neg w)})\wedge$

$x_{y\wedge\neg(z\vee\neg w)}$.

Így általánosan formulából tudunk készíteni lineáris időben (egyszer kell csak bepreorderjárni a formulát mint fát) egy max kb. nyolcszor olyan hosszú CNF-et, ami ha nem is ekvivalens, de $s$-ekvivalens az eredetivel.

Amúgy ha pl. ennél a példánál a formulát kielégíti az $y=1, z=0, w=1$ kiértékelés, akkor a plusz változókat a "megfelelő" értékre, tehát $x_{\neg w}=0$, $x_{z\vee\neg w}=0$, $x_{\neg(z\vee\neg w)=1}$ és $x_{y\wedge\neg(z\vee\neg w)}=1$, a fenti CNF is igaz lesz, tessék ellenőrizni.

A tanulság egyelőre annyi, hogy a polinomidő az néha komolyabb kritérium a konvertálás felé, mint első blikkre látszik.

Egy másik példát is néztünk: legyen $ILP$, az Integer Linear Programming a következő probléma: input egy $A\boldsymbol{x}\geq \boldsymbol{b}$ alakú egyenlőtlenség-rendszer, ahol $A$ és $\boldsymbol{b}$ egész számokból álló együtthatómátrix ill. vektor; output: lehet-e úgy egész értékeket rendelni az $\boldsymbol{x}$ változókhoz, hogy teljesüljenek az egyenlőtlenségek? (Van-e egészértékű megoldás?) Mármost ez opkutból ismerős történet, "tudjuk", hogy ha az egészértékű kikötés nem lenne az $\boldsymbol{x}$-re, akkor mondjuk a szimplex módszerrel hipp és hopp ezt megtudnánk (standardizálás, LKAF stb.) Oké, a szimplex módszer nem polinomidejű, de belsőpontossal vagy ellipszoiddal is meg lehet oldani, ami viszont polinomidejű is.

Hanem (ahogy opkutkettőből tudjuk) ebből kerekítéssel nem jön feltétlen össze egészértékű megoldás.. mindenesetre, azt azért megcsináltuk, hogy

$SAT\ \leq\ ILP$,

ez mit jelent? Egy olyan $f$ konverziót kell adnunk, ami

• CNF-ből készít
• egyenlőtlenség-rendszert úgy, hogy
• ha a CNF kielégíthető, akkor az egyenlőtlenség-rendszernek van megoldása, és csak akkor,
• mindezt polinomidőben.

Ilyenkor ki kell találni, hogy az input melyik részeiből az output melyik részei lesznek. Ha például úgy döntünk, hogy

• az input változóiból az outputnak szintén változói lesznek, azaz egy $x$ logikai változóból a SAT-ban készítünk egy $x$ egészértékű változót az ILP-be,
• azt szeretnénk jó informatikushoz méltóan, hogy az ILP-ben úgy jelenjen meg az $x$ értéke, hogy $0$ a hamis, $1$ az igaz,
• akkor fel kell vennünk minden $x$-hez egy $0\leq x\leq 1$ feltételt (hogy megfeleljen a fenti formának, ez két egyenlőtlenség: $x\geq 0$ és $-x\geq -1$), ezzel már el is értük, hogy a változók az ILP-ben binárisak lesznek;
• akkor egy pozitív $x$ literálból simán $x$-et csináljuk, a negatív $\neg x$ literál meg így elsőre úgy fog oldalhelyesen $0$-t vagy $1$-et felvenni, ha belőle $(1-x)$-et készítünk;
• végül, egy klózból egy egyenlőtlenség lesz. A klóz akkor igaz, ha van benne igaz literál (aminek az ILP alakban $1$ az értéke), és akkor hamis, ha minden literál hamis benne (azaz $0$). Tehát ha a klózban a literálok(nak megfeleltetett $x$-ek és $(1-x)$-ek) összege $0$, akkor hamis, amúgy pedig igaz lesz. Tehát az $\ell_1\vee\ldots\vee\ell_k$ klózból egy $\sum_{i=1}^{k}\ell_i\geq 1$ egyenlőtlenség pont megfelelő lesz, és ez minden, amit a visszavezetésnek tennie kell.

Egy példán keresztül: ha az input CNF az $(x_1\vee\neg x_2\vee x_3)\wedge(x_2\vee\neg x_3)$, abból a következő egyenlőtlenség-rendszer lesz:

$0\leq x_1,x_2,x_3\leq 1$,

$x_1+(1-x_2)+x_3\geq 1$,

$x_2+(1-x_3)\geq 1$.

Ha valakit zavar, hogy ez nem pont a mátrix alakban van, akkor némi (polinomidejű :D ) átrendezés után:

$x_1\geq 0$, $x_2\geq 0$, $x_3\geq 0$, $-x_1\geq -1$, $-x_2\geq -1$, $-x_3\geq -1$,

$x_1 - x_2 + x_3 \geq 0$,

$x_2-x_3\geq 0$

a generált egyenlőtlenség-rendszerünk. Ennek pont akkor van megoldása, ha az input SAT kielégíthető volt. (Például $x_1=1,x_2=1,x_3=0$ kielégíti az input formulát is és az egyenlőtlenség-rendszerünket is.)

A bonyelm kurzuson a visszavezetésekből olyan tanulságokat fogunk levonni, hogy egy probléma nehéz. Konkrétan, ha $A\leq B$ és $A$-ról már tudjuk, hogy nehéz, akkor $B$ is nehéz kell legyen. Így van ez a fenti példában is: nemsokára látjuk előadáson, hogy a SAT egy "nehéz" probléma (hogy ez mit jelent, egyelőre szakmai titok), és emiatt az ILP is nehéz kell legyen, mert a SAT visszavezethető rá. Erről még később.

folytköv nextweek