Niech prawdziwa macierz k×nk×nk\times n ( k≤nk≤nk\le n ) AA{\bf A} z tą właściwością, że dowolny zbiór kkk kolumn ma pełną rangę. P: istnieje efektywny sposób deterministyczny znaleźć wektor tak że zmodyfikowanym matrycy ' = [aa{\bf a}A′=[Aa]A′=[Aa]{\bf A}' = [{\bf A}\;{\bf a}] zachowuje tę samą...
Na cs.stackexchange zapytałem o bibliotekę algebird scala na githubie, spekulując, dlaczego mogą potrzebować abstrakcyjnego pakietu algebry. Strona github zawiera kilka wskazówek: Implementacje Monoidów dla interesujących algorytmów aproksymacyjnych, takich jak filtr Bloom, HyperLogLog i...
Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy....
Czy istnieje znana konstrukcja kodu korygującego błędy liniowe (z rozsądnymi parametrami), na przykład gdy podano logiczny wektor zwraca również wartość logiczną wektora logicznego? (chociaż to koniec \ mathbb {F} _q )ECC:Fnq→FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to...
Wiem, że eliminacja Gaussa wymaga operacji arytmetycznych , ale nie jestem pewien, czy znane są lepsze algorytmy.O (
Podczas mojej pracy wpadłem na następujący problem: Usiłuję znaleźć macierz n × nn×nn \times n M dla dowolnego n > 3 o następujących właściwościach:( 0 , 1 )(0,1)(0,1)M.M.Mn > 3n>3)n > 3 Wyznacznik M.M.M jest parzysty. Dla niepustych podzbiorów ja, J⊆ { 1 , 2 , 3...
Biorąc pod uwagę dwie permutacje i nad elementami (tj. ), jaka jest złożoność obliczania kolejności podgrupy generowanej przez ? Albo po prostu decydując, czy podgrupa jest rzędu(tj. wszystkie )?h n S n g , h n ! S nsolgghhhnnnS.nSnS_nsol, hg,hg,hn
Od jakiegoś czasu bardzo interesuję się teorią języka programowania i procesami i zacząłem je studiować. Szczerze mówiąc, jest to coś, w czym nie miałbym nic przeciwko karierze. Uważam teorię za niezwykle fascynującą. Jedno ciągłe pytanie, na które wciąż wpadam, brzmi: czy teoria PL lub Process...
W Bernsteina i Vazirani w przełomowej pracy „Quantum Theory Complexity”, pokazują, że redd wymiarowa przekształcenie unitarne można skutecznie przybliżony przez iloczyn co nazywają „w pobliżu trywialna obroty” i „przesunięcia fazowe niemal trywialne”. „Near-trywialne obrotów” oznaczają wymiarową...
Możemy wykonać splot w O(nlogn)O(nlogn)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 /...
Powiedzmy, że mamy wielościan w standardowej formie: A x = bx ≥ 0ZAx=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba...
W złożoności komunikacyjnej domniemanie log-rank stwierdza, że c c ( M) = ( logr k ( M) )O ( 1 )cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Gdzie jest złożoność komunikacji M ( x , y ) , a r k ( M ) jest rangę M (jako matrycy) w liczb rzeczywistych.c c ( M)cc(M)cc(M)M.( x , y)M(x,y)M(x,y)r k...
Istnieje program liniowy, dla którego chcę nie tylko rozwiązania, ale rozwiązania, które jest tak centralne, jak to możliwe na powierzchni polytopa, który przyjmuje minimalną wartość. Z góry oczekujemy, że minimalizująca powierzchnia powinna być wielowymiarowa z różnych powodów, w tym, że...
Jednym z głównych problemów w wyliczaniu wykresów jest określenie „kształtu” wykresu, np. Klasy izomorfizmu dowolnego konkretnego wykresu. Jestem w pełni świadomy, że każdy wykres może być reprezentowany jako macierz symetryczna. Jednak, aby uzyskać jego kształt, potrzebujesz kolekcji permutacji...
Rozważ przestrzeń Hilberta H.=H.1⊗ ⋯ ⊗H.nH.=H.1⊗⋯⊗H.nH = H_1 \otimes \dots \otimes H_n. Podstawa produktu nie do rozszerzenia (UPB) to zestaw wektorów produktu|vja⟩ = |v1ja⟩ ⊗ ⋯ ⊗ |vnja⟩|vja⟩=|vja1⟩⊗⋯⊗|vjan⟩\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle takie,...
To jest wyspecjalizowana wersja poprzedniego pytania: Złożoność znalezienia składowej macierzy . W przypadku macierzy symetrycznych NxN wiadomo, że czas O (N ^ 3) wystarcza do obliczenia rozkładu własnego. Pytanie brzmi: czy możemy osiągnąć sub-sześcienną złożoność?...
Według tytułu, oprócz korzystania z solwera LP ogólnego przeznaczenia, istnieje podejście do rozwiązywania układów nierówności względem zmiennych xja, ... ,xkxi,…,xkx_i, \ldots, x_k gdzie nierówności mają formę ∑ja ∈ jaxja<∑j ∈ Jxjot∑i∈Ixi<∑j∈Jxj\sum_{i \in I} x_i < \sum_{j \in J} x_j? Co ze...
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...
Wprowadzenie Piszę pracę doktorską na temat abstrakcyjnego modelowania delty (ADM), abstrakcyjnego algebraicznego opisu modyfikacji (znanych jako delty ) zdolnych do działania na produkty (jak w „produktach programowych”). Można to wykorzystać do zorganizowania zestawu powiązanych produktów...
Pozwolić AAAbyć skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .L⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to...