Pytania otagowane jako matrices

6
Złożoność znalezienia składowej macierzy
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 )?O(n3)O(n3)O(n^3) Proszę zauważyć, że proszę o analizę najgorszego przypadku (tylko w kategoriach …
1
Złożoność zasilania macierzy
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 nas potencjalnie obsługi liczb całkowitych o podwójnie wykładniczej wielkości, tj. Mających wykładniczo wiele bitów. …
2
Przybliżenie rangi znaku macierzy
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: czy są jakieś znane algorytmy …
1
Złożoność przestrzenna algorytmu Coppersmitha – Winograda
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 nO(n2.376)O(n2.376)O(n^{2.376})Θ(n2)Θ(n2)\Theta(n^2)
2
Pytanie o dwie matryce: Hadamard przeciwko „magicznej” w dowodzie przypuszczenia wrażliwości
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 n≥2n≥2n\geq 2 , n = ( n - 1 mi n - 1 mi n - 1An=(An−1In−1In−1−An−1)An=(An−1In−1In−1−An−1)A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix} W szczególności …
2
Jawna zrównoważona macierz
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 właściwości. Łatwo zauważyć, że macierz losowa ma tę właściwość z prawdopodobieństwem wykładniczo bliskim . Również lemat mieszania ekspandera nie …
4
Pozytywne uporządkowanie topologiczne, weź 3
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 również by go rozwiązał. Edycja: Laszlo Vegh …
3
Złożoność decydowania, czy macierz jest całkowicie regularna
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 bardziej ogólnie, nazwij matrycę całkowicie nieregularną, jeśli wszystkie kwadratowe podmacie wielkości co najwyżej …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
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 z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
2
Dolne granice złożoności Gaussa
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ą wydaje się bardzo podstawowy i musiał zostać zbadany. O …
2
podobne matryce
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 są permutacją, które wiążą ten problem z …
1
Jak obliczyć moc macierzy kwadratowych?
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, które wymaga produktów …
1
Czy możemy zdecydować, czy stały ma unikalny termin?
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 można wymienić produkt na sumę, problem pozostaje ten …
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.