Pytania otagowane jako arithmetic-circuits

3
Obwody arytmetyczne o
Rozważ obwód, który przyjmuje jako liczby wejściowe w [ 0 , 1 ][0,1][0,1] i ma bramki, które składają się z funkcji max ( x , y)max(x,y)\max(x, y) , min ( x , y)min(x,y)\min(x, y) , 1 - x1−x1 - x i x + y2)x+y2\frac{x+y}{2} . Wyjście obwodu jest wówczas również …
2
Determinanty i mnożenie macierzy - podobieństwo i różnice w złożoności algorytmicznej i wielkości obwodu arytmetycznego
Próbuję zrozumieć związek między złożonością algorytmiczną a złożonością obwodów determinant i mnożenia macierzy. Wiadomo, że wyznacznik macierzy można obliczyć w czasie , gdzie to minimalny czas wymagany do pomnożenia dowolnych dwóch macierzy. Wiadomo również, że najlepszą złożonością obwodów wyznaczników jest wielomian na głębokości i wykładniczy na głębokości 3. Ale złożoność …
2
Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków
Rozważ następujący problem: Biorąc pod uwagę macierz , chcemy zoptymalizować liczbę dodatków w algorytmie mnożenia do obliczania .MMMv↦Mvv↦Mvv \mapsto Mv Uważam ten problem za interesujący ze względu na jego związek ze złożonością mnożenia macierzy (ten problem jest ograniczoną wersją mnożenia macierzy). Co wiadomo o tym problemie? Czy są jakieś interesujące …
1
Dlaczego dolne granice dla obwodów boolowskich nie implikują niższych granic obwodów arytmetycznych
Moje pytanie brzmi: dlaczego dolne granice dla głębokości 3 Obwody logiczne z bramkami „i” i „xor” dla wyznacznika nie oznaczają takich samych dolnych granic dla obwodów arytmetycznych w ?ZZ\mathbb{Z} Co jest nie tak z następującym argumentem: Niech będzie wyznacznikiem obliczającym obwód arytmetyczny, a następnie biorąc wszystkie zmienne mod 2 otrzymamy …
1
Randomizowane testy tożsamości dla wielomianów wysokiego stopnia?
Niech będzie wielomianem zmiennym podanym jako obwód arytmetyczny o rozmiarze poli i niech będzie liczbą pierwszą.faffnnn(n)(n)(n)p=2)Ω(n)p=2Ω(n)p = 2^{\Omega(n)} Czy możesz sprawdzić, czy jest identycznie zerowe w stosunku do , z czasem i prawdopodobieństwem błędu , nawet jeśli stopień nie jest a priori ograniczone? Co jeśli jest jednoznaczny?faffZpZp\mathbb{Z}_ppoli(n)poly(n)\mbox{poly}(n)≤1-1/poli(n)≤1−1/poly(n)\leq 1-1/\mbox{poly}(n)faff Zauważ, że …
1
Sprawdzanie, czy wielomian wpływa na czynniki liniowe
Niech będzie wielomianem podanym przez obwód arytmetyczny o rozmiarze . Biorąc pod uwagę jako dane wejściowe, czy istnieje algorytm deterministyczny, aby sprawdzić, czy wszystkie nieredukowalne czynniki w są formami liniowymi? W pokrewnej uwadze, biorąc pod uwagę postać liniową , możemy sprawdzić deterministycznie, czy jest współczynnikiem . Oczywiście chcemy, aby czas …
2
Anulowanie i wyznacznik
Algorytm Berkowitza zapewnia obwód wielomianowy o głębokości logarytmicznej do wyznaczania macierzy kwadratowej z wykorzystaniem mocy macierzy. Algorytm domyślnie wykorzystuje anulowanie. Czy anulowanie jest niezbędne do uzyskania obwodu wielomianowego o głębokości logarytmicznej lub liniowej w celu obliczenia wyznacznika (i każdego możliwego najlepszego obwodu na stałe)? Czy istnieją dolne granice w pełni …
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.