Teoretyczne informatyka

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

3
Czy każdy zachłanny algorytm ma strukturę matroidu?
Jest dobrze znane, że dla każdego matroid M.MM żadna funkcja ciężaru www , nie wychodzi algorytm GreedyBasis (M, w )GreedyBasis(M,w)\mbox{GreedyBasis}(M,w) , która zwraca na podstawę maksymalny ciężar MMM . Czy zatem odwrotny kierunek jest również prawdą? Oznacza to, że jeśli istnieje jakiś chciwy algorytm, musi również istnieć pewna struktura matroidu.
1
Czy występują problemy z „NP-Intermediate-Complete”?
Załóżmy, że P NP.≠≠\ne Twierdzenie Ladnera mówi, że istnieją problemy pośrednie NP (problemy w NP, które nie są ani w P, ani w NP-Complete). Znalazłem w Internecie kilka zawoalowanych odniesień, które sugerują (myślę), że istnieje wiele „poziomów” wzajemnie redukowalnych języków w ramach NPI, które zdecydowanie nie wszystkie się zlewają. Mam …
1
Znalezienie najkrótszej ścieżki w obecności cykli ujemnych
Biorąc pod uwagę ukierunkowany wykres cykliczny, na którym ciężar każdej krawędzi może być ujemny, koncepcja „najkrótszej ścieżki” ma sens tylko wtedy, gdy nie ma żadnych cykli ujemnych, iw takim przypadku można zastosować algorytm Bellmana-Forda. Jestem jednak zainteresowany znalezieniem najkrótszej ścieżki między dwoma wierzchołkami, która nie wymaga cyklizacji (tj. Pod warunkiem, …
1
Czy call / cc Scheme może implementować wszystkie znane struktury przepływu sterowania?
Strona „Advanced Scheme: Some Naughty Bits” stanowi: Kontynuacje są potężnym konstruktem sterowania przepływem, z którego można wyprowadzić prawie każdą inną strukturę przepływu sterowania [...]. Myślałem, że Scheme call/cc, związane (*) z operatorem J Petera Landina, może być wykorzystane do wdrożenia dowolnej znanej struktury przepływu sterowania? W „strukturze kontroli przepływu” szczególnie …
2
Dlaczego stan FSM tradycyjnie oznacza
Ucząc, jak implementować FSM przy użyciu synchronicznych obwodów logicznych, zauważyłem intrygujący zbieg okoliczności: zarówno w teoretycznym świecie CS, jak iw świecie elektrotechniki „stan” jest zwykle oznaczany jako (i przestrzeń stanu Q ). Najpierw zapytałem na EE.sx , ale potem, badając nieco ten temat, odkryłem, że nawet oryginalny papier Turinga z …
1
Dlaczego te dwie definicje PPAD są równoważne?
Klasa złożoności PPAD jest zwykle definiowana przez stwierdzenie, że Koniec linii jest kompletny z PPAD. Koniec linii to problem z wyszukiwaniem. Dane wejściowe składają się z ukierunkowanego wykresu, w którym każdy węzeł ma co najwyżej stopień i stopień 1. Wykres jest podawany przez funkcję obliczeniową wielomianową która zwraca poprzednika i …
3
Gra na kilku wykresach
Rozważ następującą grę na ukierunkowanym wykresie ważonym solGG z chipem w pewnym węźle. Wszystkie węzły solGG oznaczone są literą A lub B. Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B). Początkowo Alice i Bob mają odpowiednio mZAmAm_A i mbmBm_B dolarów. …
1
Deterministyczna redukcja błędów, najnowocześniejszy?
Załóżmy, że jeden ma losowy (BPP) algorytm ZAAA przy użyciu rrr bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do 1 - δ1−δ1-\delta dla każdego wybranego δ> 0δ>0\delta>0 Niezależne przebiegi + większość głosów: przebieg ZAAA niezależnie T.= Θ ( log( 1 / δ)T=Θ(log⁡(1/δ)T=\Theta(\log(1/\delta) razy ) i przyjmowanie większości głosów …
1
Liczba 4 cykli
Niech C4C4C_4 będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres GGG z nnn wierzchołkami i krawędziami m, powiedz m>nn−−√m>nnm>n\sqrt n , ileistniejeC4C4C_4? Czy jest na to dolna granica?
3
Czuję się niezadowolony po każdym przesłaniu
Jestem studentem trzeciego roku na uniwersytecie „20 najlepszych”, który pracuje nad złożoną złożonością (dużo zabawy z 3-SUM, OV i zwykłymi popularnymi przypuszczeniami dotyczącymi twardości). W ciągu ostatniego roku byłem dość produktywny i otrzymałem 3 zaakceptowane prace i dwie przesłane prace. Wszystko po to, by powiedzieć, że jestem dość doświadczonym absolwentem …
1
Co sprawia, że ​​język (i jego system typów) jest w stanie udowodnić twierdzenia o swoich terminach?
Niedawno próbowałem zaimplementować Cedille-Core Aarona , minimalistyczny język programowania zdolny do udowodnienia twierdzeń matematycznych na temat własnych terminów. Udowodniłem również indukcję dla typów danych zakodowanych na λ, co wyjaśniło, dlaczego jego rozszerzenia byłyby konieczne. Nie mówiąc już o tym, wciąż zastanawiam się, skąd pochodzą te rozszerzenia. Dlaczego są tacy, jacy …
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.