Grafilogika és társai - unique megoldások, mitől nehéz egy input?

Az megvan, hogy a Grafilogika NP-teljes? :-)

Csakhogy, az újságokban látható rejtvények egyvalamiben nagyon különböznek az eddig tárgyaltakról: pontosan egy megoldásuk van. Ez a grafilogika esetében momentán egy szép kép is.

Ha pedig a célunk az, hogy egy rejtvénytípusban kiváltsuk a (költséges) szakértőt, pályatervező mestert, akármit egy (eladható :P ) programmal, akkor a feladat: feladványok generálása, melyeknek pontosan egy megoldásuk van, és ezeknek a nehézségét is valamilyen módon mérni kell. Az se hátrány, ha gyorsan generálunk. Ugyanakkor biztosítanunk kell, hogy tényleg egyetlen megoldás legyen - ha ezt egy solverrel ellenőrizzük le, akkor a generált feladvány annyira nem lesz nehéz, hiszen egy solver (a mienk) meg fogja tudni oldani. Vagy, eleve a generálási módszer kell olyan legyen, ami garantálja a unique megoldhatóságot.

Létezik persze olyan SAT-variáns (called UNIQUE-SAT), ami ezt akarja elkapni: az input CNF-re a specifikáció annyi, hogy igen-t kell mondani, ha pontosan egy kielégítő értékelése van, nemet akkor, ha kielégíthetetlen, egyébként pedig bármi elfogadható. (Az ilyen típusú problémákat promise problémának is nevezik: "megígérem, hogy 0 vagy 1 megoldás van, mondd meg, melyik az igazság" -- ha az ígéretet "megszegi" az input, akkor bármit válaszolhatunk.)

Itt a "hagyományos" visszavezetés-fogalom nem alkalmazható: lehet, hogy a visszavezetésünk (mint pl. amit láttunk a SAT-ból 3SAT-ba is) egy olyan példányból, melynek pontosan egy megoldása van, egy olyat készít, melynek több is. (De lehet olyan visszavezetést is készíteni, mely a kielégítő kiértékelések számát is megtartja, az ilyet parsimonious vagy magyarul talán "takarékos" visszavezetésnek hívják).

Mármost a Valiant-Vazirani tétel azt mondja, hogy ha a UNIQUE-SAT-ra van polinomidejű algoritmus, akkor NP = RP. Ez annyit tesz, hogy az összes NP-beli problémára van hatékony randomizált algoritmus, ezt is úgy hisszük, hogy nem igaz. Akárhogy is, jó okunk van azt hinni, hogy

az NP-teljes problémák akkor is nehezek maradnak, ha unique a megoldásuk.

Legalábbis jó részük, ha már egyszer a SAT-ra igaz ez.

A másik lényeges kérdés megint az, hogy még ha a problémára tudjuk is, hogy NP-nehéz, az csak azt jelenti, hogy minden eddig ismert algoritmusra vannak olyan inputok, amik az adott algoritmust bekergetik egy exponenciális lassú futásba. De ez csak annyit mond, hogy "ez az input ennek az algoritmusnak nehéz". Viszont egy-egy jól összeállított rejtvényről lehet az a vélekedés, hogy uniforman nehéz: valamilyen értelemben minden generikus algoritmus számára nehéz. De mit jelent ez? A másik kérdés tehát az, hogy

mitől nehéz egy adott példány 

generikus értelemben, tehát mikor tudjuk (ha tudjuk) azt mondani egyáltalán inputok egy családjára, hogy ezek "nehezek"?

Maradva az elkezdett aknakeresős témánál, egy remek feladat lehet (ami engem is nagyon érdekel) a következő: egy generátor fejlesztése, mely olyan (aknakereső, grafilogika, eternity, akármi) feladványokat állít elő lehetőleg gyorsan, melyekre garantált, hogy pontosan egy megoldásuk van, és egy olyan "metrikát" előállítani, mellyel az előállított példányok "nehézsége" mérhető. Hogy egy ilyen metrika mennyire lehet objektív, az szakirodalmazás kérdése :-) és a választott problémától függ, természetesen. Még jobb lenne, ha a generátor konzisztensen képes lenne nehéz példányokat generálni.

A feladat eléggé beleharap az automatikus tartalomgenerálás területébe, és ebben a köntösben ipari szemszögből elsősorban persze a "random" pályás játékfejlesztés vonalon lehet profitálni belőle.