Popisná složitost -Descriptive Complexity
Descriptive Complexity je kniha v oblasti matematické logiky a teorie výpočetní složitosti od Neila Immermana . Jedná se o teorii popisné složitosti , což je oblast, ve které se ukazuje, že expresivita matematických vlastností pomocí různých typů logiky je ekvivalentní s jejich vyčíslitelností v různých typech výpočetních modelů vázaných na zdroje. To bylo vydáno v roce 1999 Springer-Verlag v jejich knižní sérii Graduate Texts in Computer Science.
Témata
Kniha má 15 kapitol, zhruba seskupených do pěti kapitol o logice prvního řádu , tří o logice druhého řádu a sedmi samostatných kapitol o pokročilých tématech.
První dvě kapitoly poskytují základní materiál v logice prvního řádu (včetně aritmetiky prvního řádu , predikátu BIT a pojmu dotazu prvního řádu) a teorie složitosti (včetně formálních jazyků , tříd složitosti vázaných na zdroje a úplných problémů ). Kapitola třetí začíná spojení mezi logikou a složitostí, s důkazem, že jazyky rozpoznatelné prvním řádem lze rozpoznat v logaritmickém prostoru , a konstrukcí úplných jazyků pro logaritmický prostor, nedeterministický logaritmický prostor a polynomiální čas . Čtvrtá kapitola se týká indukčních definic, operátorů s pevným bodem a charakterizace polynomiálního času z hlediska logiky prvního řádu s operátorem s nejméně pevným bodem. Část knihy o tématech prvního řádu končí kapitolou o logických charakteristikách mezí prostředků pro paralelní stroje s náhodným přístupem a složitosti obvodů .
Kapitola šestá představuje hry Ehrenfeucht – Fraïssé , klíčový nástroj k prokázání logické nevyslovitelnosti, a kapitola sedm představuje logiku druhého řádu. Zahrnuje Faginovu větu charakterizující nedeterministický polynomiální čas z hlediska existenciální logiky druhého řádu, Cook – Levinovu větu o existenci NP-úplných problémů a rozšíření těchto výsledků do polynomiální hierarchie . Kapitola osm používá hry k prokázání nevýslovnosti určitých jazyků v logice druhého řádu.
Kapitola devátá se týká doplňování jazyků a operátoru tranzitivního uzavření , včetně Immerman – Szelepcsényiho věty, že nedeterministický logaritmický prostor je uzavřen doplňováním. Kapitola deset poskytuje úplné problémy a logickou charakterizaci polynomiálního prostoru druhého řádu . Kapitola jedenáctá pojednává o uniformitě složitosti obvodů (rozdíl mezi existencí obvodů pro řešení problému a jejich algoritmickou konstruovatelností) a kapitola dvanáct o úloze řazení a počítání predikátů v logických charakterizacích tříd složitosti. Třináctá kapitola používá přepínací lemma pro dolní hranice a čtrnáctá kapitola se týká aplikací pro databáze a kontrolu modelů . Závěrečná kapitola nastiňuje témata, která v této oblasti stále potřebují výzkum.
Publikum a příjem
Kniha je primárně zaměřena na odkaz výzkumným pracovníkům v této oblasti, ale může být také použita jako základ postgraduálního kurzu a je vybavena cvičeními pro tento účel. I když tvrdí, že je samostatný, recenzent W. Klonowski píše, že jeho čtenáři již musí rozumět klasické složitosti i základům matematické logiky.
Recenzent Anuj Dawar píše, že některé z raných příslibů popisné složitosti byly tlumeny její neschopností přinést logické nástroje, které by řešily hlavní problémy teorie složitosti, a nutností přidávat do logických jazyků doplňky podobné výpočtům, aby bylo možné použít je charakterizovat výpočet. Nicméně, píše, kniha je užitečná jako způsob, jak seznámit vědce s touto oblastí výzkumu, a jako méně prozkoumaný způsob přiblížení výpočetní složitosti.
