Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Znajdowanie podobnych wektorów w czasie subkwadratowym
Pozwolić d:{0,1}k×{0,1}k→Rd:{0,1}k×{0,1}k→Rd:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}być funkcją, którą nazywamy funkcją podobieństwa . Przykłady funkcji podobieństwa to odległość cosinus,l2l2l_2 norma, odległość Hamminga, podobieństwo Jaccard itp. Rozważać nnn binarne wektory długości kkk: v⃗ ∈({0,1}k)nv→∈({0,1}k)n\vec{v} \in (\{0,1\}^k)^n. Naszym celem jest grupowanie wektorów, które są podobne. Bardziej formalnie chcemy obliczyć wykres podobieństwa, w którym węzły …
1
Sekretarka zatrudniająca
Jest to rozszerzenie klasycznego problemu sekretarza . W grze o zatrudnianie masz zestaw kandydatów i porządek na temat umiejętności każdego pracownika.C={c1,…,cN}C={c1,…,cN}\mathcal C=\{c_1,\ldots,c_N\} Wlog, zakładamy, że jest najbardziej wykwalifikowany, a następnie itd.c1c1c_1c2c2c_2 Kolejność, w jakiej kandydaci są wybierani losowo, jest jednolita i (oczywiście) nieznana pracodawcom. Załóżmy teraz, że masz rynek z …
2
Złożoność rozwiązywania równań liniowych
Co wiadomo na temat złożoności rozwiązywania układu równań liniowych na pewnym polu skończonym? Wiem, że istniejeO (n3))O(n3))O(n^3)algorytm (Gauss), który oblicza rozwiązanie, aw przypadku systemów rzadkich istnieją jeszcze lepsze algorytmy. Zastanawiałem się jednak, czy istnieje jakaś teoretyczna charakterystyka złożoności tego problemu. Na przykład jest odpowiedni problem decyzyjny wN C.N.do\mathbf{NC}? Czy jest …
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 …
1
Najmniejsza liczba bramek do mnożenia
Jaki jest najlepszy wynik dla liczby bramek w obwodzie pomnożącym dwie liczby całkowite n-bitowe? Oczywista metoda generuje bramki . Istnieją lepsze podejścia z i .θ(n2)θ(n2)\theta(n^2)θ(nlognloglogn)θ(nlog⁡nlog⁡log⁡n)\theta(n\log n \log\log n)θ(nlogn2log∗(n))θ(nlog⁡n2log∗⁡(n))\theta(n\log n2^{\log^*(n)}) Nie mogłem znaleźć żadnej rodziny obwodów boolowskich, która obsługiwałaby mnożenie za pomocą bramek . Zastanawiam się, czy istnieje taka rodzina obwodów.nlognnlog⁡nn\log …
1
Losowe ograniczenia i związek z całkowitym wpływem funkcji boolowskich
Powiedzmy, że mamy funkcję boolowską fa: { - 1 , 1}n→ { - 1 , 1 }f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} i aplikujemy δδ\delta-losowe ograniczenie na faff. Ponadto powiedz, że drzewo decyzyjneT.TT to oblicza faff zmniejsza się O ( 1 )O(1)O(1)w wyniku losowego ograniczenia. Czy to implikuje tofafaf ma bardzo niski wpływ całkowity?
3
Czy istnieje uogólnienie teorii informacji na wielomianowo poznaną informację?
Przepraszam, to trochę „miękkie” pytanie. Teoria informacji nie ma pojęcia złożoności obliczeniowej. Na przykład instancja SAT lub instancja SAT plus bit wskazujący na satysfakcję niosą tę samą ilość informacji. Czy istnieje sposób sformalizowania pojęcia „wielomianowo poznawalny”? Takie ramy mogą definiować na przykład pojęcie dywergencji wielomianowej KL między zmienną losową X …
1
Asymptotyczna gęstość niejednoznacznych gramatyk bezkontekstowych (CFG)
Jaki jest stosunek niejednoznacznych CFG do wszystkich CFG ? Ponieważ oba zestawy są w nieskończoność nieskończone, stosunek nie jest dobrze zdefiniowany. Ale co z asymptotyczną gęstością : limn ↦ ∞# niejednoznaczny CFG o rozmiarze < n# CFG o wielkości < nlimn↦∞# niejednoznaczny CFG wielkości<n# CFG wielkości<n\lim_{n \mapsto \infty}\frac {\# \text{ …
2
Przybliżenie problemów trudnych do # P
Rozważ klasyczny problem # P-zupełny nr 3SAT, tj. Policz liczbę wycen, aby uzyskać 3CNF z nnnzmienne zadowalające. Interesuje mnie przybliżalność addytywna . Najwyraźniej istnieje prosty algorytm do osiągnięcia2)n - 12n−12^{n-1}- błąd, ale jeśli k &lt;2)n - 1k&lt;2n−1k<2^{n-1}, czy można mieć skuteczny algorytm aproksymacyjny, czy ten problem jest również trudny do …
3
Posadzona klika w G (n, p), zmieniająca się p
W przypadku problemu sadzonej kliki należy odzyskać kkk-klinka posadzona na losowym wykresie Erdosa-Renyi G ( n , p )G(n,p)G(n,p). To było głównie rozpatrywanep =12)p=12p=\frac{1}{2}, w którym to przypadku wiadomo, że można rozwiązać czas wielomianowy, jeśli k &gt;n--√k&gt;nk > \sqrt{n} i przypuszczalnie trudne k &lt;n--√k&lt;nk< \sqrt{n}. Moje pytanie brzmi: co wiadomo …
2
Obliczanie przejściowego zakończenia / wyroku istnienia ścieżki
Było kilka pytań ( 1 , 2 , 3 ) na temat przechodniego uzupełniania, które zmusiły mnie do zastanowienia się, czy coś takiego jest możliwe: Załóżmy, że otrzymujemy wykres skierowany na dane wejściowe GsolG i chciałby odpowiedzieć na zapytania typu „(u,v)∈G+(u,v)∈sol+(u,v)\in G^+? ”, tzn. pytając, czy istnieje krawędź między dwoma …
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.