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...
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...
(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...
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...
Rozpoczynam doktorat tej jesieni i planuję pracować nad teorią złożoności. Tworzę listę ważnych prac, które powinien znać każdy teoretyk złożoności. Jakie dokumenty poleciłbyś osobie takiej jak ja? I proszę krótko wyjaśnić, dlaczego uważasz, że ten papier jest...
Jako student informatyki zapoznałem się z teorią gier, ale nie widziałem zbyt wielu szczegółów na ten temat. Szukałem w Google i przeglądałem książki o teorii gier, które potwierdziły jej wykorzystanie w informatyce. Rozpocząłem formalne studium teorii gier z perspektywy ekonomisty. Teraz chcę...
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...
Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne...
Pamiętam jakiś czas temu badanie lub artykuł, w którym twierdziłem, że większość przyspieszenia obserwowanego w programach komputerowych w ciągu ostatnich kilku dekad wynika z lepszych algorytmów niż z szybszego sprzętu. Czy ktoś zna badanie lub
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...
Wykazano, że propagacja przekonań jest bardzo skuteczną metodą dzięki badaniom w probabilistycznych modelach graficznych. Jednak nie wiem nic o BP, które byłoby porównywalne z metodami MCMC, w których możemy mieć w pełni wielomianowe losowe schematy aproksymacji (FPRAS) dla problemów z #...
tło : Kończę studia magisterskie z matematyki i rozpocznę doktorat z logiki w sierpniu. Im więcej logiki studiuję, tym bardziej teoretyczna jest informatyka, np. Teoria rekurencji, rachunek lambda, ale leżące u podstaw CS jest szczotkowane pod dywan. Moje główne obszary zainteresowań - teoria...
Niech będzie rodziną wszystkich języków Σ spełniającą właściwości pompowania zwykłych języków. Mianowicie: dla każdego L ∈ L jest N ∈ N każde słowo w ∈ L , | w | > N można zapisać w postaci w = x y z gdzie: 1. | y | > 0 , 2. | x y | ≤ N , 3. x y i...
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...
Jaka klasa złożoności jest powiązana z wyczerpującymi algorytmami wyszukiwania? (jeśli jest) Czy to jest NP czy PSPACE? Czy istnieją ograniczone modele obliczeń przechwytujące klasę wyczerpujących algorytmów wyszukiwania podobnych do modeli dla chciwego i dynamicznego...
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 ;...
Jak każdy wie, SAT jest kompletna dla wrt wielomian czasie wiele-jeden redukcje. Nadal jest kompletny z redukcjami wielokrotności A C 0 .NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Moje pytania brzmi: jaka jest minimalna wymagana głębokość redukcji? Bardziej formalnie, Co najmniej takie, że SAT jest...
Rozważmy nnn -wymiarowej przestrzeni {0,1}n{0,1}n\{0,1\}^n , niech ccc być liniowy ograniczenie formy 1 x 1 + 2 x 2 + 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k , gdzie a i ∈ R , x i ∈a1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ +...
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...
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ą...