Teoretyczne informatyka

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

2
Struktura danych do dynamicznej alokacji pamięci
Pomyśl o modelu sondy komórkowej. Czy istnieje struktura danych, która może przydzielić ciągłe fragmenty pamięci o dowolnej długości (jak np. Malloc w C) i zwolnić je, unikając segmentacji pamięci, i wykonuje każdą operację w najgorszym przypadku deterministycznym czasie O (log n), gdzie n jest całkowity rozmiar pamięci? Unikając segmentacji pamięci …
1
Czy szerokość sugeruje istnienie nieletniego ?
Niech zostanie naprawione, a będzie (połączonym) wykresem. Jeśli się nie mylę, z pracy Bodlaendera [1, Twierdzenie 3.11] wynika, że ​​jeśli szerokość wynosi w przybliżeniu co najmniej , wówczas zawiera gwiazdę jako pomniejszą.G G 2 k 3 G K 1 , kkkksolGGsolGG2 tys3)2k32k^3solGGK.1 , kK1,kK_{1,k} Czy możemy zmniejszyć termin ? To …
2
Lista zagadnień teoretycznych lub algebraicznych w różnych klasach złożoności
Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład, GCD w jest otwarty,N.do1NC1NC^1 faktoring w jest otwarty,P.PP obliczanie kohomologii snopów to -hard# P#P\#P , Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie jest jasne, na podstawie dyskusji na NP-zupełnym wariantu faktoringu. ),N.P.NPNP …
5
Aplikacje kombinatoryki addytywnej w projektowaniu algorytmów
Czytam ankiety Trevisana i Lovetta dotyczące zastosowań dodatku kombinatorycznego w TCS. Większość tych aplikacji ma złożoność obliczeniową , np. Niższe granice. Zastanawiam się, czy kombinatoryka addytywna znalazła również zastosowania w projektowaniu algorytmów . Motywacja mojego pytania jest następująca: chociaż związek między kombinatoryką addytywną a złożonością wydaje się dość naturalny, jestem …
1
Czy te gry kolorowanki zostały rozwiązane?
W artykule „O złożoności niektórych gier koloryzujących” Bodlaender podaje kilka otwartych pytań na temat złożoności decydowania, czy gracz 1 lub 2 ma strategię wygrywającą w niektórych grach kolorystycznych. Czy ktoś wie, czy zostały rozwiązane? 1) W jednej grze dwóch graczy wybiera kolejno jeden wierzchołek na wykresie i odpowiednio koloruje go …
2
Zakres barier naturalnych dowodów
Naturalna bariera dowodowa Razborova i Rudicha mówi, że przy wiarygodnych założeniach kryptograficznych nie można mieć nadziei na oddzielenie NP od P / poli poprzez znalezienie kombinatorycznych właściwości funkcji, które są konstruktywne, duże i użyteczne. Istnieje kilka dobrze znanych wyników, które potrafią ominąć barierę. Istnieje również kilka artykułów omawiających możliwe luki …
2
Jak dokładnie rachunek lambda uwzględnia intuicyjne pojęcie obliczalności?
Próbowałem owinąć głowę wokół tego, co, dlaczego i jak rachunek, ale nie jestem w stanie poradzić sobie z „dlaczego to działa”?λλ\lambda „Intuicyjnie” dostaję model obliczeniowy Turing Machines (TM). Ale ta abstrakcja wprawia mnie w zakłopotanie.λλ\lambda Załóżmy, że bazy danych nie istnieją - jak więc można „intuicyjnie” przekonać się o zdolności …
4
Problemy, o których wiadomo, że nie są kompletne z PSPACE
Jakie są problemy z następującymi właściwościami: 1) są ograniczeniem (prawdopodobnie dobrze znanych) problemów, które są kompletne z PSPACE; 2) wersje ograniczone są w PSPACE, ale jest to otwarty problem, jeśli są one kompletne (lub nawet jeśli są trudne w wersji NP). Cztery przykłady z „puzzli i C.”: Złożoność 1x1 Godziny …
1
Praktyczne zastosowania gier parzystości
Czy istnieją przykłady praktycznych zastosowań gier parzystych, tj. Systemów w świecie rzeczywistym, które można przedstawić jako gry parzyste? Zwykle powiązana dokumentacja dotycząca gier z parzystością prawie nigdy nie jest praktycznym przykładem tej aplikacji.
3
Zastosowania kategorii
Nie jestem teoretycznym informatykiem. Jestem stabilnym teoretykiem homotopii, posługującym się kategoriami . Widziałem zastosowań teorii teorii kategorii i topos teoretycznej informatyki, a ja zastanawiałem się, czy istnieje jakikolwiek sposób można użyć ∞ -categories (i korzystnie dla mnie, stabilny teorii homotopii) w teoretycznej informatyki. Myślę, że HoTT może być jedną z …
2
Generator pseudolosowy dla automatów skończonych
Niech będzie stałą. Jak możemy w sposób wiarygodny skonstruować pseudolosowy generator, który oszuka -state skończone automaty?dreddredd Tutaj automat skończony -state ma węzły, węzeł początkowy, zestaw węzłów reprezentujących stany akceptacji i dwie skierowane krawędzie oznaczone 0, 1 wychodzące z każdego węzła. Zmienia stan w naturalny sposób, odczytując dane wejściowe. Biorąc pod …
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.