Prehľad dolných hraníc pre splniteľnosť a súvisiace problémy

Pôvodný názov:

A Survey of Lower Bounds for Satisfiability and Related Problems

Obsah knihy:

NP-úplnosť je pravdepodobne najrozšírenejší pojem z informatiky, pretože zachytáva výpočtovú zložitosť tisícov dôležitých problémov zo všetkých oblastí vedy a techniky.

Otázka P verzus NP sa pýta, či sa tieto problémy dajú vyriešiť v polynomiálnom čase. Záporná odpoveď sa už dlho všeobecne predpokladá, ale až donedávna neboli známe žiadne konkrétne dolné hranice na všeobecných modeloch výpočtov.

Uspokojivosť je problém rozhodovania, či daná logická formula má aspoň jedno vyhovujúce priradenie. Je to prvý problém, o ktorom sa ukázalo, že je NP-úplný, a je pravdepodobne najčastejšie študovaným NP-úplným problémom, a to tak pre jeho teoretické vlastnosti, ako aj pre jeho aplikácie v praxi. Prehľad dolných hraníc pre splniteľnosť a súvisiace problémy sa zaoberá nedávno objavenými dolnými hranicami časovej a priestorovej zložitosti splniteľnosti a úzko súvisiacich problémov.

Obsahuje prehľad najnovších výsledkov o všeobecných deterministických, náhodných a kvantových modeloch výpočtov a predstavuje základné argumenty v jednotnom rámci. A Survey of Lower Bounds for Satisfiability and Related Problems je neoceniteľnou príručkou pre profesorov a študentov, ktorí sa venujú výskumu v oblasti teórie zložitosti alebo ho plánujú.