A Satisfiability és kapcsolódó problémák alsó határainak áttekintése

Eredeti címe:

A Survey of Lower Bounds for Satisfiability and Related Problems

Könyv tartalma:

Az NP-teljesség vitathatatlanul az informatika legelterjedtebb fogalma, mivel a tudomány és a mérnöki tudományok minden ágából több ezer fontos probléma számítási bonyolultságát ragadja meg.

A P versus NP kérdés azt firtatja, hogy ezek a problémák megoldhatók-e polinomiális idő alatt. A nemleges választ már régóta széles körben feltételezik, de egészen a közelmúltig nem ismertek konkrét alsó korlátokat a számítás általános modelljeire.

A kielégíthetőség annak eldöntése, hogy egy adott Boole-formulának van-e legalább egy kielégítő hozzárendelése. Ez az első probléma, amelyről kimutatták, hogy NP-teljes, és valószínűleg ez a leggyakrabban vizsgált NP-teljes probléma, mind elméleti tulajdonságai, mind gyakorlati alkalmazásai miatt. A Survey of Lower Bounds for Satisfiability and Related Problems (A kielégíthetőség és a kapcsolódó problémák alsó határainak áttekintése) a kielégíthetőség és a szorosan kapcsolódó problémák idő- és térbeli komplexitásának nemrégiben felfedezett alsó határait tekinti át.

Áttekinti az általános determinisztikus, véletlenszerű és kvantumszámítási modellekre vonatkozó legfrissebb eredményeket, és egységes keretben mutatja be a mögöttes érveket. Az A Survey of Lower Bounds for Satisfiability and Related Problems felbecsülhetetlen értékű referencia a komplexitáselmélet területén kutatást végző vagy azt tervező professzorok és hallgatók számára.