Beskrivande komplexitet
Descriptive Complexity är en bok i matematisk logik och beräkningskomplexitetsteori av Neil Immerman . Det handlar om deskriptiv komplexitetsteori , ett område där uttryckbarheten av matematiska egenskaper med hjälp av olika typer av logik visar sig vara likvärdig med deras beräkningsbarhet i olika typer av resursbundna beräkningsmodeller. Den publicerades 1999 av Springer-Verlag i deras bokserie Graduate Texts in Computer Science.
Ämnen
Boken har 15 kapitel, grovt grupperade i fem kapitel om första ordningens logik , tre om andra ordningens logik och sju oberoende kapitel om avancerade ämnen.
De två första kapitlen ger bakgrundsmaterial i första ordningens logik (inklusive första ordningens aritmetik , BIT-predikatet och begreppet en första ordningens fråga) och komplexitetsteori (inklusive formella språk , resursbundna komplexitetsklasser och kompletta problem ). Kapitel tre börjar kopplingen mellan logik och komplexitet, med ett bevis på att de första ordningens igenkännbara språken kan kännas igen i logaritmiskt utrymme , och konstruktionen av kompletta språk för logaritmiskt utrymme, icke-deterministiskt logaritmiskt utrymme och polynomtid . Det fjärde kapitlet handlar om induktiva definitioner, fixpunktsoperatorer och karakterisering av polynomtid i termer av första ordningens logik med den minsta fixpunktsoperatorn. Den del av boken om första ordningens ämnen avslutas med ett kapitel om logiska karakteriseringar av resursgränser för parallella slumpmässiga maskiner och kretskomplexitet .
Kapitel sex introducerar Ehrenfeucht–Fraïssé-spel , ett nyckelverktyg för att bevisa logisk outsägbarhet, och kapitel sju introducerar andra ordningens logik. Den inkluderar Fagins sats som karakteriserar icke-deterministisk polynomtid i termer av existentiell andra ordningens logik, Cook–Levins sats om förekomsten av NP-fullständiga problem och utökningar av dessa resultat till polynomhierarkin . Kapitel åtta använder spel för att bevisa att vissa språk inte kan uttryckas i andra ordningens logik.
Kapitel nio handlar om komplementering av språk och den transitiva stängningsoperatorn , inklusive Immerman–Szelepcsényi-satsen att icke-deterministiskt logaritmiskt rum stängs under komplementering. Kapitel tio ger kompletta problem och en andra ordningens logisk karakterisering av polynomrymden . Kapitel elva handlar om enhetlighet i kretskomplexitet (skillnaden mellan förekomsten av kretsar för att lösa ett problem och deras algoritmiska konstruktionsbarhet), och kapitel tolv handlar om rollen av ordning och räkning av predikat i logiska karakteriseringar av komplexitetsklasser. Kapitel tretton använder växlingslemmat för nedre gränser, och kapitel fjorton handlar om applikationer till databaser och modellkontroll . Ett sista kapitel beskriver ämnen som fortfarande behöver forskning inom detta område.
Publik och mottagning
Boken är främst avsedd som en referens till forskare inom detta område, men den kan också användas som grund för en forskarutbildning och är utrustad med övningar för detta ändamål. Även om den påstår sig vara fristående, skriver recensenten W. Klonowski att dess läsare redan måste förstå både klassisk komplexitet och grunderna i matematisk logik.
Recensenten Anuj Dawar skriver att en del av det tidiga löftet om beskrivande komplexitet har dämpats av dess oförmåga att ta med logiska verktyg att påverka kärnproblemen inom komplexitetsteorin, och av behovet av att lägga till beräkningsliknande tillägg till logiska språk för att kunna använda dem för att karakterisera beräkningar. Ändå, skriver han, är boken användbar som ett sätt att introducera forskare till denna forskningslinje, och för ett mindre undersökt sätt att närma sig beräkningskomplexitet.