Pochodne cząstkowe w złożoności arytmetycznej i nie tylko

Oryginalny tytuł:

Partial Derivatives in Arithmetic Complexity and Beyond

Zawartość książki:

Wielomiany są prawdopodobnie najważniejszą rodziną funkcji w matematyce. Pojawiają się w słynnych wynikach zarówno z czasów starożytnych, jak i współczesnych, takich jak nierozwiązywalność przez rodniki wielomianów stopnia >= 5 Abla i Galois oraz dowód Wilesa na "ostatnie twierdzenie" Fermata.

W informatyce znajdują one zastosowanie m.in. w kodach korygujących błędy i dowodach probabilistycznych. Manipulacja wielomianami jest niezbędna w wielu zastosowaniach algebry liniowej i obliczeń symbolicznych.

Książka Partial Derivatives in Arithmetic Complexity and Beyond poświęcona jest głównie badaniu wielomianów z perspektywy obliczeniowej. Ilustruje, że można dowiedzieć się wiele o strukturze i złożoności wielomianów, badając (niektóre) ich pochodne cząstkowe.

Pokazuje również, że pochodne cząstkowe dostarczają niezbędnych składników w dowodzeniu zarówno górnych, jak i dolnych ograniczeń na obliczanie wielomianów za pomocą różnych naturalnych modeli arytmetycznych. W dalszej części artykułu przyjrzymy się zastosowaniom, które wykraczają poza złożoność obliczeniową, gdzie pochodne cząstkowe dostarczają wielu informacji strukturalnych o wielomianach (w tym o ich liczbie pierwiastków, redukowalności i wewnętrznych symetriach) i pomagają nam rozwiązywać różne problemy z zakresu teorii liczb, geometrii i kombinatoryki. Książka Partial Derivatives in Arithmetic Complexity and Beyond jest nieocenionym źródłem informacji dla każdego, kto interesuje się wielomianami.

Wiele rozdziałów w tych trzech częściach można czytać niezależnie. W przypadku nielicznych, które wymagają kontekstu z poprzednich rozdziałów, jest to określone w streszczeniu rozdziału.