Obwody arytmetyczne: Przegląd najnowszych wyników i otwartych pytań

Oryginalny tytuł:

Arithmetic Circuits: A Survey of Recent Results and Open Questions

Zawartość książki:

Teoria złożoności algebraicznej bada nieodłączną trudność problemów algebraicznych poprzez kwantyfikację minimalnej ilości zasobów wymaganych do ich rozwiązania. Najbardziej podstawowe pytania w teorii złożoności algebraicznej są związane ze złożonością obwodów arytmetycznych: dostarczanie wydajnych algorytmów dla problemów algebraicznych, udowadnianie dolnych ograniczeń na rozmiar i głębokość obwodów arytmetycznych, dostarczanie wydajnych deterministycznych algorytmów testowania tożsamości wielomianów oraz znajdowanie wydajnych algorytmów rekonstrukcji wielomianów obliczanych przez obwody arytmetyczne.

Obwody arytmetyczne: A Survey of Recent Results and Open Questions stanowi przegląd dziedziny złożoności obwodów arytmetycznych. Obejmuje główne wyniki i techniki w tej dziedzinie, z naciskiem na prace z ostatnich dwóch dekad.

W szczególności omówiono klasyczne wyniki strukturalne, w tym VP = VNC2, oraz najnowsze osiągnięcia podkreślające znaczenie obwodów o głębokości 4, klasyczne dolne ograniczenia Strassena i Baura-Strassena oraz najnowsze dolne ograniczenia dla obwodów i formuł wieloliniowych, postępy poczynione w dziedzinie deterministycznego sprawdzania tożsamości wielomianów oraz wyniki dotyczące rekonstrukcji obwodów arytmetycznych. Przedstawiono również wiele otwartych pytań, które można uznać za naturalne "kolejne kroki", biorąc pod uwagę obecny stan wiedzy.