W jaki sposób mogę ustalić liczbę unikalnych prostych ścieżek na niekierowanym wykresie? Albo dla określonej długości, albo w zakresie dopuszczalnych długości. Przypomnij sobie, że prosta ścieżka to ścieżka bez cykli, więc mówię o policzeniu liczby ścieżek bez...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Nigdy wcześniej nie widziałem algorytmu z logiem w mianowniku i zastanawiam się, czy w tym formularzu są jakieś przydatne algorytmy? Rozumiem wiele rzeczy, które mogą powodować mnożenie współczynnika logu w czasie wykonywania, np. Algorytmy sortowania lub oparte na drzewach, ale co może powodować...
XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu...
Czy wszystkie funkcje, których waga Fouriera jest skoncentrowana na małych zestawach (lub terminach o niskim stopniu), są obliczane przez obwody
Powszechnie wiadomo, że komputery kwantowe są silniejsze niż ich klasyczne odpowiedniki pod względem złożoności zapytań . Czy istnieją inne modele (naturalne lub sztuczne), które są ściśle kwantowe i klasyczne pod względem złożoności zapytań? Separacja może być włączona specyficzne...
Rozważmy język składający się ze wszystkich ciągów -lettera nad tak aby żadne dwie litery nie były równe:L k - d i s t i n c tLk−distinctL_{k-distinct} k kkΣΣ\Sigma L k - d i s t i n c t : = { w = σ 1 σ 2 . . . σ k ∣ ∀ i ∈ [ k ] : σ i ∈ Σ and ∀ j ≠ i : σ j ≠ σ i...
Praca bezpośrednio ze złożonością czasu lub dolnymi granicami obwodu jest przerażająca. Dlatego opracowujemy narzędzia takie jak złożoność zapytań (lub złożoność drzewa decyzyjnego), aby uzyskać kontrolę nad dolnymi granicami. Ponieważ każde zapytanie zajmuje co najmniej jeden krok jednostkowy, a...
Teoria kategorii i algebra abstrakcyjna zajmują się sposobem łączenia funkcji z innymi funkcjami. Teoria złożoności dotyczy tego, jak trudna jest funkcja do obliczenia. Dziwne jest dla mnie to, że nie widziałem, aby ktoś łączył te kierunki studiów, ponieważ wydają się one takimi naturalnymi parami....
Jaka jest złożoność (na standardowej całkowitej liczbie pamięci RAM) obliczania standardowej dyskretnej transformaty Fouriera wektora nnn liczb całkowitych? Klasyczny algorytm szybkich transformacji Fouriera , niewłaściwie [1] przypisany Cooleyowi i Tukeyowi, jest zwykle opisywany jako działający...
Czy podjęto prace nad tym, jak złożoność przypadkowych instancji # 2-SAT zmienia się w zależności od gęstości klauzuli? To znaczy: w jaki sposób trudność liczenia satysfakcjonujących rozwiązań dla losowo generowanej instancji 2-SAT różni się w zależności od gęstości klauzuli? W szczególności, czy...
Załóżmy, że jest drzewem o stałym stopniu, którego struktury nie znamy. Problem polega na wyprowadzeniu drzewa T przez zadawanie zapytań o postać: „Czy węzeł x leży na ścieżce od węzła a do węzła b ?”. Załóżmy, że na każde zapytanie można odpowiedzieć w stałym czasie przez wyrocznię. Znamy wartość...
W oficjalnym opisie problemu Clay dla P kontra NP stwierdzono, że wynikałoby z pokazania, że „każdy język w E [klasa języków rozpoznawalnych w czasie wykładniczym z deterministyczną maszyną Turinga] może być obliczony przez rodzinę obwodów boolowskich < B n > , tak że co najmniej jedno n ,...
Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie. Czy to ciekawe podejście do separacji klasowej? Motywem tego pytania jest to, że musimy powiedzieć istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości...
Treewidth odgrywa ważną rolę w algorytmach FPT, częściowo dlatego, że wiele problemów jest FPT parametryzowanych przez treewidth. Powiązanym, bardziej ograniczonym pojęciem jest szerokość ścieżki. Jeśli wykres ma szerokość ścieżki , ma również szerokość co najwyżej , podczas gdy w kierunku...
Próbuję rozwiązać konkretny problem i pomyślałem, że mogę go rozwiązać za pomocą teorii automatów. Zastanawiam się, jakie modele automatów mają rozstrzygające rozstrzyganie w czasie wielomianowym? tzn. jeśli masz maszyny M.1, M2)M.1,M.2)M_1, M_2 , możesz sprawdzić, czy wydajnie.L ( M1) ⊆ L (...
EDYCJA (22 sierpnia 2011 r.): Jeszcze bardziej upraszczam pytanie i wyróżniam je. Być może to prostsze pytanie będzie miało łatwą odpowiedź. Przekreślę także wszystkie części pierwotnego pytania, które nie są już istotne. (Podziękowania dla Stasysa Jukny i Ryana O'Donnella za częściową odpowiedź...
Część pracy nad czułością w porównaniu do czułości bloku miała na celu zbadanie funkcji z możliwie największą luką między s(f)s(f)s(f) i bs(f)bs(f)bs(f) w celu rozstrzygnięcia przypuszczenia, że bs(f)bs(f)bs(f) jest tylko wielomianowo większy niż s(f)s(f)s(f) . Co z przeciwnym kierunkiem? Co...
Zwiastun Ponieważ problem jest długotrwały, tutaj jest szczególny przypadek, który oddaje jego istotę. Problem: Niech A będzie algorytmem detrministycznym dla 3-SAT. Czy problem polega na całkowitej symulacji algorytmu A (na każdym wystąpieniu problemu). P-Space trudne? (Dokładniej, czy...
I powiedziano, że istnieją dobre wielomianowe algorytmy czasu dla zbliżenia liczbę prostych odcinków w skierowanej wykresie począwszy od danego wierzchołka do danego zakończony wierzchołek T . Czy ktoś zna dobre referencje na ten temat?sssttt Tło: zliczanie dokładnej liczby ścieżek na ogólnym...