Jawne wielomiany w 1 zmiennej o dolnych granicach złożoności obwodu superlogarytmicznego?

Zliczając argumenty, można pokazać, że istnieją wielomiany stopnia n w 1 zmiennej (tj. Coś w postaci które mają złożoność obwodu n. Można również pokazać, że wielomian taki jak wymaga co najmniej mnożenia (potrzebujesz tego tylko, aby uzyskać wystarczająco wysoki stopień). Czy są jakieś wyraźne przykłady wielomianów w 1 zmiennej o superlogarytmicznej dolnej granicy złożoności? (wyniki na dowolnym polu byłyby interesujące) $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ $x^n$ $\log_2 n$

cc.complexity-theory circuit-complexity polynomials algebraic-complexity matowe pośpiechy
źródło

Czy masz na myśli przykłady złożoności obwodu w polu skończonym? Nie rozumiem, jak argument liczący działałby na nieskończonym polu, a biorąc pod uwagę racjonalność, jestem prawie pewien, że ograniczenie Patersona-Stockmeyera jest ścisłe (patrz także moja odpowiedź poniżej).

n

$n$

\sqrt{n}

$\sqrt{n}$

Joshua Grochow

Ograniczenie sqrt (n), o którym wspominasz, jest tylko górną granicą liczby mnożenia (w dowolnym polu), ale jeśli liczymy zarówno dodania, jak i mnożenia jako operacje, to potrzebujemy n operacji na nieskończonym polu dla prawie każdego wielomianu, po prostu ponieważ nie ma n różnych współczynników w wielomianu i nie ma sposobu, aby ocenić wszystkie możliwe wielomiany z mniej niż n operacji (nie jestem pewien, czy należy to nazwać argumentem liczącym, czy nie).

mat hastings

Myślę, że musisz być bardziej precyzyjny w stwierdzeniu „nie ma sposobu, aby ocenić wszystkie możliwe wielomiany z mniej niż n opami”. Jednym ze sposobów interpretacji tego jest: jeśli uważamy wielomian za wielomian nie tylko w , ale również traktujemy jako zmienne (lub, równoważnie, załóżmy, że są algebraicznie niezależne), to wynik, że wymaga to n dodatków, należy do Pana (1966) i nie jest tylko argumentem liczącym (choć nie jest to zbyt trudne). W przeciwnym razie nie jestem pewien, do jakiego wyniku odnosi się to stwierdzenie.

\sum a_{i} x^{i}

$\sum a_i x^i$

x

$x$

a_{i}

$a_i$

a_{i}

$a_i$

Joshua Grochow

Mam na myśli: obwód składa się z bramek dodawania i mnożenia. Wejściami dla danej bramki mogą być wyjścia poprzednich bramek, x lub niektóre stałe. Pytanie brzmi: czy dla danego wielomianu możemy znaleźć obwód i wybór stałych w tym obwodzie, aby go obliczyć? Ale mamy (n + 1) wymiarową przestrzeń wielomianów, ale jeśli naprawimy strukturę obwodu z mniej niż n bramkami (przez „strukturę”, mam na myśli, które bramki używają wyjść z których innych bramek) i rozważymy wszystkie możliwy wybór stałych daje to mniej niż n wymiarową przestrzeń wielomianów, które można obliczyć.

mat hastings

Btw --- mam wrażenie, że konstruowanie wyraźnych przykładów na podstawie R lub C bez dalszych ograniczeń współczynników jest w większości rozwiązane. Z drugiej strony, konstruowanie wyraźnych przykładów, w których wszystkie współczynniki a_i są liczbami całkowitymi i nie rosną zbyt szybko, nadal jest otwarty? Istnieje przykład ze wszystkimi stałymi liczbami całkowitymi w ankiecie, o której wspominasz, ale rosną one podwójnie wykładniczo.

mat hastings

Paterson i Stockmeyer pokazują, że dla większości -liczb liczb wymiernych ocena wymaga arytmetyki operacje, a to jest trudne. $n$ $(a_1, \dotsc, a_n)$ $\prod_{i=1}^{n} (x - a_i)$ $\Omega(\sqrt{n})$

Następujące wielomiany mieszczą się w logarytmicznym współczynniku granicy , na podstawie wyników ze Strassen, Schnorr i Heintz & Sieveking: , , (dla wymierna nie jest liczbą całkowitą), i inne dokładne odniesienia i więcej na ten temat, patrz str. 324-325 w badaniu von zur Gathen użytkownika . $\sqrt{n}$ $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$ $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$ $\sum_{i=1}^{n} i^{r} x^{i}$ $r$

Joshua Grochow
źródło

Dzięki. Wydaje się więc, że otwartym problemem jest to, że jeśli policzymy dodatki również jako operacje, można zbudować wielomian, który wymaga więcej niż operacji sqrt (n), w celu stworzenia takiej, która wymaga n operacji. Jakieś wyniki w tym kierunku? (Wątpię w to, ponieważ w metodzie, która wymaga tylko mnożenia sqrt (n), dodatki dają pewne mnożenie macierzy, a to prawdopodobnie zmniejsza się do niższych granic złożoności mnożenia macierzy-skalara)

mat hastings

Jawne wielomiany w 1 zmiennej o dolnych granicach złożoności obwodu superlogarytmicznego?

Odpowiedzi: