Evil regexek

...szóval, mikor is baj az a backtrack.

Az egrep (és talán a tcl) regex motorja rendes, véges automatás elvű, az $O(n\cdot m)$ időigényét nem lehet semmilyen regexszel (eek) és/vagy inputtal legyalázni, kb minden más programozási környezetét (kivéve a hírek szerint a C++11 <regex> könyvtárát, amit még nem volt érkezésem kipróbálni - ha a hírek igazak, az a ma létező legjobb cucc. Részletek később) viszont igen, mert azok backtracket használnak.

A backtracking illesztés nem csak azt mondja meg, hogy az input regexre illeszkedik-e a text, de azt is, hogy hol van az illeszkedés. Dióhéjban:

1. A specifikáció szerint a legelső illeszthető pozíción kell kezdődjön a visszaadott illeszkedés. Ezért a regex motorok lényegében egy forciklussal végigpróbálgatják szépen először az első, majd a második, stb. karakternél kezdve illeszteni az egész regexet.
2. Alternatívákat balról jobbra próbál végig. Így például az $(a|aa|b)$ regexnél előbb az $a$, majd az $aa$, ha az $a$-val nem sikerült, végül ha azzal sem, a $b$ alternatívát próbálja.
3. Az $*$ iteráció és a $?$ opcionális operátorok mohók. Ha tehát aktuálisan a jelenlegi pozíciótól egy $R?$ subregexet akarunk illeszteni, akkor oda először is megpróbálja illeszteni az $R$ regexet (azt is olyan hosszan, ahogy csak lehet), ha sikerül, akkor megy tovább az engine. Ha ezek után az egész regex maradék része nem illeszkedik a maradék textre, akkor az $R$ regexet rövidebb substringre akarja illeszteni, ha úgy sem, még rövidebbre, végül ha sehogy nem áll össze, akkor az $R?$-nek az opcionális, kihagyó ágára fut rá, és úgy próbálja befejezni az illesztést. Ha így se sikerül, akkor ebből az állapotból is visszalépés a keresésben.

Ezt a hármas pontot egy-két példával szemléltetném inkább: van mondjuk az $ab?b$ regexet, és illesszük az $aab$ textre.

• Először az $ab?b$-t az első $a$-ra próbálja illeszteni. Az $a$ stimmel. Most $b?b$-t illeszti a fennmaradó $ab$-re. A $b?$ részt ilesztve az $ab$-re először $b$-t illeszt $ab$-re, nem illeszkedik, mert $a$-val kezd. Akkor a $b?$ subregexet üres stringgel oldja meg (tehát kihagyja), és már csak a regex végén lévő $b$-t illeszti az $ab$-re. Nem sikerül. Visszalépés.
• Most az $ab?b$-t a második $a$-nál kezdve próbálja illeszteni. Az $a$ oké, $b?b$-t akar illeszteni a fenmaradó $b$-re, akkor először kipróbálja, hogy ha a $b?$-beli $b$-t illeszti, mi történik. Sikerül, a regex maradék $b$-jét kell a.. elfogyott a text. Akkor ez így nem jó, visszalép. Most a $b?$-et skippeléssel illeszti, és a regex maradék $b$-jét a text maradékára, $b$-re próbálja illeszteni, sikerül, mindenki boldog, illeszkedik a regex: a második pozíción kezdve, mégpedig úgy, hogy a $b?$ skippeli az opcionálist.

Mindenki boldog, kivéve, hogy mikor a Jeffrey Friedl könyvében ezt olvastam, az arcomon egy apró ideg elkezdett rángatózni... aztán kisétáltam az udvarra, felástam egy részét, és nem volt ezzel gondom.

Ahogy mondtam, a csillag is mohó operátor, annyiszor próbál illeszteni, ahányszor csak tud, azon belül pedig minden egyes iterációban amilyen hosszút csak tud. Ha rájön, hogy túl hosszan illesztett, akkor az utolsó iterációt rövidíti, majd elengedi, stb.

Ez még nem hangzik olyan veszélyesnek, igaz?

plain wrong

dehogynem.

Illesszük mondjuk az.. $(a^*)^*b$ regexet az $a^n$ textre, valamilyen $n$-re! Érzi remélem mindenki, hogy nem kéne illeszkedjen? Pastebin itt. Ideone.com output:

On a, .find run in 2451933 nanoseconds.
On aa, .find run in 69710 nanoseconds.
On aaa, .find run in 75366 nanoseconds.
On aaaa, .find run in 121180 nanoseconds.
On aaaaa, .find run in 419257 nanoseconds.
On aaaaaa, .find run in 421194 nanoseconds.
On aaaaaaa, .find run in 1158488 nanoseconds.
On aaaaaaaa, .find run in 2692903 nanoseconds.
On aaaaaaaaa, .find run in 1265485 nanoseconds.
On aaaaaaaaaa, .find run in 377794 nanoseconds.
On aaaaaaaaaaa, .find run in 672745 nanoseconds.
On aaaaaaaaaaaa, .find run in 1399777 nanoseconds.
On aaaaaaaaaaaaa, .find run in 2746695 nanoseconds.
On aaaaaaaaaaaaaa, .find run in 5498918 nanoseconds.
On aaaaaaaaaaaaaaa, .find run in 10948008 nanoseconds.
On aaaaaaaaaaaaaaaa, .find run in 21770596 nanoseconds.
On aaaaaaaaaaaaaaaaa, .find run in 43556607 nanoseconds.
On aaaaaaaaaaaaaaaaaa, .find run in 86682752 nanoseconds.
On aaaaaaaaaaaaaaaaaaa, .find run in 172915112 nanoseconds.
On aaaaaaaaaaaaaaaaaaaa, .find run in 345402683 nanoseconds.
On aaaaaaaaaaaaaaaaaaaaa, .find run in 653601295 nanoseconds.
On aaaaaaaaaaaaaaaaaaaaaa, .find run in 1266362512 nanoseconds.

és a szokásos timeout. Megint $a^{10}$ környékére ficcent be a hotspot, utána szépen duplázódott az időigény, $a^{22}$-re még sikerült illessze, aztán elszállt.

Miért is?

Az első menetben $a^{20}$-ra (mondjuk nézzük ezt) illeszti $(a^*)^*b$-t. Ehhez először $(a^*)^*$-ot illeszt a legelső karaktertől. Ahhoz $a^*$-ot illeszt a legelső karaktertől. Itt iterációban szépen megpróbál annyi $a$-t benyelni, amennyit csak lehet: az $a^*$ rész megeszi az egész inputot. Elfogyott az input, most ide próbálná illeszteni a $b$-t, nem sikerül, visszalép.

Most az az eset jön, mikor a belső $a^*$ már szerényebben csak $a^{19}$-et nyel le. Ezután az $(a^*)^*$-on futó motor azt mondja, hogy oké, akkor egy iterációban a belső rész lenyelt $19$ darab $a$-t, próbáljunk meg még egy iterációt! Illeszti az $a^*$-ra a maradék $a$-t, betalál, elfogyott az input, jé, megint nincs a végén $b$. Akkor ezt a második iterációt elfelejtjük, és a text utolsó $a$-jára illesztjük a regexet záró $b$-t. Hm, nem sikerült. Akkor az első iterációs $a^*$ még szerényebb, már csak $18$ karaktert nyel le, marad $aa$ a textből, amin a motor továbbra is az $(a^*)^*b$-t próbálja illeszteni. Először a belső $a^*$-gal lenyeleti az egész textet, elfogy, nem passzol a $b$, oké, akkor a belső $a^*$-gal csak az első $a$-t nyeleti be, és a maradék $a$-ra illeszti tovább az $(a^*)^*b$-t, a belső $a^*$-gal először lenyeleti az egész $a$-t, elfogy, nem passzol a $b$, akkor skippeli az $a^*$-ot, rájön, hogy a $b$ nem illeszkedik az $a$-ra, visszalép, akkor az $aa$-ra illeszti $(a^*)^*b$-t úgy, hogy az egész csillag üres stringre illjen, jé, a $b$ nem illeszkedik az $aa$-ra se, visszalépek, az első iterációs $a^*$ már csak $17$ karaktert szeretne, akkor $(a^*)^*b$-t illesztjük $aaa$-ra úgy, hogy először $3$, majd $2+1$, majd $2$, majd $1+2$, majd $1+1+1$, majd $1+1$, majd $1$, végül $0$ darab $a$-t akarunk lenyeletni, de persze az a $b$ egyszer se lesz ott...

...ha kiszámoljuk, ez azt jelenti, hogy a regex illesztő backtracking motor $(a^*)^*b$-t $a^n$-re illesztéskor $\Theta(2^n)$ idő alatt jön rá, hogy ez bizony nem illeszkedik. (És ahogy a fenti ideone logot láthatjuk, ez Javában is így megy...)

Mikor ezt olvastam a Jeffrey Friedl könyvében, becsuktam a könyvet, kimentem a fejszémért, kivágtam egy (kiszáradt) fát, ittam egy sört, visszamentem olvasni és megállapítottam, hogy valaki elég kókány munkát végzett valamikor.

A fenti "catastrophic backtracking" (mikor sikerül kicsalni egy exponenciális futásidőt egy alkalmasan megválasztott texten való futtatással) viselkedést mutatni képes regexeket (mint amilyen az $(a^*)^*b$ is) Evil (vagy malicious) Regexnek hívják :) ha ne adj'Isten egy webszerveren a user inputot egy evil regexre illesztik, az egy remek kiindulópontja a ReDoS (regular expression denial of service) támadásnak (ld még itt): a usernek más dolga nincs is, csak egy megfelelően craftolt stringet beírni a form megfelelő input fieldjébe, amit ha a szerver elkezd illeszteni, azzal garantáltan elfoglalkozik egy darabig :D

Az előző post $(a?)^na^n$ regexe az nem ilyen volt, mert az exponenciális viselkedéshez a regexet is egyre hosszabbra kellett venni. Ha szervert támadsz, akkor az azon levő adott regexhez kell megfelelő textet gyártani. De ha a regexedben van olyan $R^*$ vagy $R^+$ alakú rész, hogy az $R$ illeszkedik valami $u$ (nemüres) szóra és annak egy hatványára is (pl. $a$-ra is és $aa$-ra is, vagy $aba$-ra és $abaabaaba$-ra is stb), akkor ezt a regexet egy olyan text, amiben sok áll egymás után ebből az $u$-ból ezen a helyen (és melyre a regex nem illeszkedik, hogy végig kelljen tekernie a backtracket), catastrophic backtrackingbe fogja küldeni. They are all evil, period.

Egyszerű példák evil regexekre:

• $(a^*)^*$ - ez egy iteráció, aminek a belseje illeszkedik $a$-ra is és $aa$-ra is, és ahogy láttuk, $a^{30}$ már elszállítja ideone.on
• $(a|aa)^*$ - ugyanez
• $([a-zA-Z]^+)^*$ - "karaktersorozatok egymás után", szeparátor nélkül? nem jó, szintén $a$ és $aa$ is illeszkedik belül
• $(.^*,?)^+$ - vesszőkkel elválasztott szavak, gondolom ilyesmi akart volna lenni, utolsó vessző elhagyható, ezért opcionális. Ez több sebből is vérzik, de eleve a $.^*$ regexet jó ötlet kerülni, amennyire csak lehet. Belül így illeszkedik pl. $a$-ra és $aa$-ra is, de ha a vessző nem is lenne opcionális, még akkor is a $,$ és $,,$ szavakra is illeszkedik... A $.^*$ regex pedig a korábbiak szerint ha idefut a backtrack, először is szépen benyeli az input teljes maradék részét, utána egyet, még egyet, ... visszaad a regex további részének. Ez elég időigényes tud lenni (bár "csak" egy $N$-es szorzó, a text hosszával szorzódik, de az se kevés)
• $(a|a?)^+$ - ez evil, de nem a fenti ökölszabály miatt. A backtracking motor először az $a$-t próbálja illeszteni, ha az nem sikerül, akkor az $a?$-et, melyet is először úgy, hogy $a$-t, majd úgy, hogy üres stringet illeszt. Ezt a három lehetőséget aztán végigpörgeti az összes további $a$-ra is...
• Guglizva emailcím regexre meg lehet kapni akár ezt. Ennek a közepén van egy ilyen: $(([-.]|[\_])^?[a-zA-Z0-9]^+)^*$, azaz mínusz, pont vagy underscore ESETLEG ($?$), utána alfanumerikus nemüres string, ezt ismételjük. Itt ugye a gond a $?$, amiatt az első csoport akár üresre is illeszthető és az iterált rész matchel bármilyen alfanumerikussal. Pl $a$, $aa$... ne írjunk soha ilyesmit: $(R_1?R_2^*R_3?)^*$, mert ebbe belefér az $(R_2^*)^*$ is akár, amiről tudjuk, hogy rossz ötlet
• Itt van ez, hogy mi egy Java osztály neve: $([a-z]^+.)^+[A-Z][a-z]^+$, azaz (kisbetűk, akármi)párszor, nagybetű, megint kisbetűből néhány.  A "kisbetűk, akármi" részre illeszkedik $aa$ is és $aaaa$ is...

Szerencsére általában ezeket a regexeket (már ha észrevesszük, hogy a regexünk nem éppen hatékony ;) ) át lehet transzformálni olyan alakúra, amin a backtracking motor nem tölt el annyira sok időt, mint ezeken az evil formokon tölthet.

Ahogy az idő telt, egyre több és több szintaktikus elem került be a legtöbb regex motorba, amivel a backtracket irányíthatjuk (ha már automatánk nincs ugye..), legközelebb ezekről beszélek majd.

És arról is, hogy mi lehet az oka annak, hogy én magam se automatával, hanem backtrackkel próbálnék mai regexet illeszteni.

folytköv

mekkora cliffhanger

remélem, erre senki nem számított

regex matching algorithm: a success story (NOT)

..szóval úgy volt, hogy Ken Thompson a '60-as évek közepén ugye kitalálta a remek időigényű algoritmusát regex illesztésre, $m$ hosszú regexet $N$ hosszú szövegre $O(m\cdot N)$ idő alatt illeszt véges, nemdeterminisztikus automatát használva.

Amit nem tett bele a Unix-ba '71-ben, sem a grep-be: ehelyett backtracket implementált. Erre azért jó oka volt: amit akkor támogattak ezek a rendszerek, abba se a $|$ (unió), se a $+$ (iteráció), se a $?$ (opcionális) jelek nem kerültek bele, így lényegében kb csak karakterosztályokat lehetett konkatenálni, arra jó a backtrack, szintén lineáris időigénye lesz.

Alfred Aho viszont megcsinálta '79-re a teljes "klasszikus" regex illesztő motort a grepbe, majd később '85-ben a Unix-ba is. Az ő implementációja a regex$\to$NFA$\to$DFA, majd illesztés vonalat követte, így még $O(2^m\cdot N)$ időigényű volt. (Still a better love story than twilight, mert a regex általában rövid. Habár azért ránézhetünk az RFC822-re, hogy mi is az "official" regex emailcím validálásra...) 

Aztán jött Rob Pike, aki lényegében feltalálta még egyszer Ken Thompson algoritmusát és a sam szövegszerkesztőbe már ez került bele a '80-as évek közepén, egy remek kis $O(m\cdot N)$-es időigényű regex illesztő motor, ami libként bekerült a Unix nyolcadik kiadásába.

End of story, happy end?

nem hát.

Ezt követően ugyanis jött Henry Spencer, aki, ahogy a wikin olvashatjuk, "wrote a non-proprietary replacement for regex(3), the Unix library for handling regular expressions, and made it freely available; his API followed that of Eighth Edition Research Unix". Tehát, a Unix nyolcas változatában levő regex illesztőnek elkészítette egy ingyenes, nyílt forrású változatát, ugyanazzal az API-val.

hja, API-val. az input és az output specifikáció tényleg ugyanaz lett.

csak azt nem tudta, hogy a motor hogy működik, ezért backtrackkel implementálta le ezt a nyílt forrású változatot. Értjük? a hatékony, szélvészgyors, de nem nyílt forrású regex illesztő motor helyett Spencer backtrack implementációja ment ki a köztudatba és terjedt el, mert az volt a nyílt forrású. Ez belekerült a perl nyelv motorjába, ami egy, a regex matchinget nyelvi szinten támogató programozási nyelv, és innen a PCRE (perl compatible regular expression) libraryvel szépen továbbment pl. a PHP (pcre_... függvények), Java (java.util.regex.Matcher és java.util.regex.Pattern), Ruby, Python, stb. programozási nyelvekbe is, amik ezért

a mai napig backtrackkel végzik az illesztést

és ez nem is valószínű, hogy meg fog változni.

Ez azért elég komoly problémákat tud okozni. Ha például az $(a?)^na^n$ regexet akarjuk illeszteni az $a^n$ textre (valamekkora $n$-re), annak nyilván illeszkednie kéne: az opcionális $a?$-eket végig kihagyjuk, és a maradék $a^n$ a regexből szépen illeszkedik az $a^n$ textre.

Itt egy Java kód hozzá, ezt az illesztést csinálja forciklussal $n=1\ldots 30$ közt. Ha ezt pl. ideone.com-on futtatjuk (az osztályt default package-be kell átrakni és System.err helyett System.out-ra printelni, hogy lássuk), ezt kapjuk:

i = 1 found in 2522746 nanoseconds.
i = 2 found in 110668 nanoseconds.
i = 3 found in 43774 nanoseconds.
i = 4 found in 53771 nanoseconds.
i = 5 found in 311331 nanoseconds.
i = 6 found in 126130 nanoseconds.
i = 7 found in 214845 nanoseconds.
i = 8 found in 817853 nanoseconds.
i = 9 found in 443221 nanoseconds.
i = 10 found in 1894930 nanoseconds.
i = 11 found in 310500 nanoseconds.
i = 12 found in 572593 nanoseconds.
i = 13 found in 1135540 nanoseconds.
i = 14 found in 2214628 nanoseconds.
i = 15 found in 4528347 nanoseconds.
i = 16 found in 9271553 nanoseconds.
i = 17 found in 19245308 nanoseconds.
i = 18 found in 39593656 nanoseconds.
i = 19 found in 79272588 nanoseconds.
i = 20 found in 168863023 nanoseconds.
i = 21 found in 346571873 nanoseconds.
i = 22 found in 725774631 nanoseconds.
i = 23 found in 1445924416 nanoseconds.

és ezután elszáll timeouttal. Az elejét nem kell nézni, az még akkor történik, mikor melegszik a Java HotSpot, $i=11$ körülre bemelegszik és onnan mit látunk? $i=12$-től kezdve szinte tökéletes konzisztenciával mindegyik futásidő duplája az előzőnek. Ez annyira látványosan exponenciális futásidő, hogy azt tanítani kéne :D

Ez itt egy PHP kód, ugyanerre. Ha ezt futtatjuk, jön az output:

preg_match (a?)<sup>n</sup>a<sup>n</sup> on a<sup>n</sup>...<br/>
i = 1: 0.00009 seconds, answer: 1<br/>
i = 2: 0.00003 seconds, answer: 1<br/>
i = 3: 0.00002 seconds, answer: 1<br/>
i = 4: 0.00002 seconds, answer: 1<br/>
i = 5: 0.00003 seconds, answer: 1<br/>
i = 6: 0.00002 seconds, answer: 1<br/>
i = 7: 0.00003 seconds, answer: 1<br/>
i = 8: 0.00005 seconds, answer: 1<br/>
i = 9: 0.00007 seconds, answer: 1<br/>
i = 10: 0.00012 seconds, answer: 1<br/>
i = 11: 0.00025 seconds, answer: 1<br/>
i = 12: 0.00047 seconds, answer: 1<br/>
i = 13: 0.00095 seconds, answer: 1<br/>
i = 14: 0.00193 seconds, answer: 1<br/>
i = 15: 0.00392 seconds, answer: 1<br/>
i = 16: 0.00815 seconds, answer: 1<br/>
i = 17: 0.01643 seconds, answer: 1<br/>
i = 18: 0.03618 seconds, answer: 1<br/>
BULLSHIT! i = 19: 0.06781 seconds, answer: <br/>
BULLSHIT! i = 20: 0.06848 seconds, answer: <br/>
BULLSHIT! i = 21: 0.06995 seconds, answer: <br/>
BULLSHIT! i = 22: 0.06708 seconds, answer: <br/>
BULLSHIT! i = 23: 0.06774 seconds, answer: <br/>
BULLSHIT! i = 24: 0.06841 seconds, answer: <br/>
BULLSHIT! i = 25: 0.06767 seconds, answer: <br/>
BULLSHIT! i = 26: 0.06967 seconds, answer: <br/>
BULLSHIT! i = 27: 0.06852 seconds, answer: <br/>
BULLSHIT! i = 28: 0.06655 seconds, answer: <br/>
BULLSHIT! i = 29: 0.07058 seconds, answer: <br/>
BULLSHIT! i = 30: 0.06759 seconds, answer: <br/>
BULLSHIT! i = 31: 0.06765 seconds, answer: <br/>
BULLSHIT! i = 32: 0.06806 seconds, answer: <br/>
BULLSHIT! i = 33: 0.06781 seconds, answer: <br/>
BULLSHIT! i = 34: 0.07048 seconds, answer: <br/>
BULLSHIT! i = 35: 0.06778 seconds, answer: <br/>
BULLSHIT! i = 36: 0.06683 seconds, answer: <br/>
BULLSHIT! i = 37: 0.06969 seconds, answer: <br/>
BULLSHIT! i = 38: 0.06829 seconds, answer: <br/>
BULLSHIT! i = 39: 0.06688 seconds, answer: <br/>
BULLSHIT! i = 40: 0.06711 seconds, answer: <br/>
BULLSHIT! i = 41: 0.06732 seconds, answer: <br/>
BULLSHIT! i = 42: 0.06824 seconds, answer: <br/>
BULLSHIT! i = 43: 0.06870 seconds, answer: <br/>
BULLSHIT! i = 44: 0.07062 seconds, answer: <br/>
BULLSHIT! i = 45: 0.07048 seconds, answer: <br/>
BULLSHIT! i = 46: 0.06767 seconds, answer: <br/>
BULLSHIT! i = 47: 0.06768 seconds, answer: <br/>
BULLSHIT! i = 48: 0.06814 seconds, answer: <br/>
BULLSHIT! i = 49: 0.06778 seconds, answer: <br/>

ez még mókásabb, mint a Java: $i=9$-re felmelegszik, onnan kezdve szépen duplázódik az idő $i=18$-ig, meg is találja, hogy illeszkedik, de aztán! aztán mivel a backtracking motor túl sokáig fut, a függvény kilövi (how to handle backtrack 101 :D ), és azzal jön vissza lejárt időlimit után, hogy nem illeszkedik a regexre a string. Nem tudnám megmondani, hogy ez a mindenféle hibakód nélkül visszajövő hibás válasz, vagy a Java-féle timeout a jobb megoldás :D

Bottom line: ha regexet illesztesz egy mainstream programozási nyelvben, jó eséllyel egy csonthülye backtracking algoritmus fogja neked csekkolni az illeszkedést. Emiatt egymásba ágyazott csillagoknál, alternálásnál egész jó esélyed van arra, hogy ne sikerüljön az illesztés, hanem timeouttal elszálljon az egész.

Legközelebb megnézünk egy-két tippet, hogy ha már backtracking motort kell használj, mert az van a nyelvedben, akkor hogy érdemes megszerkeszteni azt a regexet, hogy gyorsabban lefusson a backtrack :)

folytköv

(források: itt)

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

Bonyelm gyakjegyzet 2014, 1. gyak

re,

kicsit off voltam nyáron. Nemsokára folytatom a regexes threadet is (remélem), addig is elkezdek itt egy bonyelm gyakjegyzetet loggolni :-)

Első jóhír, hogy jótanácsot követve belőttem a MathJaxet, úgyhogy most már talán ki fognak nézni valahogy a matekos jelek is.

Első gyakorlaton (követelményismertetés után ofc) felidéztük, hogy futásidőket és tárigényeket akarunk majd összehasonlítani és számolgatni, ezeket pedig elég lesz csak nagyságrendben ismernünk, nem a pontos függvényeket. Ha $f$, $g$ függvények (mondjuk természetes számokat valós számokra képezőek, de lehet az értelmezési tartomány is a pozitív valós, vagy az értékkészlet a természetes, mindegy), akkor azt mondjuk, hogy $f=O(g)$ (ami kb. a "$g$ legalább olyan gyorsan nő, mint $f$"-nek felel meg), ha van olyan $c>0$ konstans, amire $f\leq c\cdot g(n)$ majdnem minden $n$-re (ami matekul ugyanaz, mint hogy "van olyan $N$ küszöbszám, hogy ha $n>N$, akkor már igaz).

• Például, $3n=O(\frac{n^2}{100})$, mert ha $c=100$ és $N=3$, akkor tényleg fennáll, hogy ha $n>3$, akkor $3n \leq 100\cdot\frac{n^2}{100}=n^2$ (egyszerűsítünk $n$-nel, kész).

Az $O$ (e. ordó) kapcsolatnál szigorúbb az $o$ (kisordó) kapcsolat: $f=o(g)$, ha tetszőleges $c>0$-ra $f(n)\leq c\cdot g(n)$ majdnem minden $n$-re. (Ez kb. a "$g$ gyorsabban nő, mint $f$"-nek felel meg.) Ilyenkor már nem mondani kell egy $c$-t és egy $N$-t, hanem tetszőleges $c>0$-ra mondani kell egy $N$-t, amitől kezdve igaz az összefüggés.

• Például, $3n=o(\frac{n^2}{100})$ is igaz, hiszen ha $c>0$, akkor átrendezve kapjuk, hogy ha $\frac{300}{c}\leq n$, akkor $3n\leq c\cdot\frac{n^2}{100}$.

Ezután megláttuk a $\log^2 n=o(n)$ feladatot.. hát erre input $c>0$ küszöbszámra mondani megfelelő $N$-t már nem nekünk való feladvány (megjegyzés: a $\log$ mindig kettes alapú logaritmust jelent, mi mást, a $\log^2 n$ pedig a $(\log n)^2$-nek egy átláthatóbb formája. Nem pedig pl. a $\log\log n$-nek). Szerencsére "tudjuk", hogy ha $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$, akkor $f=o(g)$. Ha pedig a limesz legalábbis kisebb, mint végtelen (tehát például 7, 0 vagy $\pi$), akkor $f=O(g)$ lesz.

Ezután már könnyű volt, mert $\lim_{n\to\infty}\frac{\log^2 n}{n}$ a L'Hopital-szabály szerint ugyanannyi, mint $\lim_{n\to\infty}\frac{2\cdot\ln 2\cdot\log n}{n}$, ami megint ugyanemiatt a szabály miatt $\lim_{n\to\infty}\frac{2\cdot\ln 2\cdot\ln 2}{n}$, ami tényleg $0$, tehát $\log^2 n=o(n)$. Persze akármilyen $k>0$ konstanst is mondunk, ezek szerint $\log^k(n)=o(n)$ is igaz lesz - ez nálunk annyit tesz, hogy akár futásidőről, akár tárigényről lesz szó, a $\log^k(n)$ alakú erőforrás-igényt jobbnak fogjuk tartani, mint a lineárist. (A $\log^k(n)$ alakú függvényeket egyébként polilogaritmikus függvénynek hívjuk.) Persze ha szekvenciális algoritmusról beszélünk, annak nem lehet $o(n)$ (amit szublineárisnak is mondunk) az időigénye, hiszen ennyi lépésben nem tudja végigolvasni se az inputot. Amikor elő fognak jönni szublineáris függvények:

• tárigénynél;
• párhuzamos számítás időigényénél.

Példaképp felhoztam, hogy az ${Elérhetőség}$ probléma (input: irányított gráf, csúcsai $1$-től $n$-ig a számok, output: van-e út $1$-ből $n$-be?) az egy könnyű probléma, lineáris időigényű algoritmus van rá, pl. a mélységi keresés. Vagy a szélességi. Viszont ezek az algoritmusok mind $n$ tárat használnak (mert jelölgetik a csúcsokat). Házi jellegű feladatra kértem, hogy próbáljunk készíteni szublineáris tárigényű algoritmust, ami szintén eldönti az ${Elérhetőség}$ problémát.

Megnéztük még azt is, hogy $n^2=o(2^n)$, hiszen két L'Hopital szabály után kapjuk, hogy $\lim\frac{n^2}{2^n}=\lim\frac{2n}{\ln 2\cdot 2^n}=\lim\frac{2}{\ln 2\ln 2\cdot 2^n}=0$. Általában is igaz, hogy ha $p$ polinom, $e$ pedig exponenciális függvény, akkor $p=o(e)$, legyen akármekkora a polinom fokszáma és akármilyen pici is az $e$ alapja. Általában futásidőről ha szó lesz, akkor a polinomnak fogunk örülni, azt tekintjük hatékony algoritmusnak, ami polinom időigényű (legrosszabb esetben is), és egy problémát hatékonyan megoldhatónak akkor hívjuk, ha van rá polinom időigényű algoritmus. (Ez a Cobham-Edmonds tézis.)

Házi jelleggel megnézhetjük, hogy az exponenciális lassabban nő, mint $n!$, ami pedig lassabb, mint a $2^{n^2}$.

Voltam konferencián

...augusztusban, kétszer is. Előbb a DCFS 2014 volt Turkuban (ahol beszéltem is eredményekről), majd az MFCS 2014 Pesten (pontosabban Budán). Aki szakmai "élménybeszámolóra" kíváncsi, elérheti itt az előbbiét, itt az utóbbiét.