Description
ELTE Analízis tanszék szemináruma
Absztrakt:
Legyen $\mathcal{D}$ véges relációstruktúra (például gráf). A $\mathcal{D}$-hez tartozó CSP (Constraint Satisfaction Problem) alatt a következő problémát értjük: döntsük el egy adott $\mathcal{X}$ véges struktúráról, hogy van-e homomorfizmusa $\mathcal{D}$-be. A számítástudományban az elmúlt évtized egyik komoly áttörése Bulatov és Zhuk tétele: minden CSP vagy polinomiális vagy NP-teljes. Van egy konkret $(\star)$ tulajdonság, amelyet ha teljesít $\mathcal{D}$, akkor a hozzá tartozó CSP NP-teljes, egyébként pedig polinomiális.
Jelöljük a következő kompaktsági tétel-típusú állítást $K_\mathcal{D}$-vel: ha egy struktúra minden véges részének van homomorfizmusa $\mathcal{D}$-be, akkor az egész struktúrának is van.
Tétel: Egy $\mathcal{D}$ véges relációstruktúrára pontosan akkor teljesül a (\star) tulajdonság, ha a $K_\mathcal{D}$ állítás ekvivalens az elsőrendű logika kompaktsági tételével.
Szemléletesen: A véges (algoritmikus) világban egy CSP pontosan akkor nehéz (NP-teljes), ha a végtelen világban a hozzá tartozó kompaktsági tételhez ''sok kiválasztási axióma kell'' (a kiválasztási axióma gyengítései közül egy viszonylag erőssel ekvivalens).