Pytania otagowane jako linear-algebra

Algebra liniowa zajmuje się przestrzeniami wektorowymi i transformacjami liniowymi.

1
Redukcja przestrzeni logów z obwodów Parity-L na obwody CNOT?
Pytanie. W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości? Równoważnie: czy występuje ograniczenie przestrzeni logicznej z iterowanych produktów macierzy modulo …
4
Znalezienie najrzadszego rozwiązania układu równań liniowych
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi do zera? Próbuję również ustalić, na czym polega zależność od ccc . …
1
Jaka jest złożoność sprawdzenia, czy macierz można diagonalizować?
Biorąc pod uwagę macierzy A z racjonalnym pozycji. Jaką złożoność sprawdzenia A można diagonalizować?n×nn×nn\times nAAAAAA Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten problem? Wszelkie wskazówki / komentarze są mile widziane! Dzięki.
1
Algorytmiczny problem wektorowy
Mam problem algebraiczny związany z wektorami w dziedzinie GF (2). Niech będą wektorami wymiaru , a . Znaleźć wielomianowej algorytm czasową znajdzie (0,1)-wektor tego samego wymiaru tak, że nie jest sumą każdy wektory między . Dodawanie wektorów odbywa się ponad polem GF (2), które ma dwa elementy 0 i 1 …
1
Mnożenie macierzy w
Szukałem mnożenia macierzy, więc najpierw odwiedziłem algorytmy mnożenia macierzy wiki. W referencjach znalazłem artykuł, który twierdzi, że używa algorytmu O ( n2)l o g( n ) )O(n2)losol(n))O(n^2 log(n)) , chciałbym przeczytać artykuł, ale jest skomplikowany i zajmie zbyt wiele czasu, aby go przeczytać, ale jeśli jest ktoś, kto czyta ten …
1
Próbkowanie z wielowymiarowego Gaussa z grafem kowariancji Laplaciana (odwrotna)
Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie jednej z tych grafów macierzy Laplaciana jako kowariancji lub …
1
Jak agregacje bazy danych tworzą monoid?
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 CountMinSketch. Pozwalają ci myśleć o tych wyrafinowanych operacjach, takich jak liczby, i dodawać je w hadoopie lub …
1
Konstruowanie wektorów w pozycji ogólnej
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ą właściwość coAA{\bf A} : dowolnekkk …
2
Na
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie 4: wymiarową afinicznej kolektor jest do ekspresji w skończonej związek rozdzielaczy …
1
Złożoność osiągalności w liniowych układach dynamicznych nad polami skończonymi
Niech AAA będzie macierzą nad polem skończonym F2={0,1}F2={0,1}\mathbb{F}_2 = \{0,1\} a xxx , yyy będą wektorami przestrzeni Fn2F2n\mathbb{F}_2^n . Interesuje mnie złożoność obliczeniowa przy podejmowaniu decyzji, czy istnieje t∈Nt∈Nt \in \mathbb{N} takie, że Atx=yAtx=yA^t x = y , tj. Problem osiągalności liniowych układów dynamicznych nad polami skończonymi. Problem ten jest …
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.