Complexitate descriptivă -Descriptive Complexity
Complexitatea descriptivă este o carte în logica matematică și teoria complexității computaționale de Neil Immerman . Se referă la teoria complexității descriptive , un domeniu în care expresia proprietăților matematice care utilizează diferite tipuri de logică se arată echivalentă cu computabilitatea lor în diferite tipuri de modele de calcul limitate de resurse. A fost publicat în 1999 de Springer-Verlag în seria lor de cărți Graduate Texts in Computer Science.
Subiecte
Cartea are 15 capitole, grupate aproximativ în cinci capitole despre logica de prim ordin , trei pe logica de ordinul doi și șapte capitole independente pe subiecte avansate.
Primele două capitole furnizează materiale de fond în logica de prim ordin (incluzând aritmetica de prim ordin , predicatul BIT și noțiunea de interogare de prim ordin) și teoria complexității (incluzând limbaje formale , clase de complexitate limitate de resurse și probleme complete ). Capitolul trei începe legătura dintre logică și complexitate, cu o dovadă că limbajele de prim ordin pot fi recunoscute în spațiul logaritmic și construcția de limbi complete pentru spațiul logaritmic , spațiul logaritmic nondeterminist și timpul polinomial . Al patrulea capitol se referă la definiții inductive, operatori cu punct fix și caracterizarea timpului polinomial în termeni de logică de prim ordin cu operatorul cu punct fix. Partea cărții pe subiecte de prim ordin se încheie cu un capitol despre caracterizarea logică a limitelor resurselor pentru mașinile paralele cu acces aleatoriu și complexitatea circuitului .
Capitolul șase introduce jocurile Ehrenfeucht – Fraïssé , un instrument cheie pentru dovedirea inexpresibilității logice, iar capitolul șapte introduce logica de ordinul doi. Include teorema lui Fagin care caracterizează timpul polinomial nondeterminist în termeni de logică existențială de ordinul doi, teorema Cook-Levin privind existența problemelor complete NP și extensii ale acestor rezultate la ierarhia polinomială . Capitolul opt folosește jocuri pentru a demonstra inexpresibilitatea anumitor limbi în logica de ordinul doi.
Capitolul nouă se referă la completarea limbilor și a operatorului de închidere tranzitorie , inclusiv teorema Immerman-Szelepcsényi conform căreia spațiul logaritmic neterministic este închis în completare. Capitolul zece oferă probleme complete și o caracterizare logică de ordinul doi al spațiului polinomial . Capitolul unsprezece se referă la uniformitate în complexitatea circuitului (distincția dintre existența circuitelor de rezolvare a unei probleme și constructivitatea algoritmică a acestora), iar capitolul 12 se referă la rolul de a ordona și de a număra predicatele în caracterizarea logică a claselor de complexitate. Capitolul treisprezece folosește lama de comutare pentru limitele inferioare, iar capitolul paisprezece se referă la aplicații pentru bazele de date și verificarea modelelor . Un capitol final prezintă subiecte care încă mai au nevoie de cercetări în acest domeniu.
Audiență și recepție
Cartea este destinată în principal ca referință la cercetătorii din acest domeniu, dar ar putea fi folosită și ca bază a unui curs de absolvire și este dotată cu exerciții în acest scop. Deși susține că este de sine stătător, recenzorul W. Klonowski scrie că cititorii săi trebuie să înțeleagă deja atât complexitatea clasică, cât și elementele de bază ale logicii matematice.
Recenzorul Anuj Dawar scrie că o parte din promisiunea timpurie a complexității descriptive a fost diminuată de incapacitatea sa de a aduce instrumente logice care să suporte problemele de bază ale teoriei complexității și de nevoia de a adăuga completări asemănătoare calculului în limbajele logice pentru a putea fi utilizate ei pentru a caracteriza calculul. Cu toate acestea, scrie el, cartea este utilă ca o modalitate de introducere a cercetătorilor în această linie de cercetare și pentru un mod mai puțin explorat de abordare a complexității computaționale.
