Pytania otagowane jako algebraic-complexity

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 …
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
Determinant uogólnionej macierzy Vandermonde'a
Macierz Moore'a jest podobna do macierzy Vandermonde, ale ma nieco zmodyfikowaną definicję. http://en.wikipedia.org/wiki/Moore_matrix Jaka jest złożoność obliczenia wyznacznika danego pełnego rzędu macierzy Moore'a modulo jakiejś liczby całkowitej?n × nn×nn \times n Czy wyznacznik Moore'a można zredukować z przy użyciu technik FFT do dla niektórych ?O ( n log a n …
2
Dolne granice dla liniowego problemu satysfakcji
W SODA 1995 Jeff Erickson wykazały niższe granice liniowego spełnialności (sprawdzenie, czy niektóre -subset z n liczb rzeczywistych spełnia równanie liniowe o r zmiennych). Metoda dowodowa wykorzystuje nieskończenie małe i zasadę transferu Tarskiego .rrrnnnrrr Czy ktoś mógłby wyjaśnić intuicję, jaką kryje się za tą trasą, aby udowodnić tę granicę? Jaka …
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 …
3
Znajdź pozostałą część dużego stałego wielomianu po podzieleniu przez niewielki nieznany wielomian
Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych tabelach przeglądowych. Pod koniec „fazy początkowej” otrzymamy …
1
(Kryptograficzne) problemy do rozwiązania w wielomianowej liczbie kroków arytmetycznych
W artykule Adi Shamira [1] z 1979 r. Pokazuje, że faktoring można wykonać w wielomianowej liczbie kroków arytmetycznych . Fakt ten został powtórzony i dlatego zwrócił moją uwagę w niedawnej pracy Borweina i Hobarta [2] w kontekście programów liniowych (SLP). Ponieważ byłem raczej zaskoczony, gdy to przeczytałem, mam następujące pytanie: …
1
Stała macierzy i z wyznaczników
Niech będzie macierzą lub z wpisami . Czy ktoś może mi dostarczyć macierz , aby ? Jaki jest najmniejszy znany jawny B , taki że \ operatorname {per} (A) = \ det (B) ? Wszelkie odniesienia do tego z wyraźnymi przykładami?AZAA3×33)×3)3 \times 34×44×44 \times 4aijzajajota_{ij}BbBper(A)=det(B)za⁡(ZA)=det(b)\operatorname{per}(A) = \det(B)BbBper(A)=det(B)za⁡(ZA)=det(b)\operatorname{per}(A) = \det(B) Niektóre …
1
Rzeczywista złożoność bitowa mnożenia macierzy wynosi
Mnożenie macierzy przy użyciu techniki regularnej (iloczyn wewnętrzny rzędów i kolumn) O (n3))O(n3))O(n^{3}) mnożenia i O (n3))O(n3))O(n^{3})wzbogacenie. Jednak przy założeniu, że wpisy o jednakowej wielkości (liczba bitów w każdym wpisie obu macierzy jest mnożona) o wielkościmmm bitów, operacja dodawania faktycznie się dzieje O (n3)n m ) = O (n4m )O(n3)nm)=O(n4m)O(n^{3}nm) …
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.