Circuiti aritmetici: Un'indagine sui risultati recenti e sulle questioni aperte

Titolo originale:

Arithmetic Circuits: A Survey of Recent Results and Open Questions

Contenuto del libro:

La teoria della complessità algebrica studia la difficoltà intrinseca dei problemi algebrici quantificando la quantità minima di risorse necessarie per risolverli. Le questioni fondamentali della complessità algebrica sono legate alla complessità dei circuiti aritmetici: fornire algoritmi efficienti per i problemi algebrici, dimostrare i limiti inferiori della dimensione e della profondità dei circuiti aritmetici, fornire algoritmi deterministici efficienti per la verifica dell'identità dei polinomi e trovare algoritmi efficienti di ricostruzione per i polinomi calcolati da circuiti aritmetici.

Circuiti aritmetici: A Survey of Recent Results and Open Questions analizza il campo della complessità dei circuiti aritmetici. Copre i principali risultati e tecniche del settore, con particolare attenzione ai lavori degli ultimi due decenni.

In particolare, vengono discussi i risultati strutturali classici, tra cui VP = VNC2, e i recenti sviluppi che evidenziano l'importanza dei circuiti di profondità 4, i limiti inferiori classici di Strassen e Baur-Strassen e i recenti limiti inferiori per i circuiti e le formule multilineari, i progressi compiuti nel campo della verifica deterministica delle identità polinomiali e i risultati relativi alla ricostruzione dei circuiti aritmetici. Vengono inoltre presentate molte questioni aperte che possono essere considerate come “passi successivi” naturali, dato lo stato attuale delle conoscenze.