Pytanie główne / ogólne Niech LLL będzie językiem. Zdefiniuj języki LiLiL_i pomocą L0=LL0=LL_0 = L i Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} dla i≥1i≥1i \geq 1 . Rozważmy L = ⋃ l i . Tak więc wielokrotnie „osadzić” L w siebie, aby uzyskać L...
W obliczeniach rozproszonych problem konsensusu wydaje się być jednym z głównych tematów, który przyciągnął intensywne badania. W szczególności artykuł „Niemożność rozproszonego konsensusu z jednym wadliwym procesem” otrzymał nagrodę PODC Influential Paper Award 2001 . Dlaczego więc problem...
Obliczanie stałej Cheegera na wykresie , znanej również jako stała izoperymetryczna (ponieważ jest to zasadniczo minimalny stosunek powierzchni do objętości), jest znana jako NP-zupełna. Ogólnie jest to przybliżone. Chciałbym się dowiedzieć, czy dokładne algorytmy wielomianowe są znane dla...
Matryca jest nazywana całkowicie regularną, jeśli wszystkie jej kwadratowe submatrice mają pełną rangę. Takie matryce zastosowano do budowy superkoncentratorów. Jaka jest złożoność decyzji, czy dana matryca jest całkowicie regularna w stosunku do racjonalności? Ponad skończonymi polami? Mówiąc...
Interesuje mnie następujący problem: Biorąc pod uwagę zestaw X i podzbiory X_1, ..., X_n z X, znajdź kolorystykę elementów X za pomocą k kolorów, tak że wszystkie elementy w każdym X_i mają różne kolory. Mówiąc dokładniej, przyjmuję przypadek, w którym wszystkie X_i mają rozmiar k. Czy jest to...
Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2. Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? 1 , 2 , … , n1,2),…,n{1,2,\ldots,n} Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna...
Chciałbym wiedzieć, czy w TCS istniały przypuszczenia, które od dawna nie zostały udowodnione, a które później udowodniono na podstawie innego twierdzenia, które mogłyby być łatwiejsze do udowodnienia.
W latach 90. widzę wiele badań nad hiper-obliczeniami , ale w ostatnich latach wydaje się, że niewiele jest pracy na ten temat. Czy to prawda, że badania w tej dziedzinie wygasły? Jeśli tak, jakie mogą być tego przyczyny? Czy ten obszar przekonująco okazał się mało...
Chciałbym dowiedzieć się o złożoności parametryzowanej (zarówno po stronie algorytmicznej, jak i po stronie twardości). Jakie książki / notatki z wykładów mogę przeczytać na ten
Problemem zatrzymania maszyn Turinga jest być może kanoniczny nierozstrzygalny zestaw. Niemniej jednak dowodzimy, że istnieje algorytm decydujący o prawie wszystkich jego wystąpieniach. Problem zatrzymania należy zatem do rosnącej liczby osób wykazujących zjawisko teorii złożoności „czarnej...
Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym...
Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o ZmZm\mathbb{Z}_m , pierścień reszt modulo mmm . Liczba mmm może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu). O ile mi wiadomo (czytaj poniżej),...
Ostatnie podejście do tworzenia zdecentralizowanej waluty internetowej, zwanej Bitcoin , wzbudza pewne zainteresowanie. Celem jest posiadanie sposobu na przelewanie waluty bez centralnego organu i bez podwójnych wydatków lub fałszowania. Ich podejście polega na tym, że wszystkie węzły w sieci...
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ść...
2 pytania do geometrii obliczeniowej lub algebraistów: Właśnie zaczynam nurkować w geometrii obliczeniowej i uwielbiam ją =) Próbuję przeczytać słynny artykuł Guibasa i Stolfiego zatytułowany „Prymitywy do manipulowania ogólnymi poddziałami i obliczaniem diagramów Voronoi” w celu...
Czy to prawda, że w hierarchii wielomianowej występują problemy, które można rozwiązać w czasie O(nk)O(nk)O(n^k) (przez naprzemienną maszynę Turinga na pewnym poziomie hierarchii wielomianowej), których nie można rozwiązać w O(nk−1)O(nk−1)O(n^{k-1}) na żadnym poziomie hierarchia wielomianowa?...
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...
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 automatyczne dowodzenie twierdzeń i przeszukiwanie dowodów jest łatwiejsze w liniowych i innych zdaniach logiki strukturalnej pozbawionej kurczenia? Gdzie mogę przeczytać więcej o automatycznym dowodzeniu twierdzeń w tych logikach i roli skurczu w poszukiwaniu
Czy są jakieś algorytmy rozwiązywania SAT, które nie są oparte na DPLL? Czy wszystkie algorytmy używane przez solwery SAT są oparte na