Moje pytanie jest proste: Jaki jest najgorszy czas z najbardziej znanych algorytm działa dla wyliczania eigendecomposition danego matrycy?n×nn×nn \times n Czy skład eigend redukuje się do mnożenia macierzy, czy w najgorszym przypadku są najlepiej znanymi algorytmami (przez SVD...
Powszechnie uważa się, że dla wszystkich ϵ > 0ϵ>0\epsilon > 0 możliwe jest pomnożenie dwóch macierzy n × nn×nn \times n w czasie O ( n2 + ϵ)O(n2+ϵ)O(n^{2 + \epsilon}) . Trochę dyskusji jest tutaj . Zapytałem niektórych ludzi, którzy są bardziej zaznajomieni z badaniami, czy myślą, że...
Niech będzie kwadratową macierzą liczb całkowitych, a niech n będzie liczbą całkowitą dodatnią. Interesuje mnie złożoność następującego problemu decyzyjnego:MMMnnn Czy prawy górny wpis dodatni?MnMnM^n Zauważ, że oczywiste podejście iterowanego kwadratu (lub innego jawnego obliczenia) wymaga od...
Ranga znaku macierzy A z wpisami + 1, -1 jest najmniejszą rangą (ponad rzeczywistymi) macierzy B, która ma taki sam wzór znaków jak A (tj. dla wszystkich i , j ). Pojęcie to jest ważne w złożoności komunikacji i teorii uczenia się.AijBij>0AijBij>0A_{ij}B_{ij}>0i,ji,ji,j Moje pytanie brzmi:...
Algorytm Coppersmitha – Winograda jest asymptotycznie najszybszym znanym algorytmem do mnożenia dwóch macierzy kwadratowych. Czas działania ich algorytmu to który jest najlepiej znany do tej pory. Jaka jest złożoność przestrzeni tego algorytmu? Czy to jest w ?n×nn×nn \times...
Najnowszy i niezwykle zręczny dowód domniemania wrażliwości opiera się na wyraźnej * konstrukcji macierzy An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times 2^n} , zdefiniowanej rekurencyjnie w następujący sposób: A1=(0110)A1=(0110)A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix} oraz dla...
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP...
Czy możliwe jest zbudowanie wyraźnej macierzy z , tak aby każda podmacierz zawiera mniej niż ?N×NN×NN \times N 0/10/10/1N1.5N1.5N^{1.5}N0.499×N0.499N0.499×N0.499N^{0.499} \times N^{0.499}N0.501N0.501N^{0.501} Lub prawdopodobnie możliwe jest zbudowanie jawnego zestawu uderzeń dla takiej...
Matryca jest nazywana całkowicie regularną, jeśli wszystkie jej kwadratowe submatrice mają pełną rangę. Takie matryce zastosowano do budowy superkoncentratorów. Jaka jest złożoność decyzji, czy dana matryca jest całkowicie regularna w stosunku do racjonalności? Ponad skończonymi polami? Mówiąc...
Określić Gaussa złożoność danego matrycy, tak aby minimalna ilość elementarnych wierszy i kolumn operacji wymaganych do matrycy w postaci górnej trójkątnej. Jest to wielkość od do (poprzez eliminację Gaussa). Pojęcie ma sens w każdej dziedzinie.n×nn×nn \times n000n2n2n^2 Ten problem z pewnością...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
W algorytmie Strassena, aby obliczyć iloczyn dwóch macierzy ZAZA\mathbf{A} i , macierze i są podzielone na macierze blokowe i algorytm kontynuuje rekurencyjne obliczanie bloków produkty matryca-matryca w przeciwieństwie do naiwnych blokowych produktów matrycowo-matrycowych, tj. jeśli chcemy ,...
Załóżmy, że otrzymujemy macierz i pozwólmy . Jak szybko możemy obliczyć moc A ^ m tej macierzy? m ∈ N 0 A mA ∈ RN.× N.ZA∈RN.×N.A \in \mathbb R^{N\times N}m ∈ N0m∈N.0m \in \mathbb N_0ZAmZAmA^m Kolejną najlepszą rzeczą w porównaniu do obliczania produktów jest zastosowanie szybkiego potęgowania,...
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że...
Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacjaσσ\sigma taka, że dla wszystkich permutacji mamy ?π≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Õ Mi π( i )ΠM.jaσ(ja)≠ΠM.jaπ(ja)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Uwagi Oczywiście...
Biorąc pod uwagę macierz m×nm×nm \times n (przy założeniu, że m≥nm≥nm \ge n ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn? Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany...
Niech kwadratowa rzeczywista macierz A i dwa wektory x i b o długości n , takie, że A x = b . Rozwiązanie x poprzez standardową eliminację Gaussa daje łączną złożoność prawie O ( n 3 ) . Są jednak przypadki, w których rozwiązywanie (lub ϵ - rozwiązywanie w przybliżeniu) dla x kosztuje O ( n log ρ...
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...
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...
Rozważ następujący problem testowania członkostwa w podgrupie abelian . Wejścia: Skończona grupa abelowa G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} o dowolnie dużych didid_i . Wytwarzające osadzone {h1,…,hn}{h1,…,hn}\lbrace...