Jak dobrze zbadano następujący problem w TCS? (Przepraszam, jeśli opis problemu brzmi niejasno!) Biorąc pod uwagę model obliczeń MC (maszyna Turinga, automaty komórkowe, maszynę Kolmogorov-Uspenskii ... itd.) Oraz model hałasu, który mógłby wpływać na obliczenia MC, istnieje sposób na odzyskanie...
Niech będzie formułą CNF z n zmiennymi i klauzulami m . Niech t ∈ { 0 , 1 } n reprezentuje przypisanie zmiennej, a f φ ( t ) ∈ { 0 , … , m } zliczają liczbę klauzul spełnionych przez przypisanie zmiennej do φ . Następnie zdefiniuj Median-SAT jako problem obliczania mediany wartości f φ ( t ) dla...
Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu G=(V,E)G=(V,E)G = (V, E) . Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).GGGd=|E||V|d=|E||V|d = \frac{|E|}{|V|} Mam...
Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.LL.L.L Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla...
Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe...
Zadałem już to pytanie przy przepełnieniu stosu , ale może lepiej pasuje do tej witryny. Problemem jest: Mam N par liczb całkowitych bez znaku. Muszę je posortować. Wektor końcowy par należy posortować nie malejąco według pierwszej liczby w każdej parze i nieskończenie według drugiej liczby w...
Niech G będzie n-węzłem niekierowanym grafem, a niech T będzie podzbiorem węzłów V (G) zwanym zaciskami . Zabezpieczenie odległości (G, T) jest wykresem H spełniającym tę właściwość reH.( u , v ) = dsol( u , v )reH.(u,v)=resol(u,v)d_H(u,v) = d_G(u,v) dla wszystkich węzłów u, v w T. (Należy...
Dwie części TCS to algorytmy i złożoność. Upraszczając powiem, że algorytmy to badanie górnych granic, pokazujące, że możesz coś zrobić (przy danych ograniczonych zasobach), a złożoność polega na pokazaniu, że nie możesz tego zrobić bez minimalnych zasobów. Tak często problem algorytmiczny pojawia...
Istnieje piękne twierdzenie Koebe'a (patrz tutaj ), które stwierdza, że każdy płaski wykres można narysować jako wykres całowania dysków (bardzo romantyczny ...). (Mówiąc nieco inaczej, każdy wykres płaski można narysować jako wykres przecięcia dysków.) Twierdzenie Koebe'a nie jest łatwe do...
Interesuje mnie implementacja SM dla zadania LP, jednak słyszałem o możliwych pułapkach: książka Cormena mówi, że możliwe jest posiadanie danych wejściowych, które sprawią, że naiwna implementacja zachowa się w wykładniczym czasie. Słyszałem również, że naiwna implementacja może zapętlać dane. Czy...
Interesuje mnie optymalizacja wykresów przepływu danych i kontroli przepływu, a w szczególności bardziej złożonych obliczeniowo. Interesujące będzie jednak także zapoznanie się z najnowszymi wynalazkami w dziedzinie optymalizacji
Czy jest coś znanego na temat następującego problemu? Czy to w ogóle ma sens? Jak to jest nazywane? Czy jest to banalnie równoważne z jakimś innym problemem? Jaka jest złożoność czasu? Biorąc pod uwagę nieukierowany (ogólny / płaski / ograniczony / itd.) Wykres G = (V, E), znajdź maksymalny...
Greg Egan w swojej powieści „Dark Integers” (opowieść o dwóch wszechświatach z dwiema różnymi matematykami komunikującymi się poprzez dowodzenie twierdzeń o niespójności arytmetycznej) twierdzi, że możliwe jest zbudowanie komputera ogólnego przeznaczenia wyłącznie na istniejących routerach...
Ostatnio miałem do czynienia z algorytmami związanymi z kompresją i zastanawiałem się, który jest najlepszy współczynnik kompresji, jaki można osiągnąć dzięki kompresji danych bezstratnych. Jak dotąd jedynym źródłem, jakie mogłem znaleźć na ten temat, była Wikipedia: Bezstratna kompresja danych...
G=(V,E)G=(V,E)G=(V,E)minS⊂V e(S,Sc)min(|S|,|Sc|),minS⊂V e(S,Sc)min(|S|,|Sc|),\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},e(S,Sc)e(S,Sc)e(S,S^c)SSSScScS^c Bardziej konkretnie przypuszczać wiem średnica wynosi co najmniej (albo co najwyżej) . Co to mówi mi o przewodności, jeśli w ogóle? I...
Od dawna wiadomo, że przy dowolnym stopniu reuringu istnieje dobrze przedstawiona grupa, której problem słowny jest w tym stopniu. Moje pytanie brzmi, czy to samo dotyczy dowolnych stopni Turinga w czasie wielomianowym . W szczególności, biorąc pod uwagę rozstrzygalny zestaw, , czy istnieje...
Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście...
W tablicach skrótów, które rozwiązują kolizje za pomocą sondowania liniowego, w celu zapewnienia oczekiwanej wydajności , zarówno konieczne, jak i wystarczające jest, aby funkcja skrótu pochodziła z 5-niezależnej rodziny. (Wystarczalność: „Sondowanie liniowe ze stałą niezależnością”, Pagh i in. ,...
Istnieje wiele problemów w kombinatorycznej teorii reprezentacji i geometrii algebraicznej, dla których nie jest znana formuła dodatnia. Myślę o kilku przykładach, ale pozwólcie, że obliczę współczynniki Kroneckera jako mój przykład. Zwykle pojęcie „formuły dodatniej” nie jest precyzyjnie...
Beigi, Shor i Watrous mają bardzo ładny artykuł na temat mocy kwantowych dowodów interaktywnych z krótkimi wiadomościami. Rozważają trzy warianty „krótkich wiadomości”, a konkretny, na którym mi zależy, to ich drugi wariant, w którym można wysłać dowolną liczbę wiadomości, ale całkowita długość...