Pytania otagowane jako reference-request

Jaka jest najbardziej znana złożoność zapytań algorytmu uczenia się Goldreich-Levin? Notatki z bloga Luca Trevisan , Lemma 3, stwierdza się jako . Czy jest to najlepiej znane pod względem zależności od n ? Będę szczególnie wdzięczny za odniesienie do źródła cytowanego!O ( 1 / ϵ4n logn )O(1/ϵ4nlog⁡n)O(1/\epsilon^4 n \log n)nnn …

14 cc.complexity-theory  reference-request  lg.learning  fourier-analysis 

Byłoby miło zebrać listę warunków, które sugerują, że bezkontekstowy język L jest regularny, tj. Warunki postaci: „jeśli dany CFG / PDA ma właściwość P, to jego języki są regularne” Właściwość P nie musi charakteryzować CFG generujących zwykłe języki. Ponadto P nie musi być rozstrzygalne, a P powinno „w jakiś sposób …

14 reference-request  fl.formal-languages  regular-language  context-free  survey 

Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej …

14 reference-request  open-problem  nt.number-theory  halting-problem  computability 

(już pytałem na głównej stronie , ale proszę również tutaj o lepszy zasięg, przepraszam) Ponieważ wiedziałem o zwięzłych strukturach danych, rozpaczliwie potrzebuję dobrego przeglądu najnowszych osiągnięć w tej dziedzinie. Poszukałem google i przeczytałem wiele artykułów, które mogłem zobaczyć na górze wyników wyszukiwania Google na prośby z góry mojej głowy. Nadal …

14 reference-request  ds.data-structures  advice-request  space-time-tradeoff 

Jaka jest złożoność obliczeniowa optymalizacji różnych funkcji w grupie jednolitej ?U(n)U(n)\mathcal{U}(n) Typowe zadanie, często wynikające z teorii informacji kwantowej byłoby maksymalizując ilość typu (lub wyższych wielomiany rzędu w U ) w stosunku do wszystkich macierze jednostkowe U . Czy tego rodzaju optymalizacja jest wydajna (być może w przybliżeniu) do obliczenia, …

14 cc.complexity-theory  reference-request  optimization  quantum-information 

Wdrażam część systemu, która wymaga pomocy. Dlatego kadruję go jako problem graficzny, aby uczynić go niezależnym od domeny. Problem: Otrzymujemy ukierunkowany wykres acykliczny . Bez utraty ogólności załóżmy, że G ma dokładnie jeden wierzchołek źródłowy s i dokładnie jeden wierzchołek tonący ; pozwolić P oznacza zbiór wszystkich skierowanych ścieżek z …

14 ds.algorithms  reference-request  co.combinatorics  graph-algorithms  directed-acyclic-graph 

To nie jest praca domowa, choć na to wygląda. Wszelkie odniesienia są mile widziane. :-) Scenariusz: Istnieje nnn różnych piłek i nnn różnych pojemników (oznaczonych od 1 do nnn , od lewej do prawej). Każda piłka jest rzucana niezależnie i równomiernie do koszy. Niech f(i)f(i)f(i) będzie liczbą kulek w iii …

14 reference-request  co.combinatorics  pr.probability 

Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście współrzędnych odbywa się cyklicznie przez współrzędne, ustalając wszystko oprócz wybranego i minimalizując wzdłuż …

14 ds.algorithms  reference-request  optimization  heuristics 

Niech G będzie n-węzłem niekierowanym grafem, a niech T będzie podzbiorem węzłów V (G) zwanym zaciskami . Zabezpieczenie odległości (G, T) jest wykresem H spełniającym tę właściwość reH.( u , v ) = dsol( u , v )reH.(u,v)=resol(u,v)d_H(u,v) = d_G(u,v) dla wszystkich węzłów u, v w T. (Należy zauważyć, że …

14 ds.algorithms  reference-request  graph-algorithms  planar-graphs 

Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.LL.L.L Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.L.nL.nL_nL.nL.nL_n{ 1 …

14 reference-request  fl.formal-languages  lower-bounds  grammars  context-free 

Algorytm węgierski jest kombinatorycznym algorytmem optymalizacyjnym, który rozwiązuje problem dwustronnego dopasowania maksymalnej masy w czasie wielomianowym i przewidywał późniejszy rozwój ważnej metody pierwotnej podwójnej . Algorytm został opracowany i opublikowany przez Harolda Kuhna w 1955 r., Który nadał mu nazwę „algorytm węgierski”, ponieważ algorytm był oparty na wcześniejszych pracach dwóch …

14 graph-theory  reference-request  graph-algorithms  linear-programming  primal-dual 

Kto wprowadził pomysł rekurencji ? Czy ktoś może wyjaśnić, skąd się wziął i jak wpłynął na informatykę?

14 reference-request  ho.history-overview  recursion 

Niedawno dowiedziałem się o chciwych przypuszczeniach dotyczących najkrótszego problemu superstrun . W tym problemie otrzymujemy zestaw ciągów s1, … , Sns1,…,sns_1,\dots, s_n i chcemy znaleźć najkrótszy superstrun sss tj. Taki, aby każdy sjasis_i pojawiał się jako podciąg sss . Problem ten jest trudny do przeprowadzenia w NP i po długiej …

14 reference-request  approximation-algorithms  greedy-algorithms 

f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f\colon\{-1,1\}^n \to \{-1,1\}iiiInfi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]Infi⁡[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)] \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})] x⊕ix⊕ix^{\oplus i}iiixxxfffMinInf[f]=defmini∈[n]Infi[f].MinInf⁡[f]=defmini∈[n]Infi⁡[f].\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f]. Biorąc pod uwagę parametr p∈[0,1]p∈[0,1]p\in[0,1] , wybieramy funkcję ppp losową fff , wybierając jej wartość na każdym z 2n2n2^n wejść niezależnie losowo, aby była równa 111 z prawdopodobieństwem ppp , a −1−1-1 z prawdopodobieństwem …

14 reference-request  pr.probability  boolean-functions 

Czy wiadomo, czy problem z oceną obwodu występuje w ? Co powiesz na (uniform )? N C 1 A L O g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Wiemy, że obwody o głębokości można oceniać za pomocą obwodów o głębokości gdzie jest stałą uniwersalną. Oznacza to, że obwody o …

14 cc.complexity-theory  reference-request  circuit-complexity