UWAGA : Pytanie zostało ponownie sformułowane w moich odpowiedziach: Zakładając, że możemy znaleźć najniższych przodków rodzeństwa w czasie , czy ANN można naprawdę wykonać w ?O ( 1 )O(1)O(1)O ( logn )O(logn)O(\log n) Czworoboki są wydajnymi wskaźnikami przestrzennymi. Mam łamigłówkę z...
Dobrze wiadomo, że do klasycznego uczenia się PAC, przykłady są konieczne, aby osiągnąć granicę błędu whp, gdzie jest wymiarem VC klasy koncepcyjnej.Ω ( d/ ε)Ω(re/ε)\Omega(d/\varepsilon)εε\varepsilonrered Czy wiadomo, że w przypadku agnostyki potrzebne są przykłady ?Ω ( d/...
Jestem ciekawy, czy ktoś mógłby polecić jakiś materiał uzupełniający do głębszego zrozumienia artykułu: „ Niektóre wyniki i problemy dotyczące nierówności typu kwantowego dzwonu - Tsirelson ”. W szczególności coś, co może nieco bardziej rozwinąć geometryczną interpretację nierówności typu Bell....
W artykule o tym samym tytule co tytuł tego pytania, autorzy opisują, jak zbudować nieblokowalną, liniową, wielowątkową operację CAS , używając tylko jednego słowa CAS. Najpierw wprowadzają operację podwójnego porównania-pojedynczej wymiany - RDCSS, jak następuje: word_t RDCSS(RDCSSDescriptor_t...
Monotoniczna formuła CNF z m terminami na n zmiennych ( ) jest formułą postaci , gdzie każdy jest OR pewnego podzbioru zmiennych i i wynosi od 1 do m . f ( x 1 , … , x n ) = ⋀ C i C i x 1 , … , x n i 1 mx1,…,xnx1,…,xnx_1,\ldots,x_nf(x1,…,xn)=⋀Cif(x1,…,xn)=⋀Cif(x_1,\ldots,x_n) = \bigwedge...
Czytam doskonały papier ankietowy Watrous na papierze na temat teorii złożoności kwantowej. Stwierdza w nim, że byłoby zaskakujące, gdyby okazało się, że problem z QMA miałby pustą obietnicę (tj. Być językiem). Dlaczego tak jest? Czy ma to związek z faktem, że k-lokalny problem hamiltonowski jest...
Czy istnieje w-bitowa struktura danych słowo-RAM z czasem O (1) na operację dla następującego problemu ?: Utrzymanie zestawu w-bitowych nieujemnych liczb całkowitych, które obsługują operacje add (x): dodaj x do zestawu remove (x): usuń x z zestawu odcisk palca (): zwraca odcisk palca zestawu....
Luźno mówiąc, dopasowanie wzorców permutacji dotyczy następujących problemów: Biorąc pod uwagę permutacje w S n i w , przy , czy zawiera podsekwencję o długości której elementy są uporządkowane według ?ππ\piSnSnS_nS m m ≤ n π τ m σσσ\sigmaSmSmS_mm≤nm≤nm\leq nππ\pi ττ\taummmσσ\sigma Na...
Oto pytanie „ścieżka B”, czy kiedykolwiek było. Podsumowanie: pierwsza rzecz, o której myślę, kiedy próbuję nadać semantykę programom niedeterministycznym, skutkuje semantyką, w której nie mogę udowodnić rzeczy o pętlach, które kończą tylko niedeterministyczność. Z pewnością ktoś wymyślił, co...
Czy ktoś może wskazać mi odniesienie do niezdefiniowalności modułu ciągłości funkcjonalnej w PCF? \ newcommand {\ bool} {\ mathsf {bool}}\newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer napisał bardzo fajny post na blogu , w którym szczegółowo omawia niektóre problemy,...
Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu. Zakładając problem FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q < 2 n P QN.= PQN=PQN = PQP., Q <...
Biorąc pod uwagę mieszany wykres z krawędziami i łukami , znajdź dopasowanie w które minimalizuje liczbę łuków w , gdzie jest uzyskiwane z przez kurczenie dopasowanych wierzchołków i usuwanie łuki równoległe.E A E G / M G / M GG = ( V, E, A )G=(V,E,A)G=(V,E,A)miEEZAAAmiEEG / MG/MG/MG /...
Chcę zacząć uczyć się o kodowaniu sieci: http://en.wikipedia.org/wiki/Network_coding Czy znasz jakieś dobre ankiety (np. Z ankiet i samouczków IEEE) na powyższe tematy. Znalazłem kilka kursów uniwersyteckich w Google, ale chciałbym uzyskać rekomendacje od osób, które już czytają i znają dobre...
Czy są stanowiska dla absolwentów studiów licencjackich lub magisterskich z historią badań naukowych do pracy jako naukowiec przed podjęciem pracy doktorskiej? TCS ma kulturę stanowisk podoktoranckich dla ostatnich absolwentów studiów doktoranckich w celu przeprowadzenia badań przed próbą...
Powiedzmy, że mamy wielościan w standardowej formie: A x = bx ≥ 0ZAx=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Czy są znane metody znalezienia hiperpłaszczyzny która dzieli wielościan w taki sposób, że liczba...
Katz i Lindell wspominają w swojej książce, że LFSR są okropne jako podstawa dla generatorów pseudolosowych i zalecają, aby nie były już używane (cóż, zalecają również, aby ludzie używali szyfrów blokowych zamiast szyfrów strumieniowych). Widzę jednak na przykład, że jeden z szyfrów w portfolio...
Załóżmy, że jest językiem boolowskim o skończonych łańcuchach ponad . Niech będzie liczbą łańcuchów w o długości . Dla funkcji od dodatnich liczb całkowitych do dodatnich liczb rzeczywistych, ma górną gęstość jeśli dla wszystkich wystarczająco dużych .L.L.LL n L n d ( n ) L d ( n ) L n ≤ 2 n d ( n...
Język jest w klasie iff istnieją dwa języki L1 \ w NP i L2 \ w coNP, tak że L = L1 \ cap L2D P L 1 ∈ N P L 2 ∈ c o N P L = L 1 ∩ L 2LLLDPDPDPL1∈NPL1∈NPL1 \in NPL2∈coNPL2∈coNPL2 \in coNPL=L1∩L2L=L1∩L2L = L1 \cap L2 Kanonicznym problemem z dopełnieniem DPDPDP jest SAT-UNSAT: biorąc pod uwagę dwa...
Stoję przed trudnym dylematem: Ukończyłem M.Tech w CS dwa lata temu, kończąc moją rozprawę w zakresie testowania VLSI. Chociaż podobała mi się moja praca, nie chcę wracać do doktoratu w tym zakresie - bardzo chciałem kontynuować kurs teoretyczny (w przybliżeniu / algorytmy online) jako sposób na...
Szukam pełnego tekstu wyniku kliknięcia Księżyca i Mosera z 1965 r. O klikach na wykresach (istnieją wykresy z liczbą maksymalnych wykładniczych klik w ). Zapora mojego uniwersytetu nie ma dostępu do konkretnego czasopisma. (W rzeczywistości podgląd zawiera kilka pierwszych zdań dowodu, ale potem...