Arithmetic Circuits: O analiză a rezultatelor recente și a întrebărilor deschise

Titlul original:

Arithmetic Circuits: A Survey of Recent Results and Open Questions

Conținutul cărții:

Teoria complexității algebrice studiază dificultatea inerentă a problemelor algebrice prin cuantificarea cantității minime de resurse necesare pentru rezolvarea acestora. Cele mai fundamentale întrebări din complexitatea algebrică sunt legate de complexitatea circuitelor aritmetice: furnizarea de algoritmi eficienți pentru problemele algebrice, demonstrarea limitelor inferioare pentru dimensiunea și adâncimea circuitelor aritmetice, furnizarea de algoritmi deterministici eficienți pentru testarea identității polinomiilor și găsirea de algoritmi eficienți de reconstrucție pentru polinoamele calculate prin circuite aritmetice.

Circuite aritmetice: A Survey of Recent Results and Open Questions analizează domeniul complexității circuitelor aritmetice. Acesta acoperă principalele rezultate și tehnici din domeniu, cu accent pe lucrările din ultimele două decenii.

În special, se discută rezultatele structurale clasice, inclusiv VP = VNC2 și evoluțiile recente care evidențiază importanța circuitelor de adâncime 4, limitele inferioare clasice ale lui Strassen și Baur-Strassen și limitele inferioare recente pentru circuitele și formulele multiliniare, progresele realizate în domeniul verificării deterministe a identităților polinomiale și rezultatele privind reconstrucția circuitelor aritmetice. Acesta prezintă, de asemenea, multe întrebări deschise care pot fi considerate ca fiind "următorii pași" naturali, având în vedere stadiul actual al cunoștințelor.