Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Wykorzystanie dodatkowej mocy metody negatywnego przeciwnika
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 wszystkie wystąpienia 0 są daleko od wszystkich 1 wystąpień, wówczas metoda przeciwnika …
3
W jaki sposób modele hiper obliczeń pokonują problem zatrzymania?
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 Turinga. Nazwij to „supermocarstwem”: hiperkomputer z supermocarstwem może zdecydować, czy zakończy się jakakolwiek standardowa …
1
Analiza kulek i pojemników w systemie m >> n.
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(log⁡n)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 szczegółowo, pokazując, że wraz ze wzrostem mmm …
3
Jak trudna jest dokładna symulacja algorytmów i powiązana z nią operacja na klasach złożoności
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 istnieją powody, by sądzić, że to zadanie jest trudne dla P-Space, robi coś …
2
Równoważność śladu vs równoważność LTL
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 w stanie tego wyobrazić, czy może …
5
Niejednoznaczność i logika
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 maszynę istnieje co najwyżej k różnych przebiegów do zaakceptowania w .wwwkkkwwwkkkwww Pojęcie to …
2
Sparametryzowana złożoność numeru przecięcia wykresu
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 najwyżej różnych zamkniętych sąsiedztw wierzchołków (dwa wierzchołki mają te same sąsiedztwa …
1
Jakie są granice obliczeń w tym wszechświecie?
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 użyte wszystkie atomy we wszechświecie.ππ\pi Jakie są zatem …
2
Czy istnieje algorytm do skutecznego utrzymywania informacji o połączeniach dla DAG w przypadku wstawiania / usuwania?
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 Glink(G,a,b)link(G,a,b)link(G,a,b)aaabbbGGG : Usuwa krawędź od a do b w Gunlink(G,a,b)unlink(G,a,b)unlink(G,a,b)aaabbbGGG : Dodaje wierzchołek do Gadd(G,a)add(G,a)add(G,a) …
3
Zwięzłe badanie struktur danych?
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ą . Czy istnieje „zwięzła” struktura danych, która wymaga przechowywania …
2
Teoria kategorii, złożoność obliczeniowa i połączenia kombinatoryczne?
Próbowałem przeczytać „ Perły projektowania algorytmu funkcjonalnego ”, a następnie „ Algebra programowania ”, i istnieje oczywista zgodność między rekurencyjnie (i wielomianowo) zdefiniowanymi typami danych i obiektami kombinatorycznymi, mającymi tę samą definicję rekurencyjną, a następnie prowadzącą do tych samych formalnych szeregów mocy (lub funkcji generujących), jak pokazano we wstępach do …
4
Zastosowania struktur metrycznych na posetach / sieciach w teorii CS
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 największą dolną granicę.x∨yx∨yx \vee yXXXx∧yx∧yx \wedge y Krata to …
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.