Beskrivende kompleksitet -Descriptive Complexity
Beskrivende kompleksitet er en bog i matematisk logik og beregningskompleksitetsteori af Neil Immerman . Det drejer sig om beskrivende kompleksitetsteori , et område, hvor det er vist, at matematiske egenskabers ekspressibilitet ved hjælp af forskellige typer logik svarer til deres beregbarhed i forskellige typer af ressourcebundne beregningsmodeller. Det blev udgivet i 1999 af Springer-Verlag i deres bogserie Graduate Texts in Computer Science.
Emner
Bogen har 15 kapitler, groft grupperet i fem kapitler om førsteordens logik , tre om andenordens logik og syv uafhængige kapitler om avancerede emner.
De to første kapitler leverer baggrundsmateriale i første ordens logik (inklusive førsteordens aritmetik , BIT-predikatet og begrebet en første ordens forespørgsel) og kompleksitetsteori (herunder formelle sprog , ressourcebundne kompleksitetsklasser og komplette problemer) ). Kapitel tre begynder forbindelsen mellem logik og kompleksitet med et bevis på, at de første orden-genkendelige sprog kan genkendes i logaritmisk rum , og konstruktionen af komplette sprog til logaritmisk rum, nondeterministisk logaritmisk rum og polynomisk tid . Det fjerde kapitel vedrører induktive definitioner, fastpunktsoperatorer og karakterisering af polynomisk tid med hensyn til førsteordens logik med den mindst fastpunktsoperatør. Bogenes del om første ordens emner ender med et kapitel om logiske karakteriseringer af ressourcegrænser for parallelle tilfældige adgangsmaskiner og kredsløbskompleksitet .
Kapitel seks introducerer Ehrenfeucht – Fraïssé-spil , et vigtigt værktøj til at bevise logisk uudtrykkelighed, og kapitel syv introducerer andenordens logik. Det inkluderer Fagins teorem, der karakteriserer nondeterministisk polynomisk tid med hensyn til eksistentiel andenordens logik, Cook – Levin-sætningen om eksistensen af NP-komplette problemer og udvidelser af disse resultater til det polynomiske hierarki . Kapitel otte bruger spil til at bevise, at visse sprog er uudtrykkelige i andenordens logik.
Kapitel ni vedrører komplementering af sprog og den transitive lukningsoperatør , herunder sætningen Immerman – Szelepcsényi, at nondeterministisk logaritmisk rum lukkes under komplementering. Kapitel ti giver komplette problemer og en anden orden logisk karakterisering af polynomial plads . Kapitel elleve vedrører ensartethed i kredsløbskompleksitet (sondringen mellem eksistensen af kredsløb til løsning af et problem og deres algoritmiske konstruktivitet), og kapitel tolv vedrører rollen som bestilling og tælling af predikater i logiske karakteriseringer af kompleksitetsklasser. Kapitel tretten bruger skiftelemmaet til lavere grænser, og kapitel fjorten vedrører applikationer til databaser og modelkontrol . Et sidste kapitel skitserer emner, der stadig er behov for forskning på dette område.
Målgruppe og modtagelse
Bogen er primært rettet som en henvisning til forskere på dette område, men den kan også bruges som grundlag for et kandidatuddannelse og er udstyret med øvelser til dette formål. Selvom den hævder at være selvstændig, skriver anmelderen W. Klonowski, at dens læsere allerede har brug for at forstå både klassisk kompleksitet og det grundlæggende i matematisk logik.
Anmelder Anuj Dawar skriver, at noget af det tidlige løfte om beskrivende kompleksitet er blevet dæmpet af dets manglende evne til at bringe logiske værktøjer til at bære kerneproblemerne i kompleksitetsteorien og af behovet for at tilføje beregningslignende tilføjelser til logiske sprog for at kunne bruge dem til at karakterisere beregning. Ikke desto mindre, skriver han, er bogen nyttig som en måde at introducere forskere til denne forskningslinje og til en mindre stærkt undersøgt måde at nærme sig beregningsmæssig kompleksitet.
