Pytania otagowane jako reference-request

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

4
Rozpoczęcie pracy z rozwiązaniami SAT
Chcę zrobić pierwszy solver SAT. Znam konkurs SAT i konferencję SAT i jest tak wiele artykułów na ten temat. Jestem starterem, przytłoczonym starterem. Od czego powinienem zacząć W końcu chcę wprowadzić najnowocześniejsze rozwiązania. Chcę porady ekspertów, jak zacząć, żeby nie marnować czasu na rzeczy nieistotne zbyt wcześnie. Wielkie dzięki.
1
Hipoteza odbudowy i częściowe 2-drzewa
Przypuszczenie o rekonstrukcji mówi, że wykresy (z co najmniej trzema wierzchołkami) są określane jednoznacznie przez ich podgrupy usunięte z wierzchołków. Ta hipoteza ma pięć dekad. Przeszukując odpowiednią literaturę, odkryłem, że następujące klasy grafów są rekonstruowalne: drzewa wykresy odłączone, wykresy, których dopełnienie jest odłączone regularne wykresy Maksymalne wykresy zewnętrzne maksymalne wykresy …
4
Jaki jest najszybszy sposób sprawdzenia włączenia zestawu?
Biorąc pod uwagę podzbiorów z .nnnS1,…,SnS1,…,SnS_1,\ldots,S_n{1,…,d}{1,…,d}\{1,\ldots,d\} Sprawdź, czy istnieją zestawy z . (Jeśli tak, znajdź przykład, jeśli nie, po prostu powiedz „nie”)Si,SjSi,SjS_i,S_jSi⊊SjSi⊊SjS_i \subsetneq S_j Trywialne rozwiązanie tego problemu polega na przejściu wszystkich par zestawów i sprawdza włączenie pary w czasie , więc całkowity czas działania wynosi . Czy ten problem …
8
Obliczanie odległości Levenshteina szybko
Biorąc pod uwagę ogromną bazę dozwolonych słów (posortowane alfabetycznie) i słowo, znajdź słowo z bazy danych, która jest najbliższa podanemu słowu pod względem odległości Levenshteina. Naiwnym podejściem jest oczywiście po prostu obliczenie odległości levenshteina między danym słowem a wszystkimi słowami w słowniku (możemy przeprowadzić wyszukiwanie binarne w bazie danych przed …
1
Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski , …
2
Czy Cheeger jest stały -trwały?
Przeczytałem w niezliczonych artykułach, że wyznaczanie stałej Cheegera na wykresie to -hard. To wydaje się być twierdzeniem ludowym, ale nigdy nie znalazłem ani cytatu, ani dowodu na to stwierdzenie. Komu mam to przypisać? W starym artykule (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar potwierdza to twierdzenie „dla …
3
Jakie są relacje między tymi hipotezami w teorii drobnoziarnistej złożoności?
Teoria złożoności, poprzez takie koncepcje jak kompletność NP, rozróżnia problemy obliczeniowe, które mają względnie skuteczne rozwiązania, i te, które są trudne do rozwiązania. Złożoność „drobnoziarnista” ma na celu dopracowanie tego jakościowego rozróżnienia w ilościowy przewodnik co do dokładnego czasu potrzebnego na rozwiązanie problemów. Więcej informacji można znaleźć tutaj: http://simons.berkeley.edu/programs/complexity2015 Oto …
2
Rozpoznawanie węzłów jako dowód pracy
Obecnie bitcoin ma system proof of work (PoW) wykorzystujący SHA256. Inne funkcje skrótu wykorzystują wykresy wykorzystania systemu dowodu pracy, częściowe odwrócenie funkcji skrótu. Czy można zastosować problem decyzyjny w teorii węzłów, taki jak rozpoznawanie węzłów, i uczynić z niego funkcję dowodu pracy? Czy ktoś już to zrobił? Ponadto, kiedy będziemy …
5
Problemy z EXPSPACE
Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników. Jak dotąd je znalazłem i mam problem z rozwinięciem listy: uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem. problemy związane z systemami dodawania wektorów nieobserwowalne gry (patrz na przykład ten …
1
Języki rozpoznawane przez DFA wielkości wielomianowej
W przypadku ustalonego skończonego alfabetu język formalny L ponad Σ jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad ΣΣΣ\SigmaLL.LΣΣ\SigmaΣΣ\Sigma który akceptuje dokładnie .LL.L Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być rozpoznawane przez rodziny automatów wielkości, które rosną tylko wielomianowo wraz z długością słowa. …
6
Zaawansowane techniki określania dolnych granic złożoności
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby udowodnić dolne granice złożoności problemu w czasie? W …
5
Pakowanie prostokątów w wypukłe wielokąty, ale bez rotacji
Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i zapytano, ile identycznych kopii prostokąta można upakować w wielokącie. Uważam, …
2
Analiza kulek i pojemników w reżimie
mmmnnnm≫nm≫nm \gg nXiXiX_iiiiXmaxXmaxX_\maxXminXminX_\minXsec−maxXsec−maxX_{\mathrm{sec-max}}Xi−Xj∼N(0,2m/n)Xi−Xj∼N(0,2m/n)X_i - X_j \sim N(0,2m/n)|Xi−Xj|=Θ(m/n−−−−√)|Xi−Xj|=Θ(m/n)|X_i - X_j| = \Theta(\sqrt{m/n}) i,ji,ji,jXmax−Xmin=O(mlogn/n−−−−−−−−√)Xmax−Xmin=O(mlog⁡n/n)X_{\max} - X_{\min} = O(\sqrt{m\log n/n})n/2n/2n/2 pary rozłącznych pojemników. Ten (nie do końca formalny) argument prowadzi nas do oczekiwania, że ​​różnica między XmaxXmaxX_{\max} aXminXminX_{\min} to Θ(mlogn/n−−−−−−−−√)Θ(mlog⁡n/n)\Theta(\sqrt{m\log n/n}) z dużym prawdopodobieństwem. Interesuje mnie różnica między XmaxXmaxX_\max a Xsec−maxXsec−maxX_{\mathrm{sec-max}} . Przedstawiony …
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.