2-kielégíthetőség

kielégíthetőségi probléma, ahol minden klóz legfeljebb két literált tartalmaz

Az informatikában a 2-kielégíthetőség, 2-SAT vagy csak a 2SAT egy számítási probléma a változókhoz való értékek hozzárendelésével kapcsolatban, amelyek mindegyikének két lehetséges értéke van, hogy megfeleljen a változópárokra vonatkozó kényszerrendszernek. Ez egy speciális esete az általános logikai kielégítési problémának, amely kettőnél több változóra vonatkozhatnak a megszorítások, valamint a kényszer-elégedettségi problémának, amelyek kettőnél több választást tesznek lehetővé minden változó értékére. De ellentétben azokkal az általánosabb problémákkal, amelyek NP-teljesek, a 2-kielégíthetőség polinomiális időben megoldható.

A 2-es kielégíthetőségi probléma előfordulásait jellemzően speciális típusú Boole-képletekkel fejezik ki, amelyeket konjunktív normálformának (2-CNF) vagy Krom-formulának neveznek. Alternatív megoldásként kifejezhetők irányított gráfok speciális típusaként, az implikációs gráf, amely egy példány változóit és azok negációit a gráf csúcsaiként fejezi ki, a változópárokra vonatkozó kikötéseket pedig irányított élekként. Mindkét fajta bemenet megoldható lineáris időben, akár visszalépésen alapuló módszerrel, akár az implikációs gráf erősen összefüggő komponenseinek felhasználásával. A rezolúció, a kényszerpárok kombinálásának módszere további érvényes megszorítások létrehozására, szintén polinomiális időmegoldáshoz vezet. A 2-kielégíthetőség problémák a konjunktív normálalakú formulák két fő alosztályának egyikét jelentik, amelyek polinomiális időben megoldhatók; a másik a két alosztály közül a Horn-kielégíthetőség.

A 2-kielégíthetőség olyan geometriai és vizualizációs problémákra alkalmazható, amelyekben az objektumok gyűjteményének két lehetséges helye van, és a cél minden objektum számára olyan elhelyezést találni, amely elkerüli az átfedéseket más objektumokkal. Egyéb alkalmazások közé tartozik az adatok klaszterezése a klaszterek átmérőinek összegének minimalizálása érdekében, az osztálytermi és sportütemezés, valamint az alakzatok visszaállítása a keresztmetszeteik információiból.

A számítási komplexitáselméletben a 2-kielégíthetőség egy olyan NL-teljes probléma példája, amely logaritmikus mennyiségű tárhely használatával nem-determinisztikusan megoldható, és amely az egyik legnehezebb megoldható probléma ebben az erőforrás-korlátban. A 2-kielégíthetőség példány összes megoldásának halmaza megadható egy mediángráf szerkezetével, de ezeknek a megoldásoknak a számlálása #P-teljes, ezért nem várható, hogy polinomiális idejű megoldása lesz. A véletlenszerű példányok éles fázisátalakuláson mennek keresztül a megoldhatóból a megoldhatatlanba, ahogy a megszorítások és a változók aránya 1 fölé nő, ez a jelenség feltételezhető, de nem bizonyított a kielégíthetőségi probléma bonyolultabb formáira. A 2-es teljesíthetőség számításilag nehéz variációja, olyan igazság-hozzárendelés megtalálása, amely maximalizálja a kielégített megszorítások számát, van egy közelítő algoritmusa, amelynek optimálissága az egyedi játékok sejtésétől függ, és egy másik nehéz variáció, egy kielégítő hozzárendelés megtalálása, amely minimalizálja a valódi változók számát, a paraméterezett komplexitás fontos tesztje.

ProblémareprezentációkSzerkesztés

 
Az ebben a szakaszban bemutatott példa 2-kielégíthetőség példányának implikációs grafikonja

A 2-kielégíthetőség probléma egy speciális korlátozott formájú Boole-féle kifejezéssel írható le. Ez a tagmondatok konjunkciója (a logikai és művelet), ahol minden tagmondat két változó vagy negált változó diszjunkciója (logikai vagy művelet). Az ebben a képletben szereplő változókat vagy tagadásaikat literáloknak nevezzük.[1] Például a következő képlet konjunktív normál formában van, hét változóból, tizenegy klózból és 22 literálból áll:

 
A 2-kielégíthetőség probléma az, hogy ezekhez a változókhoz olyan igazság-hozzárendelést találjunk, amely az egész képletet igazzá teszi. Az ilyen hozzárendelés eldönti, hogy mindegyik változó igaz vagy hamis legyen, így minden klózban legalább egy literál igaz lesz. A fent bemutatott kifejezéshez az egyik lehetséges kielégítő hozzárendelés az, amely mind a hét változót igazra állítja. Minden klóznak van legalább egy nem negált változója, így ez a hozzárendelés minden klózt kielégít. 15 másik módja is van az összes változó beállításának, hogy a képlet igaz legyen. Ezért a kifejezés által képviselt 2-kielégíthetőség példány kielégíthető.

Az ilyen formájú képleteket 2-CNF képleteknek nevezzük. A „2” ebben a névben a klózonkénti literálok számát jelöli, a „CNF” pedig a konjunktív normálformát, a logikai kifejezések egy típusát, amely diszjunkciók kötőszó formájában jelenik meg.[1] Krom-képleteknek is nevezik őket Melven R. Krom, UC Davis matematikus munkája alapján, akinek 1967-es tanulmánya az egyik legkorábbi munkája volt a 2-kielégíthetőség problémája.[2]

A 2-CNF képletben minden klóz logikailag ekvivalens az egyik változóból vagy negált változóból a másikra vonatkozó implikációval. Például a példa második klóz három egyenértékű mód bármelyikével írható:

 
A különböző típusú műveletek közötti ekvivalencia miatt egy 2-kielégíthetőség példányt implicatív normál formában is fel lehet írni, amelyben a konjunktív normál alakban mindegyik vagy kitételt lecseréljük arra a két implikációra, amellyel egyenértékű.[3]

A 2-kielégíthetőség példányok leírásának egy harmadik, grafikusabb módja az implikációs gráf. Az implikációs gráf olyan irányított gráf, amelyben változónként vagy negált változónként egy csúcs van, és egy él, amely összeköti az egyik csúcsot a másikkal, amikor a megfelelő változókat egy implikáció kapcsolja össze a példány implikatív normális alakjában. Az implikációs gráfnak ferdeszimmetrikus gráfnak kell lennie, ami azt jelenti, hogy van egy olyan szimmetriája, amely minden változót a negációjához visz, és megfordítja az összes él orientációját.[4]

AlgoritmusokSzerkesztés

A 2-kielégíthetőség probléma megoldására számos algoritmus ismert. Közülük a leghatékonyabbak lineáris időt vesznek igénybe.[2] [4] [5]

Rezolúció és tranzitív lezárásSzerkesztés

Krom (1967) leírta a következő polinomiális idejű döntési eljárást a 2-kielégíthetőség példányok megoldására.[2]

Tegyük fel, hogy egy 2-kielégíthetőség példány két olyan klózot tartalmaz, amelyek mindkettő ugyanazt az x változót használja, de az x az egyik klózban negált, a másikban nem. Ezután a két klóz kombinálható egy harmadik klóz létrehozásával, amelyben a két másik literál szerepel; ennek a harmadik klóznak is kielégíthetőnek kell lennie, ha az első két klóz is kielégíthető. Például kombinálhatjuk a klózokat   és   ilyen módon előállítani a záradékot  . A 2-CNF képlet implicitív formáját tekintve ez a szabály két következményt jelent   és  , és a tranzitivitásból következtetve egy harmadik implikációra  .[2]

Krom azt írja, hogy egy képlet akkor konzisztens, ha ennek a következtetési szabálynak az ismételt alkalmazása nem tudja előállítani mindkét klózt   és  , bármely változóhoz  . Ahogy Krom bizonyítja, a 2-CNF képlet akkor és csak akkor teljesíthető, ha konzisztens. Mert ha egy képlet nem konzisztens, akkor nem lehet mindkét klózt kielégíteni   és   egyidejűleg. És ha konzisztens, akkor a képlet kiterjeszthető a forma egy klózának ismételt hozzáadásával   vagy   egyszerre, minden lépésben megőrizve a konzisztenciát, amíg minden változóhoz nem tartalmaz ilyen klózt. Mindegyik kiterjesztési lépésnél a következetesség megőrzése mellett mindig hozzáadható a két klóz egyike, mert ha nem, akkor a másik klóz előállítható a következtetési szabály segítségével. Miután minden változónak van ilyen formájú klóza a képletben, az összes változó kielégítő hozzárendelése generálható egy   változó beállításával igazra, ha a képlet tartalmazza a klózt   és hamisra állítva, ha a képlet tartalmazza a klózt  .[2]

Krom elsősorban a következtetési szabályrendszerek teljességével foglalkozott, nem pedig az algoritmusok hatékonyságával. Módszere azonban polinomiális időkorláthoz vezet a 2-kielégíthetőség problémák megoldásához. Az ugyanazt a változót használó klózok csoportosításával, és a következtetési szabály alkalmazásával minden klózpárra, meg lehet találni minden olyan következtetést, amely egy adott 2-CNF-példányból lehetséges, és megvizsgálhatja, hogy konzisztens-e. az O(n3), ahol n a változók száma a példányban. Ez a képletet úgy kapjuk, hogy a változók számát megszorozzuk az adott változót tartalmazó klózpárok O(n2) számával, amelyekre a következtetési szabály alkalmazható. Így meg lehet határozni, hogy egy adott 2-CNF példány kielégíthető-e O(n3) időben. Mivel a Krom-módszerrel kielégítő hozzárendelés megtalálása O(n) konzisztencia-ellenőrzések sorozatát foglalja magában, ez O(n4) időt vesz igénybe. Even, Itai & Shamir (1976) az O(n2) gyorsabb időkorlátját idézi ehhez az algoritmushoz, amely a műveletek gondosabb rendezésén alapul. Ennek ellenére még ezt a kisebb időkorlátot is jelentősen javították Even, Itai & Shamir (1976) és Aspvall, Plass & Tarjan (1979) lineáris idő algoritmusai.

A 2-kielégíthetőség példány implikációs gráfja szempontjából a Krom-féle következtetési szabály a gráf tranzitív lezárását konstruálja. Amint azt Cook (1971) megjegyzi, a Davis–Putnam-algoritmus egy példányaként is felfogható a kielégítési problémák megoldására a rezolúció elvén. Helyessége a Davis–Putnam algoritmus általánosabb helyességéből következik. Polinomiális időkorlátja abból adódik, hogy minden felbontási lépés növeli a klózok számát a példányban, aminek felső határa a változók számának másodfokú függvénye.[6]

Korlátozott visszalépésSzerkesztés

Even, Itai & Shamir (1976) egy korlátozott visszalépést magában foglaló technikát ír le a kényszer-kielégíthetőség problémák megoldására bináris változókkal és páronkénti kikötésekkel. Alkalmazzák ezt a technikát az osztálytermi ütemezés problémájára, de megfigyelik, hogy ez más problémákra is vonatkozik, beleértve a 2-SAT.[5]

Megközelítésük alapötlete egy részigazság hozzárendelés felépítése, egy-egy változóval. Az algoritmusok bizonyos lépései „választási pontok”, olyan pontok, amelyeknél egy változó két különböző igazságérték közül adható meg, az algoritmus későbbi lépései pedig arra késztethetik, hogy a változó e választási pontok valamelyikére visszalépjen. Azonban csak a legutóbbi választástól lehet visszalépni. A legutóbbinál korábban hozott minden döntés végleges.[5]

Kezdetben nincs választási pont, és egy változó sincs hozzárendelve. Az algoritmus minden lépésben kiválasztja azt a változót, amelynek értékét beállítja, az alábbiak szerint:

  • Ha van olyan klóz, amelynek mindkét változója már be van állítva, oly módon, hogy meghamisítja a klózt, akkor az algoritmus visszalép a legutóbbi választási ponthoz, visszavonja a választás óta végzett hozzárendeléseket, és megfordítja az adott választáskor hozott döntést. Ha nincs választási pont, vagy ha az algoritmus már visszalépett a legutóbbi választási ponthoz, akkor megszakítja a keresést, és azt jelenti, hogy a bemeneti 2-CNF képlet nem kielégíthető.
  • Ha van olyan záradék, amelyben a klóz két változója közül az egyik már be van állítva, és a klóz még mindig igaz vagy hamis lehet, akkor a másik változót úgy állítjuk be, hogy a klóz igazzá váljon.
  • A fennmaradó esetben minden klóz vagy garantáltan igaz lesz, függetlenül attól, hogy a fennmaradó változókat hogyan rendelték hozzá, vagy a két változó közül még egyik sem lett hozzárendelve. Ebben az esetben az algoritmus új választási pontot hoz létre, és a hozzá nem rendelt változók bármelyikét tetszőlegesen választott értékre állítja.

Az algoritmus intuitív módon követi az összes következtetési láncot az egyes választások meghozatala után. Ez vagy ellentmondáshoz és visszalépéshez vezet, vagy ha nincs ellentmondás, abból az következik, hogy a választás helyes volt, ami kielégítő feladathoz vezet. Ezért az algoritmus vagy helyesen talál egy kielégítő hozzárendelést, vagy helyesen határozza meg, hogy a bemenet nem kielégítő.[5]

Even et al. nem írta le részletesen, hogyan kell ezt az algoritmust hatékonyan megvalósítani. Csak azt állítják, hogy "megfelelő adatszerkezetek használatával bármely döntés következményeinek megtalálása érdekében" az algoritmus minden lépése (a visszalépés kivételével) gyorsan végrehajtható. Egyes bemenetek azonban azt okozhatják, hogy az algoritmus sokszor visszalép, minden alkalommal sok lépést végrehajtva a visszalépés előtt, így az általános összetettsége nemlineáris lehet. A probléma elkerülése érdekében módosítják az algoritmust úgy, hogy az egyes választási pontok elérése után egyszerre kezdje meg a két hozzárendelés tesztelését a választási pontban lévő változókészlethez, és egyenlő számú lépést tölt el a két hozzárendelésre. Amint a két hozzárendelés egyikének tesztje újabb választási pontot hoz létre, a másik teszt leáll, így az algoritmus bármely szakaszában csak két ága van a visszakövetési fának, amelyek még tesztelés alatt állnak. Ily módon a két teszt elvégzésére fordított teljes idő bármely változó esetén arányos a bemeneti képlet azon változóinak és klózainak számával, amelyek értékei állandóan hozzá vannak rendelve. Ennek eredményeként az algoritmus összesen lineáris időt vesz igénybe.[5]

Erősen kapcsolódó komponensekSzerkesztés

Aspvall, Plass & Tarjan (1979) egy egyszerűbb lineáris időeljárást talált 2-kielégíthetőség esetek megoldására, a gráfelmélet erősen összefüggő komponensek fogalma alapján.[4]

Egy irányított gráf két csúcsát erősen összefüggőnek mondjuk, ha van irányított út az egyikből a másikba és fordítva. Ez egy ekvivalenciareláció, és a gráf csúcsai erősen összefüggő komponensekre, részhalmazokra particionálhatók, amelyeken belül minden két csúcs erősen összefügg. Számos hatékony lineáris idő algoritmus létezik a gráf erősen összefüggő összetevőinek megtalálására a mélységi első keresés alapján: a Tarjan-féle erősen összefüggő komponensek algoritmusa[7] és az út alapú erős komponens algoritmusa egyaránt egyetlen mélységi keresést hajt végre. Kosaraju algoritmusa két mélységi első keresést hajt végre, de nagyon egyszerű.

Az implikációs gráf szempontjából két literál ugyanahhoz az erősen összefüggő komponenshez tartozik, ha léteznek implikációs láncok az egyik literáltól a másikig és fordítva. Ezért a két literálnak azonos értékkel kell rendelkeznie bármely kielégítő hozzárendelésben az adott 2-kielégíthetőség példányhoz. Különösen, ha egy változó és a tagadása is ugyanahhoz az erősen összefüggő komponenshez tartozik, akkor a példány nem teljesíthető, mert lehetetlen mindkét literálhoz ugyanazt az értéket rendelni. Ahogy Aspvall et al. megmutatta, ez egy szükséges és elégséges feltétel : egy 2-CNF formula akkor és csak akkor teljesíthető, ha nincs olyan változó, amely ugyanahhoz az erősen kapcsolódó komponenshez tartozik, mint a tagadása.[4]

Ez azonnal egy lineáris idő algoritmushoz vezet a 2-CNF képletek kielégíthetőségének tesztelésére: egyszerűen hajtson végre egy erős kapcsolódási elemzést az implikációs gráfon, és ellenőrizze, hogy minden változó és negációja különböző komponensekhez tartozik-e. Azonban, mint Aspvall et al. is megmutattuk, hogy egy lineáris idő algoritmushoz vezet a kielégítő hozzárendelés megtalálásához, ha létezik ilyen. Algoritmusuk a következő lépéseket hajtja végre:

  • Szerkessze meg a példány implikációs gráfját, és keresse meg erősen összefüggő összetevőit bármely ismert lineáris idejű algoritmus segítségével az erős kapcsolódási elemzéshez.
  • Ellenőrizze, hogy valamelyik erősen kapcsolódó komponens tartalmaz-e változót és tagadását is. Ha igen, jelentse, hogy a példány nem kielégítő, és állítsa le.
  • Szerkesszük meg az implikációs gráf sűrítését, egy kisebb gráfot, amelynek minden erősen kapcsolódó komponenshez egy csúcsa van, és egy élt az i komponenstől a j komponensig, amikor az implikációs gráf tartalmaz egy uv élt úgy, hogy u az i komponenshez, v pedig az komponenshez tartozik. j. A kondenzáció automatikusan irányított aciklikus gráf, és az implikációs gráfhoz hasonlóan, amelyből létrejött, ferdeszimmetrikus.
  • Rendezd topológiailag a kondenzáció csúcsait. A gyakorlatban ez az előző lépés mellékhatásaként hatékonyan megvalósítható, mivel a komponenseket Kosaraju algoritmusa állítja elő topológiai sorrendben és Tarjan algoritmusa fordított topológiai sorrendben.
  • Minden fordított topológiai sorrendben lévő komponenshez, ha a változói még nem rendelkeznek igazság-hozzárendeléssel, állítsa be az összes literált igaznak. Ez azt is okozza, hogy a komplementer komponensben szereplő összes literál hamisra lesz állítva.

A fordított topológiai sorrend és a ferde szimmetria miatt, ha egy literál igazra van állítva, akkor már minden literál igazra van állítva, amely egy implikációs láncon keresztül elérhető belőle. Szimmetrikusan, ha egy literál x értéke hamis, akkor minden literál, amely implikációs láncon keresztül vezet hozzá, már maga is hamisra van állítva. Ezért az ezzel az eljárással megszerkesztett igazság-hozzárendelés megfelel az adott képletnek, ami egyben kiegészíti az Aspvall et al. által azonosított szükséges és elégséges feltétel helyességének bizonyítását is.[4]

Ahogy Aspvall et al. ábrán látható, egy hasonló eljárás, amely magában foglalja az implikációs gráf erősen összefüggő komponenseinek topológiai rendezését, szintén használható olyan teljesen kvantifikált Boole-képletek kiértékelésére, amelyekben a számszerűsítendő képlet egy 2-CNF képlet.[4]

AlkalmazásokSzerkesztés

Geometriai objektumok konfliktusmentes elhelyezéseSzerkesztés

Számos pontos és közelítő algoritmus az automatikus címkeelhelyezési problémára a 2-kielégíthetőségen alapul. Ez a probléma a szöveges címkék diagram vagy térkép jellemzőire való elhelyezésével kapcsolatos. Az egyes címkék lehetséges helyeinek halmazát jellemzően erősen korlátozza, nem csak maga a térkép (minden címkének a megjelölt tereptárgy közelében kell lennie, és nem takarhat el más elemeket), hanem egymás is: minden két címkének kerülnie kell az átfedést. egymást, mert különben olvashatatlanná válnának. Általánosságban elmondható, hogy olyan címkeelhelyezést találni, amely megfelel ezeknek a megszorításoknak, NP-nehéz probléma. Ha azonban mindegyik jellemzőnek csak két lehetséges helye van a címkéjének (mondjuk a jellemzőtől balra és jobbra nyúlik), akkor a címke elhelyezése megoldható polinomiális időben. Ebben az esetben létrehozhat egy 2-kielégíthetőségi példányt, amelynek minden címkéhez van egy változója, és minden címkepárhoz tartozik egy klóz, amely átfedheti egymást, megakadályozva, hogy átfedő pozíciókat rendeljenek hozzájuk. Ha a címkék mindegyike egybevágó téglalap, akkor a megfelelő 2-kielégíthetőségi példányról kimutatható, hogy csak lineárisan sok megszorítást tartalmaz, ami közel lineáris időbeli algoritmusokhoz vezet a címkézés megtalálásához.[8] Poon, Zhu & Chin (1998) egy térképcímkézési problémát ír le, amelyben minden címke egy téglalap, amely az általa címkézett vonalszakaszhoz képest három pozíció valamelyikébe helyezhető: lehet, hogy a szegmens az egyik oldala, vagy lehet a szegmens közepén. Ezt a három pozíciót két bináris változó segítségével reprezentálják oly módon, hogy az érvényes címkézés meglétének tesztelése ismét 2-es kielégítés problémává válik.[9]

Formann és Wagner (1991) a 2-kielégíthetőséget egy közelítő algoritmus részeként használja arra a problémára, hogy egy adott ponthalmazhoz a lehető legnagyobb méretű négyzetes címkéket találja meg, azzal a megkötéssel, hogy minden címkének azon a ponton van az egyik sarka, felcímkézi. Egy adott méretű címkézés megtalálásához kiiktatják azokat a négyzeteket, amelyek megduplázva átfednének egy másik pontot, és kiiktatják azokat a pontokat, amelyeket úgy lehet címkézni, hogy azok ne fedhessenek át egy másik pont címkéjével. Ezek azt mutatják, hogy ezek az eliminációs szabályok azt eredményezik, hogy a fennmaradó pontoknak csak két lehetséges címkeelhelyezésük van pontonként, ami lehetővé teszi, hogy egy érvényes címkeelhelyezést (ha létezik) találjunk megoldásként a 2-kielégíthetőségi példányra. Megkeresve a legnagyobb címkeméretet, amely egy megoldható 2-kielégíthetőségi példányhoz vezet, olyan érvényes címkeelhelyezést találnak, amelynek címkéi legalább feleakkorák, mint az optimális megoldás. Azaz a közelítő algoritmus közelítési aránya legfeljebb kettő.[8][10] Hasonlóképpen, ha minden címke téglalap alakú, és úgy kell elhelyezni, hogy a címkézett pont valahol az alsó széle mentén legyen, akkor a 2-kielégíthetőséget használva keressük meg azt a legnagyobb címkeméretet, amelyre létezik olyan megoldás, amelyben minden címkén a pont az alsó sarokban legfeljebb kettős közelítési arányhoz vezet.[11]

A 2-kielégíthetőség hasonló alkalmazásait más geometriai elhelyezési problémákra is végezték. A gráfrajznál, ha a csúcsok helyei rögzítettek, és minden élt körívként kell megrajzolni két lehetséges hely egyikével (például ívdiagramként ), akkor az egyes élekhez használt ív kiválasztásának problémája. Keresztezések elkerülése egy 2-kielégíthetőségi probléma, minden élhez változó, és minden egyes elhelyezéspárhoz egy megkötés, amely keresztezéshez vezetne. Ebben az esetben azonban felgyorsítható a megoldás egy olyan algoritmushoz képest, amely létrehozza, majd megkeresi az implikációs gráf explicit reprezentációját, ha implicit módon keresi a gráfot.[12] A VLSI integrált áramköri tervezésben, ha a modulok gyűjteményét olyan vezetékekkel kell összekötni, amelyek mindegyike legfeljebb egyszer hajlik meg, akkor ismét két lehetséges útvonal van a vezetékek számára, és a két útvonal közül melyiket kell használni. egy olyan módszer, hogy az összes vezetéket az áramkör egyetlen rétegében lehessen vezetni, megoldható 2-kielégíthetőségi példányként.[13]

Boros et al. (1999) egy másik VLSI tervezési problémát fontolgat: azt a kérdést, hogy az egyes modulokat tükrözni kell-e egy áramköri tervben vagy sem. Ez a tükörfordítás változatlanul hagyja a modul működését, de megváltoztatja azon pontok sorrendjét, ahol a modul bemeneti és kimeneti jelei csatlakoznak hozzá, esetleg megváltoztatja azt, hogy a modul mennyire illeszkedik a kialakítás többi részéhez. Boros et al. Tekintsük a probléma egyszerűsített változatát, amelyben a modulokat már egyetlen lineáris csatorna mentén helyezték el, amelyben a modulok közötti vezetékeket el kell vezetni, és van egy fix korlát a csatorna sűrűségére (a jelek maximális száma, át kell haladnia a csatorna bármely keresztmetszetén). Megfigyelték, hogy a probléma ezen változata megoldható egy 2-kielégíthetőségi példányként, amelyben a megszorítások a csatornán keresztül közvetlenül egymáshoz képest elhelyezkedő modulpárok orientációjára vonatkoznak. Ennek eredményeként az optimális sűrűség is hatékonyan kiszámítható egy bináris keresés végrehajtásával, amelyben minden lépés egy 2-kielégíthetőségi példány megoldását foglalja magában.

AdatcsoportosításSzerkesztés

Egy metrikus térben lévő adatpontok halmazának két klaszterbe csoportosításának egyik módja az, hogy a klasztereket úgy választjuk ki, hogy minimalizáljuk a klaszterek átmérőjének összegét, ahol bármelyik klaszter átmérője a legnagyobb távolság bármely klaszter között. két pontja. Ez előnyösebb a maximális fürtméret minimalizálása érdekében, ami ahhoz vezethet, hogy nagyon hasonló pontokat rendelnek hozzá a különböző fürtökhöz. Ha ismert a két klaszter célátmérője, akkor egy 2-kielégíthetőségi példány megoldásával találhatunk egy klaszterezést, amely eléri ezeket a célokat. A példánynak pontonként egy változója van, jelezve, hogy az adott pont az első vagy a második fürthöz tartozik-e. Amikor bármely két pont túl messze van egymástól ahhoz, hogy mindkettő ugyanahhoz a fürthöz tartozzon, a példányhoz egy záradék kerül hozzáadásra, amely megakadályozza ezt a hozzárendelést.

Ugyanez a módszer szubrutinként is használható, ha az egyes klaszter átmérők ismeretlenek. Annak tesztelésére, hogy az átmérők adott összege elérhető-e az egyes klaszterátmérők ismerete nélkül, kipróbálható az összes olyan maximális célátmérőpár, amely legfeljebb a megadott összeget adja, minden átmérőpárt 2-kielégíthetőségi példányként ábrázolva, és egy 2-kielégíthetőségi algoritmus annak meghatározására, hogy ez a pár megvalósítható-e klaszterezéssel. Az átmérők optimális összegének megtalálásához bináris keresést végezhetünk, amelyben minden lépés egy ilyen típusú megvalósíthatósági teszt. Ugyanez a megközelítés működik olyan klaszterezések megtalálásában is, amelyek a klaszter átmérőinek összegén kívül más kombinációkat is optimalizálnak, és tetszőleges eltérési számokat használnak (a metrikus térben lévő távolságok helyett) a klaszter méretének mérésére.[14] Ennek az algoritmusnak az időkorlátját az az idő dominálja, ameddig a 2-kielégíthetőségi esetből álló sorozat megoldható, amelyek szorosan kapcsolódnak egymáshoz, és Ramnath (2004) megmutatja, hogyan lehet ezeket a kapcsolódó példányokat gyorsabban megoldani, mintha mindegyiktől függetlenül oldanák meg őket. másik, ami az O(n3) teljes időkorlátjához vezet az átmérők összegének klaszterezési problémájához.[15]

ÜtemezésSzerkesztés

Még Itai és Shamir (1976) is egy olyan osztálytermi ütemezési modellt fontolgat, amelyben n tanárból álló csoportot kell beütemezni, hogy mind a tanulók m kohorszát tanítsák. A heti óraszám az adott tanár   kohorsszal költ   bejegyzés írja le   egy mátrixból   bemenetként adják meg a problémát, és minden tanárnak van egy órakészlete is, amelyen belül beosztható. Amint azt mutatják, a probléma NP-teljes, akkor is, ha minden tanárnak legfeljebb három szabad órája van, de megoldható a 2-kielégíthetőség példájaként, ha minden tanárnak csak két szabad órája van. (Azok a tanárok, akiknek csak egyetlen órája van, könnyen kiküszöbölhetők a problémából.) Ebben a feladatban minden változó   egy órának felel meg az a tanár   kohorszban kell költeni  ,a változóhoz való hozzárendelés meghatározza, hogy az adott óra az első vagy a második a tanár rendelkezésre álló órái közül, és van egy 2-teljesíthetőségi záradék, amely megakadályozza a kétféle konfliktust: két kohorsz hozzárendelve egy tanárhoz egyidejűleg másik, vagy egy kohorsz, amely egyszerre két tanárhoz van hozzárendelve.[5]

Miyashiro és Matsui (2005) a 2-kielégíthetőséget alkalmazza egy olyan sportütemezési problémára, amelyben már kiválasztották a körmérkőzéses torna párosításait, és a meccseket a csapatok stadionjaihoz kell hozzárendelni. Ebben a problémában kívánatos a hazai és idegenbeli meccsek lehetőség szerinti felváltása, elkerülve az olyan "szüneteket", amikor egy csapat egymás után két hazai vagy két idegenbeli meccset játszik egymás után. Legfeljebb két csapat kerülheti el teljesen a szünetet, felváltva hazai és idegenbeli meccseket; Egyetlen másik csapatnak sem lehet ugyanaz a hazai, idegenbeli menetrendje, mint ennek a kettőnek, mert akkor nem tudna játszani azzal a csapattal, amellyel ugyanaz volt. Ezért az optimális ütemtervben két megszakítás nélküli csapat van, és minden más csapat egyetlen szünetet tartalmaz. A töretlen csapatok egyikének kiválasztása után felállíthatunk egy 2-kielégíthetőségi problémát, amelyben minden változó egyetlen csapat hazai idegenbeli beosztását jelenti egyetlen meccsen, és a megszorítások érvényesítik azokat a tulajdonságokat, amelyekkel bármely két csapat konzisztens. kiosztása a meccseikre, hogy minden csapatnak legfeljebb egy szünete legyen a meccs előtt és legfeljebb egy szünete után a szünetet nem játszó csapattal, valamint hogy egyetlen csapatnak sincs két szünete. Ezért annak tesztelése, hogy egy ütemterv megenged-e optimális szünetszámú megoldást, lineáris számú 2-kielégítési feladat megoldásával végezhető el, a megszakítás nélküli csapat minden egyes választásához egyet. Egy hasonló technika lehetővé teszi olyan menetrendek megtalálását is, amelyekben minden csapatnak egyetlen szünete van, és a szünetek számának maximalizálását, nem pedig minimalizálását (a csapatok által megtett teljes futásteljesítmény csökkentése érdekében).[16]

 
Példa egy nonogramrejtvény megoldására

A tomográfia a formák visszanyerésének folyamata a keresztmetszetükből. A diszkrét tomográfiában a probléma gyakran tanulmányozott egyszerűsített változata, a helyreállítandó alakzat egy poliomino (a négyzetek egy részhalmaza a kétdimenziós négyzetrácsban ), és a keresztmetszetek összesített információkat adnak a halmazokról. négyzetek a rács egyes soraiban és oszlopaiban. Például a népszerű nonogramrejtvényekben, más néven paint by numbers vagy griddlers, a meghatározandó négyzetek halmaza egy bináris kép sötét képpontjait jelöli, és a rejtvényfejtőnek adott bemenet megmondja, hogy hány egymást követő blokk. a kép egyes soraiba vagy oszlopaiba beillesztendő sötét pixelek száma, valamint az egyes blokkok hosszúsága. A digitális tomográfia más formáiban még kevesebb információt adnak meg minden sorról vagy oszlopról: csak a négyzetek teljes számát, nem pedig a négyzettömbök számát és hosszát. A probléma ekvivalens változata az, hogy egy adott 0-1 mátrixot vissza kell állítanunk, ha csak a mátrix soraiban és oszlopaiban lévő értékek összegét kell megadni.

Bár léteznek polinomiális idő algoritmusok adott sor- és oszlopösszegekkel rendelkező mátrix megtalálására[17], a megoldás távolról sem lehet egyedi: bármely részmátrix 2 × 2-es identitásmátrix kiegészíthető anélkül, hogy ez befolyásolná a megoldás helyességét. Ezért a kutatók olyan megszorításokat kerestek a rekonstruálandó alakzatban, amelyek segítségével szűkíthető a megoldások tere. Például feltételezhetjük, hogy az alakzat össze van kötve; azonban annak tesztelése, hogy létezik-e csatlakoztatott megoldás, NP-teljes.[18] Egy még kötöttebb, könnyebben megoldható változat az, hogy az alakzat merőlegesen konvex : minden sorban és oszlopban egyetlen összefüggő négyzettömb van. Számos korábbi megoldást Chrobak & Dürr (1999) megmutatta, hogyan lehet hatékonyan rekonstruálni összekapcsolt ortogonálisan konvex alakzatokat 2-kielégítés segítségével.[19] Megoldásuknak az az ötlete, hogy kitalálják a rekonstruálandó alakzat bal és jobb szélső celláit tartalmazó sorok indexeit, majd felállítanak egy 2-kielégítési feladatot, amely megvizsgálja, hogy létezik-e ezekkel a találgatásokkal és a megadottakkal konzisztens alakzat. sorok és oszlopok összegei. Négy 2-kielégíthetőségi változót használnak minden egyes négyzethez, amely az adott alakzat részét képezheti, egyet annak jelzésére, hogy az alakzat négy lehetséges "sarokrégiójához" tartozik-e, és olyan megszorításokat alkalmaznak, amelyek ezeket a régiókat szétválasztják. hogy rendelkezzenek a kívánt alakzatokkal, összefüggő sorokkal és oszlopokkal átfogó alakzatot alakítsanak ki, és rendelkezzenek a kívánt sor- és oszlopösszegekkel. Algoritmusuk O(m3n) időt vesz igénybe, ahol m a bemeneti alakzat két dimenziója közül a kisebb, n pedig a két dimenzió közül a nagyobb. Ugyanezt a módszert később kiterjesztették az ortogonálisan konvex alakzatokra is, amelyek csak átlósan kapcsolhatók össze, ahelyett, hogy ortogonális összeköttetést igényelnének.[20]

A teljes nonogram rejtvények megoldójának egy része, Batenburg and Kosters (2008) a 2-kielégíthetőséget használta több más heurisztikából nyert információk kombinálására. A rejtvény részleges megoldása miatt minden soron vagy oszlopon belül dinamikus programozást használnak annak meghatározására, hogy az adott sor vagy oszlop kényszerei kényszerítik-e a négyzetek valamelyikét fehérre vagy feketére, és hogy ugyanabban a sorban vagy oszlopban bármelyik két négyzet képes-e implikációs relációval kell összekötni. Ezenkívül a nonogramot digitális tomográfiás problémává alakítják át azáltal, hogy minden sorban és oszlopban lecserélik a blokkhossz-szekvenciát annak összegére, és maximális áramlási formulát használnak annak meghatározására, hogy az összes sort és oszlopot kombináló digitális tomográfiás problémának vannak-e olyan négyzetei, amelyek állapot meghatározható vagy implikációs relációval összekapcsolható négyzetpárok. Ha a két heurisztika valamelyike meghatározza az egyik négyzet értékét, akkor az bekerül a parciális megoldásba, és ugyanazokat a számításokat megismételjük. Ha azonban mindkét heurisztika nem tud négyzetet beállítani, akkor a mindkettő által talált implikációkat egy 2-kielégítési problémává egyesítik, és egy 2-kielégíthetőségi megoldó segítségével keresik meg azokat a négyzeteket, amelyek értékét a probléma rögzíti, majd az eljárást ismét megismételve. Ez az eljárás lehet, hogy sikerül megoldást találni, de lehet, hogy nem, de garantáltan polinomiális időben fut le. Batenburg és Kosters arról számolnak be, hogy bár a legtöbb újságrejtvénynek nincs szüksége a teljes teljesítményre, mind ez az eljárás, mind egy erősebb, de lassabb eljárás, amely egyesíti ezt a két kielégíthetőségi megközelítést Even, Itai & Shamir (1976) korlátozott visszalépésével[5] szignifikánsan hatékonyabbak, mint a dinamikus programozás és a 2-teljesíthetőség nélküli áramlási heurisztika, ha bonyolultabb, véletlenszerűen generált nonogramokra alkalmazzák.[21]

Átnevezhető Horn-kielégíthetőségSzerkesztés

A 2-kielégíthetőség mellett a kielégítési problémák másik fő alosztálya, amely polinomiális időben megoldható, a Horn-kielégíthetőség. A kielégítési problémák ezen osztályában a bemenet ismét egy konjunktív normál formájú képlet. Klózonként tetszőlegesen sok literál lehet, de legfeljebb egy pozitív literál. Lewis (1978) talált ennek az osztálynak egy általánosítását, az átnevezhető Horn-kielégíthetőséget, amely még mindig megoldható polinomiális időben egy segéd 2-kielégíthetőségi példány segítségével. Egy képlet átnevezhető Horn -nak, ha lehetséges Horn alakba tenni úgy, hogy néhány változót negációikra cserél. Ennek érdekében Lewis beállít egy 2-kielégíthetőségi példányt egy változóval az átnevezhető Horn-példány minden változójához, ahol a 2-kielégíthetőségi változók jelzik, hogy tagadják-e a megfelelő átnevezhető Horn-változókat. Egy Horn-példány létrehozásához az átnevezhető Horn-példány ugyanabban a záradékában szereplő két változó nem jelenhet meg pozitívan abban a záradékban; ez a változópárra vonatkozó megszorítás egy 2-kielégíthetőségi megszorítás. Azáltal, hogy kielégítő hozzárendelést talál az eredményül kapott 2-kielégíthetőségi példányhoz, Lewis megmutatja, hogyan lehet bármilyen átnevezhető Horn-példányt Horn-példánygá alakítani polinomiális időben.[22] A hosszú tagmondatok több kisebb részre bontásával és a lineáris idejű 2-kielégíthetőségi algoritmus alkalmazásával ez lineáris időre csökkenthető.[23]

Egyéb alkalmazásokSzerkesztés

A 2-kielégíthetőséget alkalmazták a független halmazba particionálható irányítatlan gráfok felismerésének és kis számú teljes kétoldalú részgráfnak,[24] az internet autonóm alrendszerei közötti üzleti kapcsolatokra[25] és a evolúciós fák rekonstrukciós problémákra.[26]

Bonyolultság és kiterjesztésekSzerkesztés

NL-teljességSzerkesztés

Egyszerűen leírható egy nemdeterminisztikus algoritmus annak meghatározására, hogy egy 2-teljesíthetőségű példány nem kielégítő-e, csak logaritmikus mennyiségű írható memóriát használva: egyszerűen válasszon (nem determinisztikusan) egy v változót, és keresse meg (nem determinisztikusan) a v -ből vezető implikációs láncot tagadására, majd vissza a v-be. Ha ilyen láncot találunk, a példány nem teljesíthető. Az Immerman–Szelepcsényi-tétel alapján nemdeterminisztikus logtérben is ellenőrizhető, hogy egy kielégítő 2-kielégíthetőségi példány kielégíthető-e.

A 2-es kielégíthetőség NL-teljes,[27] ami azt jelenti, hogy ez az egyik "legnehezebb" vagy "legkifejezőbb" probléma a logaritmikus térben nemdeterminisztikusan megoldható NL komplexitási osztályban. A teljesség itt azt jelenti, hogy egy determinisztikus Turing-gép, amely csak logaritmikus teret használ, bármely más NL -beli problémát képes átalakítani egy ekvivalens 2-es kielégíthetőségi problémává. Hasonlóan az ismertebb NP komplexitási osztály eredményeihez, ez a transzformáció az Immerman–Szelepcsényi-tétellel együtt lehetővé teszi, hogy bármely NL-beli problémát másodrendű logikai képletként ábrázoljunk egyetlen egzisztenciálisan kvantifikált predikátummal, 2-re korlátozott klózokkal. Az ilyen képleteket SO-Krom néven ismerik.[28] Hasonlóképpen, az implicatív normálalak kifejezhető elsőrendű logikával egy tranzitív lezárás operátor hozzáadásával.[28]

 
A mediángráf, amely a 2-kielégíthetőségi példa összes megoldását reprezentálja, amelynek implikációs gráfja fent látható

A 2-kielégíthetőségű példány összes megoldásának halmaza egy mediángráf szerkezetével rendelkezik, amelyben egy él egy olyan változóhalmaz értékeinek átfordítási műveletének felel meg, amelyek mindegyike egyenlő vagy nem egyenlő egymással. Az élek ily módon követésével bármely megoldástól bármely más megoldásig el lehet jutni. Ezzel szemben bármely mediángráf ábrázolható egy 2-kielégíthetőségi példány megoldásainak halmazaként ilyen módon. Bármely három megoldás mediánját úgy alakítjuk ki, hogy minden változót arra az értékre állítunk, amely a három megoldás többségében fennáll. Ez a medián mindig egy másik megoldást jelent a példányra.[29]

Feder (1994) egy algoritmust ír le egy adott 2-kielégíthetőségi példány összes megoldásának hatékony felsorolására, és számos kapcsolódó probléma megoldására.[30] Léteznek algoritmusok is két kielégítő hozzárendelés megtalálására, amelyeknél a Hamming-távolság egymástól maximális.[31]

Számolja meg a kielégítő feladatokatSzerkesztés

A #2SAT az adott 2-CNF képlethez tartozó kielégítő hozzárendelések számának megszámlálásának problémája. Ez a számlálási probléma #P-teljes,[32] ami azt jelenti, hogy polinomiális időben nem oldható meg, hacsak nem P = NP. Ezenkívül nincs teljesen polinomiális véletlenszerű közelítési séma #2SAT-ra, kivéve, ha NP = RP, és ez még akkor is érvényes, ha a bemenet monoton 2-CNF-képletekre korlátozódik, azaz olyan 2-CNF-képletekre, amelyekben minden literál egy változó pozitív előfordulása.[33]

A leggyorsabb ismert algoritmus a 2SAT képlethez tartozó kielégítő hozzárendelések pontos számának kiszámítására időben fut  .[34] [35] [36]

Véletlenszerű 2-kielégíthetőségi példányokSzerkesztés

Adott n számú változóra és m klózra véletlenszerűen alkothatunk 2-kielégíthetőségi példányt úgy, hogy minden klózt egyenletesen véletlenszerűen választunk ki az összes lehetséges kétváltozós klóz halmazából. Ha m kicsi n -hez képest, egy ilyen példány valószínűleg kielégítő lesz, de m nagyobb értékei kisebb valószínűséggel teljesíthetők. Pontosabban, ha m / n állandó α ≠ 1, akkor a kielégíthetőség valószínűsége egy határhoz hajlik, mivel n a végtelenbe megy: ha α < 1, a határérték egy, míg ha α > 1, a határ nulla. Így a probléma α-nál fázisátalakulást mutat = 1.[37]

Maximum-2-kielégíthetőségSzerkesztés

A maximum-2-kielégíthetőségi feladatban (MAX-2-SAT) a bemenet egy konjunktív normálformájú képlet, amelyben tagmondatonként két literál van, és a feladat annak meghatározása, hogy egy hozzárendeléssel egyidejűleg maximálisan hány tagmondat elégíthető ki. Az általánosabb maximális kielégítési problémához hasonlóan a MAX-2-SAT is NP-nehéz . A bizonyíték a 3SAT-ról való csökkentés.[38]

A MAX-2-SAT egy vágás (vagyis a csúcsok két részhalmazra való felosztása) megtalálásának problémájaként fogalmazva meg maximalizálva azon élek számát, amelyeknek az első részhalmazban egy végpontja van, a másodikban pedig egy végpontja van egy gráfban. Az implikációs gráfhoz kapcsolódóan, és félig határozott programozási módszereket alkalmazva erre a vágási feladatra, polinomiális időben olyan közelítő megoldást találhatunk, amely az optimális klózszám legalább 0,940-szeresét elégíti ki.[39] A kiegyensúlyozott MAX 2-SAT példány a MAX 2-SAT olyan példánya, ahol minden változó egyenlő súllyal jelenik meg pozitívan és negatívan. Ennél a problémánál Austrin a közelítési arányt -ra javította  .[40]

Ha az egyedi játékok sejtése igaz, akkor polinomiális időben lehetetlen közelíteni a MAX 2-SAT-ot, akár kiegyensúlyozott, akár nem, 0,943-nál jobb közelítési állandóval.[41] A gyengébb feltételezés mellett, hogy P ≠ NP, a probléma csak egy 21/22 = 0,95454-nél jobb állandón belül közelíthetetlen.[42]

Különböző szerzők exponenciális, legrosszabb eset időhatárait is megvizsgálták a MAX-2-SAT példányok pontos megoldására.[43]

Súlyozott 2-kielégíthetőségSzerkesztés

A súlyozott 2-es kielégíthetőségi problémában ( W2SAT ) a bemenet egy   -változós 2SAT példány és egy k egész szám, és a probléma annak eldöntése, hogy létezik-e olyan kielégítő hozzárendelés, amelyben pontosan k változó igaz.[44]

A W2SAT-probléma speciális esetként tartalmazza a csúcsfedő- problémát, melynek során k csúcsból álló halmazt találunk, amelyek együtt érintik egy adott irányítatlan gráf minden élét. A csúcslefedési probléma bármely adott példányához létrehozhatunk egy ekvivalens W2SAT-problémát egy változóval a gráf minden csúcsához. A gráf minden uv élét egy uv 2SAT záradék képviselheti, amely csak úgy teljesíthető, ha u vagy v szerepel a megoldás valódi változói között. Ekkor a kapott 2SAT formula kielégítő példányai a csúcsfedő probléma megoldásait kódolják, és akkor és csak akkor van egy kielégítő hozzárendelés k igaz változóval, ha van egy k csúcsú csúcsfedő. Ezért a vertex coverhez hasonlóan a W2SAT is NP-teljes.

Ezenkívül a W2SAT paraméterezett komplexitásban természetes W[1]-teljes problémát jelent,[44] ami azt jelenti, hogy a W2SAT nem követhető fix paraméterekkel, hacsak ez nem vonatkozik a W[1] összes problémájára. Ez azt jelenti, hogy nem valószínű, hogy létezik olyan algoritmus a W2SAT számára, amelynek futási ideje f(knO(1). Még erősebb, hogy a W2SAT nem oldható meg no(k) időben, hacsak az exponenciális idő hipotézis meghiúsul.[45]

Számszerűsített Boole-képletekSzerkesztés

Amellett, hogy megtalálta az első polinomiális idejű algoritmust a 2-es kielégíthetőségre, Krom (1967) megfogalmazta a teljesen számszerűsített Boole-képletek kiértékelésének problémáját is, amelyekben a kvantifikált képlet egy 2-CNF képlet. A 2-kielégíthetőségi probléma ennek a számszerűsített 2-CNF problémának a speciális esete, amelyben minden kvantor egzisztenciális. Krom hatékony döntési eljárást is kidolgozott ezekhez a képletekhez. Aspvall, Plass & Tarjan (1979) megmutatta, hogy ez lineáris időben is megoldható, az erősen összefüggő komponensek és a topológiai rendezés technikájának kiterjesztésével.[2] [4]

Sokértékű logikaSzerkesztés

A 2-es kielégíthetőségi problémát kijelentési sokértékű logikákra is fel lehet kérdezni. Az algoritmusok általában nem lineárisak, és egyes logikák esetében a probléma még NP-teljes is. Lásd:  (2001) felmérésekhez.[46]

JegyzetekSzerkesztés

  1. a b Prestwich, Steven (2009), "2. CNF Encodings", in Biere, Armin; Heule, Marijn & van Maaren, Hans et al., Handbook of Satisfiability, vol. 185, Frontiers in Artificial Intelligence and Applications, IOS Press, pp. 75–98, ISBN 978-1-58603-929-5, doi:10.3233/978-1-58603-929-5-75.
  2. a b c d e f Krom, Melven R. (1967), The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary, vol. 13, pp. 15–20, DOI 10.1002/malq.19670130104.
  3. Russell, Stuart Jonathan & Norvig, Peter (2010), Artificial Intelligence: A Modern Approach, Prentice Hall series in artificial intelligence, Prentice Hall, p. 282, ISBN 978-0-13-604259-4.
  4. a b c d e f g Aspvall, Bengt; Plass, Michael F. & Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4, <http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf>.
  5. a b c d e f g Even, S.; Itai, A. & Shamir, A. (1976), "On the complexity of time table and multi-commodity flow problems", SIAM Journal on Computing 5 (4): 691–703, DOI 10.1137/0205048.
  6. Cook, Stephen A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symp. Theory of Computing (STOC), pp. 151–158, DOI 10.1145/800157.805047.
  7. Tarjan, Robert E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160, DOI 10.1137/0201010.
  8. a b Formann, M. & Wagner, F. (1991), Proc. 7th ACM Symposium on Computational Geometry, pp. 281–288, DOI 10.1145/109648.109680.
  9. Poon, Chung Keung; Zhu, Binhai & Chin, Francis (1998), "A polynomial time solution for labeling a rectilinear map", Information Processing Letters 65 (4): 201–207, DOI 10.1016/S0020-0190(98)00002-7.
  10. Wagner, Frank & Wolff, Alexander (1997), A practical map labeling algorithm, pp. 387–404, DOI 10.1016/S0925-7721(96)00007-7.
  11. Doddi, Srinivas & Marathe, Madhav V. (1997), "Map labeling and its generalizations", Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 148–157, ISBN 9780898713909.
  12. Efrat, Alon; Erten, Cesim & Kobourov, Stephen G. (2007), "Fixed-location circular arc drawing of planar graphs", Journal of Graph Algorithms and Applications 11 (1): 145–164, doi:10.7155/jgaa.00140, <http://jgaa.info/accepted/2007/EfratErtenKobourov2007.11.1.pdf>.
  13. Raghavan, Raghunath; Cohoon, James & Sahni, Sartaj (1986), "Single bend wiring", Journal of Algorithms 7 (2): 232–237, DOI 10.1016/0196-6774(86)90006-4.
  14. Hansen, P. & Jaumard, B. (1987), "Minimum sum of diameters clustering", Journal of Classification 4 (2): 215–226, DOI 10.1007/BF01896987.
  15. Ramnath, Sarnath (2004), "Dynamic digraph connectivity hastens minimum sum-of-diameters clustering", SIAM Journal on Discrete Mathematics 18 (2): 272–286, DOI 10.1137/S0895480102396099.
  16. Miyashiro, Ryuhei & Matsui, Tomomi (2005), "A polynomial-time algorithm to find an equitable home–away assignment", Operations Research Letters 33 (3): 235–241, DOI 10.1016/j.orl.2004.06.004.
  17. Brualdi, R. A. (1980), "Matrices of zeros and ones with fixed row and column sum vectors", Linear Algebra Appl. 33: 159–231, DOI 10.1016/0024-3795(80)90105-6.
  18. Woeginger, G. J. (1996), The reconstruction of polyominoes from their orthogonal projections.
  19. Chrobak, Marek (1999), "Reconstructing hv-convex polyominoes from orthogonal projections", Information Processing Letters 69: 283–289, DOI 10.1016/S0020-0190(99)00025-3.
  20. Kuba, Attila (2002), "Reconstruction of convex 2D discrete sets in polynomial time", Theoretical Computer Science 283: 223–242, DOI 10.1016/S0304-3975(01)00080-9; Brunetti, Sara (2003), "An algorithm reconstructing convex lattice sets", Theoretical Computer Science 304: 35–57, DOI 10.1016/S0304-3975(03)00050-1.
  21. Batenburg, K. Joost & Kosters, Walter A. (2008), Combinatorial Image Analysis, 12th International Workshop, IWCIA 2008, Buffalo, NY, USA, April 7–9, 2008, Proceedings, vol. 4958, pp. 372–383, DOI 10.1007/978-3-540-78275-9_33; Batenburg, K. Joost & Kosters, Walter A. (2009), "Solving Nonograms by combining relaxations", Pattern Recognition 42 (8): 1672–1683, DOI 10.1016/j.patcog.2008.12.003.
  22. Lewis, Harry R. (1978), "Renaming a set of clauses as a Horn set", Journal of the ACM 25 (1): 134–135, DOI 10.1145/322047.322059.
  23. Aspvall, Bengt (1980), "Recognizing disguised NR(1) instances of the satisfiability problem", Journal of Algorithms 1 (1): 97–103, DOI 10.1016/0196-6774(80)90007-3.
  24. Brandstädt, Andreas; Hammer, Peter Ladislaw & Le, Van Bang (2005), "Bisplit graphs", Discrete Mathematics 299 (1–3): 11–32, DOI 10.1016/j.disc.2004.08.046.
  25. Wang, Hao; Xie, Haiyong & Yang, Yang Richard (2005), 13th IEEE Conf. Network Protocols (ICNP), pp. 16–29, DOI 10.1109/ICNP.2005.39.
  26. Eskin, Eleazar; Halperin, Eran & Karp, Richard M. (2003), "Efficient reconstruction of haplotype structure via perfect phylogeny", Journal of Bioinformatics and Computational Biology 1 (1): 1–20, DOI 10.1142/S0219720003000174.
  27. Papadimitriou, Christos H. (1994), Computational Complexity, Addison-Wesley, pp. chapter 4.2, ISBN 978-0-201-53082-7., Thm. 16.3.
  28. a b Cook, Stephen (2004), 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), pp. 398–407, ISBN 978-0-7695-2192-3.
  29. Bandelt, Hans-Jürgen & Chepoi, Victor (2008), "Metric graph theory and geometry: a survey", Surveys on discrete and computational geometry, vol. 453, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 49–86, ISBN 9780821842393, DOI 10.1090/conm/453/08795. Chung, F. R. K. & Graham, R. L. (1989), A dynamic location problem for graphs, vol. 9, pp. 111–132, DOI 10.1007/BF02124674. Feder, T. (1995), Stable Networks and Product Graphs, vol. 555, Memoirs of the American Mathematical Society.
  30. Feder, Tomás (1994), "Network flow and 2-satisfiability", Algorithmica 11 (3): 291–319, DOI 10.1007/BF01240738.
  31. Angelsmark, Ola (2005), Recent Advances in Constraints, vol. 3419, pp. 128–141, DOI 10.1007/11402763_10.
  32. Valiant, Leslie G. (1979), The complexity of enumeration and reliability problems, vol. 8, pp. 410–421, DOI 10.1137/0208032
  33. Welsh, Dominic & Gale, Amy (2001), "The complexity of counting problems", Aspects of complexity: minicourses in algorithmics, complexity and computational algebra: mathematics workshop, Kaikoura, January 7–15, 2000, pp. 115ff, Theorem 57.
  34. Dahllöf, Vilhelm; Jonsson, Peter & Wahlström, Magnus (2005), "Counting models for 2SAT and 3SAT formulae", Theoretical Computer Science 332 (1–3): 265–291, DOI 10.1016/j.tcs.2004.10.037
  35. Fürer, Martin & Kasiviswanathan, Shiva Prasad (2007), Algorithmic Aspects in Information and Management, vol. 4508, pp. 47–57, DOI 10.1007/978-3-540-72870-2_5.
  36. Wahlström, Magnus (2008), International Workshop on Parameterized and Exact Computation, vol. 5018, pp. 202–213, DOI 10.1007/978-3-540-79723-4_19
  37. Bollobás, Béla; Borgs, Christian & Chayes, Jennifer T. et al. (2001), "The scaling window of the 2-SAT transition", Random Structures and Algorithms 18 (3): 201–256, DOI 10.1002/rsa.1006; Chvátal, V. & Reed, B. (1992), Proc. 33rd IEEE Symp. Foundations of Computer Science (FOCS), pp. 620–627, DOI 10.1109/SFCS.1992.267789; Goerdt, A. (1996), "A threshold for unsatisfiability", Journal of Computer and System Sciences 53 (3): 469–486, DOI 10.1006/jcss.1996.0081.
  38. M. R. Garey; D. S. Johnson & L. J. Stockmeyer (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science 1 (3): 237–267, ISSN 0304-3975, DOI 10.1016/0304-3975(76)90059-1; see pp. 4–6
  39. Lewin, Michael & Livnar, Dror (2002), "Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems", Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag, pp. 67–82, ISBN 978-3-540-43676-8
  40. Austrin, Per (2007), "Balanced Max 2-sat Might Not Be the Hardest", Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing (STOC '07), New York, NY, USA: ACM, pp. 189–197, ISBN 978-1-59593-631-8, DOI 10.1145/1250790.1250818.
  41. Khot, Subhash; Kindler, Guy & Mossel, Elchanan et al. (2004), "Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?", FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 146–154, ISBN 978-0-7695-2228-9, DOI 10.1109/FOCS.2004.49
  42. Håstad, Johan (2001), Some optimal inapproximability results, pp. 798–859, DOI 10.1145/502090.502098.
  43. Bansal, N. (1999), Proc. 10th Conf. Algorithms and Computation, ISAAC'99, vol. 1741, pp. 247–258; Gramm, Jens (2003), "Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT", Discrete Applied Mathematics 130 (2): 139–155, DOI 10.1016/S0166-218X(02)00402-X; Kojevnikov, Arist (2006), Proc. 17th ACM-SIAM Symp. Discrete Algorithms, pp. 11–17, DOI 10.1145/1109557.1109559
  44. a b Flum & Grohe (2006), Parameterized Complexity Theory, pp. 69–70, DOI 10.1007/3-540-29953-X
  45. Chen, Jianer & Huang, Xiuzhen (2006), Strong computational lower bounds via parameterized complexity, pp. 1346–1367, DOI 10.1016/j.jcss.2006.04.007
  46. Hähnle, Reiner (2001), Handbook of Philosophical Logic, vol. 2, pp. 297–395, DOI 10.1007/978-94-017-0452-6_5 (see in particular p. 373); Hähnle, Reiner (2003), Beyond two: theory and applications of multiple-valued logic, vol. 114, pp. 211–233, DOI 10.1007/978-3-7908-1769-0_9

FordításSzerkesztés

Ez a szócikk részben vagy egészben a(z) 2-satisfiability című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.