Theory of Computational Complexity

Evoluția teoriei complexității computaționale a trecut, în ultimele decenii, de la o disciplină pur teoretică la un pilon fundamental care dictează limitele practice ale algoritmilor moderni. Theory of Computational Complexity reflectă această maturizare a domeniului prin trecerea de la aspectele calitative ale calculabilității la analize cantitative riguroase ale resurselor necesare procesării informației. Remarcăm în această a doua ediție revizuită un efort considerabil de actualizare a principiilor fundamentale, adaptate progreselor recente din cercetare. Subliniem introducerea unei dovezi combinatoriale noi pentru teorema PCP (Probabilistically Checkable Proofs), utilizând conceptul grafurilor expander, o arie de studiu vitală în informatica teoretică actuală. Structura volumului este echilibrată, acoperind sistematic modelele computaționale, complexitatea circuitelor și pe cea probabilistică, oferind în același timp perspective noi asupra teoriei NP-completitudinii. Cititorii familiarizați cu Computability and Complexity Theory de Steven Homer vor aprecia aici tranziția mult mai detaliată către complexitatea structurală și accentul pus pe instrumentele matematice avansate. Credem că rigoarea stilistică a autorilor Ding-Zhu Du și Ker-I Ko este vizibilă și prin prisma lucrărilor lor anterioare, precum Handbook of Combinatorial Optimization sau Complexity and Approximation. Dacă în volumele precedente se concentrau pe optimizarea discretă și aproximare, lucrarea de față ancorează aceste teme într-un cadru teoretic vast. Fiecare capitol este susținut de recenzii bibliografice și exerciții calibrate pentru nivelul universitar, transformând textul într-o resursă de referință pentru cercetători și practicieni.