Ponieważ termin jest przeciążony, najpierw krótka definicja. Poset jest zbiorem XXX wyposażonym w częściowy porządek ≤≤\le . Biorąc pod uwagę dwa elementy a,b∈Xa,b∈Xa,b \in X , możemy zdefiniować (złączenie) jako ich najmniejszą górną granicę w i podobnie zdefiniować (spełnić) (połączyć) jako...
Artykuł Fischera w tym miesiącu przypomniał mi, jak mało wiem o sztuce zwięzłych struktur danych i algorytmów ich używania. Dla tych, którzy nie wiedzą o zwięzłych strukturach danych: Biorąc pod uwagę kombinatoryczną strukturę, z (n) odrębnymi konfiguracjami i znaną „użyteczną” reprezentacją ....
Jak dobrze wiadomo PARITY nie może być wykonane w obwodach o stałej wielkości o wielkiej wielkości, aw rzeczywistości obwody stałe wymagają liczby EXP bramek. Co z obwodami QUANTUM? a) Czy PARITY można wykonać za pomocą obwodu kwantowego, który ma stałą głębokość i liczbę bramek? b) Czy moje...
Rozumiem, że kompletność Turinga wymaga nieograniczonej pamięci i nieograniczonego czasu. Jednak w tej usłudze jest skończona ilość atomów, co ogranicza pamięć. Na przykład, chociaż jest irracjonalne, nie ma sposobu na przechowywanie więcej niż pewnej liczby cyfr, nawet jeśli do tego celu zostały...
Biorąc pod uwagę ukierunkowany wykres acykliczny, G(V,E)G(V,E)G(V,E) , czy można skutecznie obsługiwać następujące operacje? : Określa, czy w G istnieje ścieżkaod węzła a do węzła bisConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b)GGGaaabbb : Dodaje krawędź od a do b na wykresie...
Co jeśli wiadomo o sparametryzowanej złożoności obliczania numeru przecięcia wykresu (najmniejszej liczby klików potrzebnych do pokrycia wszystkich jego krawędzi)? Od dawna wiadomo, że jest NP-kompletny, i oczywiście FPT, ponieważ ma jądro: jeśli możesz pokryć wykres klikami, to istnieje co...
Mój pomysł na wymarzoną karierę to kariera w badaniach przemysłowych, w której można zmierzyć się z problemami, które są trudne, a także mieć praktyczne zastosowanie. W związku z tym, czy doktorat z TCS (interesują mnie takie tematy jak algorytmy rozproszone / równoległe, algorytmy online) to zły...
jak można pokazać, jaki jest związek między „hipotezą o unikalnych grach” a „twierdzeniem PCP”? jak tłumaczyć „hipoteza o unikalnych grach” jest silniejszą formą „twierdzenia
W teorii automatów (automaty skończone, automaty wypychające, ...) i złożoności występuje pojęcie „dwuznaczności”. Automat jest dwuznaczny, jeśli istnieje słowo z co najmniej dwoma odrębnymi przebiegami akceptującymi. Maszyna jest k- dwuznaczna, jeśli dla każdego słowa w zaakceptowanego przez...
Szukam prostego przykładu dwóch systemów przejściowych, które są równoważne LTL, ale nie równoważne. Przeczytałem dowód na to, że Trace Equivalence jest lepszy niż LTL Equivalence w książce „Principles of Model Checking” (Baier / Katoen), ale nie jestem pewien, czy naprawdę to rozumiem. Nie jestem...
Hyperkomputer odnosi się do modeli obliczeniowych, których nie można symulować za pomocą maszyn Turinga. (Hyperkomputery niekoniecznie są fizycznie możliwe do zrealizowania!) Niektóre hiperkomputery mają dostęp do zasobu, który pozwala na rozwiązanie problemu zatrzymania dla standardowych maszyn...
Powszechnie wiadomo, że jeśli wrzucisz n piłek do n pojemników, najprawdopodobniej w najbardziej załadowanym pojemniku będą znajdować się kulki O(logn)O(logn)O(\log n) . Ogólnie można zapytać o m>nm>nm > n piłek w nnn pojemnikach. Artykuł z RANDOM 1998 autorstwa Raaba i Stegera analizuje to...
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...
Mam dwie partycje [1…n][1…n][1 \ldots n] i szukam odległości edycji między nimi. W ten sposób chcę znaleźć minimalną liczbę pojedynczych przejść węzła do innej grupy, które są niezbędne do przejścia z partycji A na partycję B. Na przykład odległość od {0 1} {2 3} {4}do {0} {1} {2 3 4}wynosi...
Negatywna metoda przeciwnika ( A D V±ZAreV.±ADV^\pm ) to SDP, który charakteryzuje złożoność kwantowych zapytań. Jest to uogólnienie powszechnie stosowanej metody przeciwnika ( ) i pokonuje dwie bariery, które utrudniały metodę przeciwnika:A D VZAreV.ADV Bariera testowania właściwości: jeśli...
Niedawno przeczytałem dowód, który miał wykazać, że problem był silnie NP-trudny, po prostu redukując go (w czasie wielomianowym) z problemu silnie NP-trudnego. To nie miało dla mnie żadnego sensu. Pomyślałbym, że musisz pokazać, że wszelkie liczby użyte w redukcji i przypadki problemu, do którego...
Ostatnio byłem na konferencji wspieranej przez ACM. Podczas bankietu organizatorzy konferencji opowiedzieli nam o przyszłości i przeszłości konferencji. Powiedzieli nam, że podczas edycji konferencji w 2010 roku strata wyniosła 5000 $. Pokazali nam budżet poprzedniej konferencji, gdzie mogliśmy...
Jakie są najbardziej znane metody cyklicznego splotu długości na małym polu, tj. Kiedy | F | « N ? Szczególnie interesują mnie pola o stałej wielkości, a nawet F = F 2 . Doceniane są ogólne stwierdzenia i referencje dotyczące skuteczności asymptotycznej.nnn|F|≪n|F|≪n|\mathbb{F}| \ll...
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...
jest zbiorem punktów na płaszczyźnie. Losowy punkt x ∉ S jest podany na tej samej płaszczyźnie. Zadanie to rozwiązać wszystkie y ∈ S przez euklidesową odległość pomiędzy x i y .SS.Sx∉Sx∉S.x \notin Sy∈Sy∈S.y \in Sxxxyyy Podejście no-mózg jest obliczenie odległości między i Y dla wszystkich y ∈ S ,...