Pytania otagowane jako reference-request

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

5
Ciekawy o komputerowych dowodach kompletności NP
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be …
3
Uzasadnianie naukowcom asymptotycznej analizy najgorszego przypadku
Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego przypadku dla dolnych granic. Czy istnieją odniesienia do długości artykułów, które uzasadniają dolne granice i asymptotyczną …
1
Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym?
Podczas majstrowania przy niekanonicznym analizowaniu LR wymyśliłem metodę analizy (z tabelami o nieskończonych rozmiarach, co czyni ją nieco niepraktyczną ), która jest w stanie przeanalizować dokładnie jednoznaczne gramatyki w czasie , i zastanawiałem się, czy można to zrobić lepiej :O(n2)O(n2)O(n^2) Czy wszystkie jednoznaczne gramatyki można analizować w czasie liniowym? Jestem …
1
Zjednoczenie i eliminacja Gaussa
Czy ktoś zna odniesienia, które precyzyjnie określają związek między algorytmem unifikacji a eliminacją Gaussa? Szczególnie interesuje mnie związek między podstawieniami trójkątnymi a rozkładami LU. Wayne Snyder i Jean Gallier wspominają o tej analogii, przekazując w swojej pracy, Revisited Unification Higher Order: Complete Set of Transformations .
4
Artykuły na temat związku między złożonością obliczeniową a geometrią / topologią algebraiczną?
Zastanawiałem się, jakie artykuły powinienem przeczytać, aby zrozumieć to pytanie Nieoczekiwane połączenie z innymi dziedzinami matematyki, takimi jak geometria algebraiczna lub wyższa kohomologia. Być może nawet dziedzina matematyki nie została jeszcze rozwinięta. Być może ktoś opracuje zupełnie nowy kierunek matematyki, aby poradzić sobie z pytaniem P kontra NP. -Od Fortnow …
3
Dodawanie liczb całkowitych reprezentowanych przez ich faktoryzację jest tak trudne, jak faktoring? Wniosek o referencję
Szukam odwołania do następującego wyniku: Dodanie dwóch liczb całkowitych do reprezentacji faktoryzowanej jest tak trudne, jak dodanie dwóch liczb całkowitych do zwykłej reprezentacji binarnej. (Jestem prawie pewien, że tam jest, ponieważ zastanawiałem się nad tym, a potem byłem podekscytowany, gdy w końcu zobaczyłem to w druku). Problemem jest „dodanie dwóch …
1
Maksymalny przepływ dzięki Ford-Fulkerson i DFS
To pytanie dotyczy złożoności czasowej algorytmu maksymalnego przepływu Forda-Fulkersona podczas korzystania z DFS w celu znalezienia ścieżek rozszerzających. Istnieje dobrze znany przykład pokazujący, że przy użyciu DFS można potrzebować liniowej liczby iteracji w maksymalnym przepływie, patrz na przykład strona Wikipedii, do której prowadzi link powyżej. Jednak tak naprawdę nie przekonuje …
3
Źródło edukacyjne lub ankieta na temat analizy programu półfinałowego?
Podczas projektowania algorytmów aproksymacyjnych czasami rozwiązuje się program półfinałowy, po którym następuje etap zaokrąglania. Często ilustrowanym przykładem jest Max-Cut. (Zobacz np. Algorytmy aproksymacji Vijay Vazirani.) Czy istnieją dobre źródła edukacyjne lub ankiety wykraczające poza problem Max-Cut w celu wyjaśnienia bardziej złożonych algorytmów zaokrąglania i technik wykorzystywanych do ich analizy? Mam …
7
Znajdowanie bliźniaczych wierzchołków na wykresach
Niech będzie wykresem. Przez wierzchołek , określa za (otwarty) sąsiedztwie w . To znaczy, . Zdefiniuj dwa wierzchołki w aby były bliźniakami, jeżeli i mają ten sam zestaw sąsiadów, to znaczy, jeśli .G=(V,E)G=(V,E)G=(V,E)x∈Vx∈Vx\in VN(x)N(x)N(x)xxxGGGN(x)={y∈V|{x,y}∈E}N(x)={y∈V|{x,y}∈E}N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}u,vu,vu,vGGGuuuvvvN(u)=N(v)N(u)=N(v)N(u)=N(v) Biorąc pod uwagę wykres na wierzchołkach i krawędziach jako dane wejściowe, jak …
2
Czy można zaniedbać koszt GC, analizując czas działania najgorszych struktur danych określonych w zbędnym języku programowania?
Właśnie zdałem sobie sprawę, że zakładam, że odpowiedź na moje pytanie brzmi „tak”, ale nie mam dobrego powodu. Wyobrażam sobie, że może istnieje śmieciarz, który prawdopodobnie wprowadza tylko spowolnienie w najgorszym przypadku. Czy istnieje ostateczne odniesienie, które mogę zacytować? W moim przypadku pracuję nad czysto funkcjonalną strukturą danych i używam …
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.