Pytania otagowane jako polynomials

12
Gröbner bazuje w TCS?
Czy ktoś wie o ciekawych zastosowaniach baz Gröbnera w teoretycznej informatyce? Podstawy Gröbnera są używane do rozwiązywania wielowymiarowych równań wielomianowych, co jest ogólnie trudnym problemem NP. Zastanawiałem się, czy użyto niektórych możliwych do rozwiązania specjalnych przypadków w celu zapewnienia wydajnych algorytmów / konstrukcji / dowodów w obszarach TCS lub powiązanych …
1
Mnożenie n wielomianów stopnia 1
Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Możesz zrobić czas , stosując FFT w sposób drzewny. Czy możesz zrobić O ( n log n ) …
2
Metoda wielomianowa dla wyników złożoności
Metody wielomianowe , powiedzmy twierdzenie kombinatoryczne Nullstellensatz i twierdzenie Chevalleya-Ostrzegania, są potężnymi narzędziami w kombinatywnej addytywności. Reprezentując problem z właściwymi wielomianami, mogą zagwarantować istnienie rozwiązania lub liczbę rozwiązań wielomianów. Zostały one wykorzystane do rozwiązania problemów, takich jak ograniczone zestawy sum lub problemy o sumie zerowej , a niektóre twierdzenia w …
3
Reprezentowanie OR za pomocą wielomianów
Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .nnnx1,…,xnx1,…,xnx_1,\ldots, x_np(x1,…,xn)p(x1,…,xn)p(x_1,\ldots,x_n)p(x1,…,xn)=1−∏ni=1(1−xi)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)nnn Ale jak mogę pokazać, co wydaje się oczywiste, że jeśli jest wielomianem, który dokładnie reprezentuje funkcję OR (więc ), a następnie ?∀ x ∈ …
3
Obliczanie sumy rzadkich wielomianów podniesionych do kwadratu w czasie O (n log n)?
Załóżmy, że mamy wielomiany stopnia co najwyżej , , tak że całkowita liczba niezerowych współczynników wynosi (tzn. Wielomiany są rzadkie). Interesuje mnie wydajny algorytm obliczania wielomianu:p1,...,pmp1,...,pmp_1,...,p_mn > m nnnnn>mn>mn>mnnn ∑ipi(x)2∑ipi(x)2\sum_i p_i(x)^2 Ponieważ ten wielomian ma stopień co najwyżej 2n2n2n , zarówno wielkość wejściowa, jak i wyjściowa wynosi O(n)O(n)O(n) . W …
2
Jaka jest tendencja do losowych wielomianów o niskim stopniu nad GF (2)?
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Gdy piszę losowy wielomian o stopniu ≤d≤d\le d a n zmiennych, można myśleć o każdy jednomianów całkowitego stopnia ≤d≤d\le d pobrane z prawdopodobieństwem 1/2. Jedyną istotną rzeczą, jaką znam, jest wariant Schwartza-Zippla, który stwierdza, że ​​jeśli wielomian jest niestały, wówczas jego odchylenie wynosi …
2
Oceniając multilinearyzację obwodu arytmetycznego?
Niech p ( x1, … , Xn)p(x1,…,xn)p(x_1,\ldots,x_n) jest wielomianem wielu zmiennych współczynnikach nad polem faFF . Multilinearization z ppp , oznaczony przez P , jest wynikiem zastąpienia wielokrotnie każdy x d I o d > 1 o x i . Wynikiem jest oczywiście wielomianowy wielomian.p^p^\hat{p}xrejaxidx_i^dre> 1d>1d > 1xjaxix_i Rozważmy następujący …
1
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 …
1
O derandomizacji wielomianowych testów tożsamości
W teście tożsamości wielomianowej szukamy algorytmu deterministycznego, aby wnioskować o równości dwóch wielomianów . Ważnym otwartym problemem jest derandomizacja znanych skutecznych algorytmów randomizowanych i wytwarzanie wydajnego algorytmu deterministycznego. Czy istnieje kompletny problem dla PIT, tak że derandomizacja testów tożsamości dla tej jednej klasy wielomianów rozwiązuje ten otwarty problem? Jeśli nie, …
1
Złożoność splotu w pierścieniu max / plus
Możemy wykonać splot w O(nlogn)O(nlog⁡n)O(n\log n) dla wielomianów dodatnich / wielokrotnych za pomocą FFT. Jednak podejście to nie wydaje się zbyt ogólne w odniesieniu do pierścieni w ogóle. Czy nastąpił postęp w stosunku do naiwnego splotu O(n2)O(n2)O(n^2) dla pierścienia max / plus? soft-max(x,y)=log(ex+ey)=max(x,y)+log(1+emin(x,y)−max(x,y))soft-max(x,y)=log⁡(ex+ey)=max(x,y)+log⁡(1+emin(x,y)−max(x,y))\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y) + \log(1+e^{\min(x,y)-\max(x,y)})
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.