Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

3
Izomorfizm podsgrafu z drzewem
Jeśli mamy duży (skierowany) wykres i mniejsze ukorzenione drzewo H , jaka jest najbardziej znana złożoność znajdowania podgraphów G izomorficznych względem H ? Zdaję sobie sprawę z wyników dla izomorfizmu poddrzewa, w którym zarówno G, jak i H są drzewami, a także gdzie G jest płaski lub ma ograniczoną szerokość …
2
Jaki jest najszybszy algorytm do obliczania rangi macierzy prostokątnej?
Biorąc pod uwagę macierz m×nm×nm \times n (przy założeniu, że m≥nm≥nm \ge n ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn? Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany czasowo O ( m n ω - 1 …
1
Kurs do nauki złożoności algebraicznej
Chcę się dowiedzieć o algorytmach algebraicznych i złożoności tysiąca. W szczególności interesuje mnie PIT. Czy istnieje zestaw notatek z wykładów, książek, prac i ankiet dla studentów, którzy przeczytali standardowy podręcznik o teorii, taki jak książka Sipsera lub podręcznik złożoności Arory-Baraka. Zestaw referencji będzie zawierał najnowsze zaawansowane wyniki.
2
Teoretyczne gwarancje dla czasów działania metod propagowania przekonań?
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 # P-zupełnością. Czy ktoś mógłby wskazać mi jakieś odniesienia?
6
Geometryczna interpretacja obliczeń
Będąc fizyką, zostałem przeszkolony, aby patrzeć na wiele problemów z geometrycznego punktu widzenia. Na przykład geometria różniczkowa rozmaitości w układach dynamicznych itp. Kiedy czytam podstawy informatyki, zawsze staram się znaleźć interpretacje geometryczne. Jak wiarygodna geometryczna interpretacja zbiorów rekurencyjnie wyliczalnych (pracowałem nad częścią, w której próbowałem połączyć je z geometrią algebraiczną, …
1
Jaka jest minimalna wymagana głębokość redukcji dla NP-twardości SAT?
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 redukcją N P- twardą wr A C 0 d wielokrotności jeden?reddN …
2
Podejścia do GI inspirowane problemem węzłów
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 wyniki dla ?G IsoljaGI Byłoby to szczególnie pomocne, aby wiedzieć, czy …
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.