Teoretyczne informatyka

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

1
Kiedy BPP z tendencyjną monetą równa się standardowemu BPP?
Pozwól probabilistycznej maszynie Turinga mieć dostęp do nieuczciwej monety, która pojawia się z prawdopodobieństwem (trzepnięcia są niezależne). Zdefiniuj jako klasę języków rozpoznawalnych przez taki komputer w czasie wielomianowym. Standardowym ćwiczeniem jest wykazanie, że:B P P ppppBPPpBPPpBPP_p A) Jeśli jest racjonalne lub nawet obliczalne z to . (Przy -computable to znaczy: …
2
Podtypy jako podzbiory typów danych SML
Jedną z niewielu rzeczy, których nie lubię w książce Okasaki o czysto funkcjonalnych strukturach danych, jest to, że jego kod jest zaśmiecony niewyczerpującym dopasowaniem wzorca. Jako przykład podam jego implementację kolejek w czasie rzeczywistym (zreorganizowane w celu wyeliminowania niepotrzebnych zawieszeń): infixr 5 ::: datatype 'a stream = Nil | ::: …
1
Złożoność osiągalności w liniowych układach dynamicznych nad polami skończonymi
Niech AAA będzie macierzą nad polem skończonym F2={0,1}F2={0,1}\mathbb{F}_2 = \{0,1\} a xxx , yyy będą wektorami przestrzeni Fn2F2n\mathbb{F}_2^n . Interesuje mnie złożoność obliczeniowa przy podejmowaniu decyzji, czy istnieje t∈Nt∈Nt \in \mathbb{N} takie, że Atx=yAtx=yA^t x = y , tj. Problem osiągalności liniowych układów dynamicznych nad polami skończonymi. Problem ten jest …
1
Poprawiasz ogólną redukcję Cooka dla Clique do SAT?
Jestem zainteresowany zredukowaniem kliki do SAT bez powiększania instancji.kkk Klika jest w NP, więc można ją zredukować do SAT za pomocą przestrzeni logarytmicznej. Prosta redukcja podręcznika Garey / Johnson wysadza instancję do sześciennej wielkości. Jednak Klika jest w P dla każdego ustalonego k, więc „powinna” być skuteczna redukcja przynajmniej dla …
1
Wprowadzenie do automatów probabilistycznych
Gdzie mogę znaleźć wprowadzenie do automatów probabilistycznych i co one rozpoznają (niektóre funkcje od słów do )? Czy istnieje standardowy termin określający takie funkcje, które są rozpoznawane przez automaty probabilistyczne, analogiczne do „zwykłych języków”, dla których rozpoznają deterministyczne automaty skończone (DFA)?[ 0 , 1 ][0,1][0,1] Szukam czegoś, co podchodzi do …
1
Czy w teorii typów istnieje dobre pojęcie o braku terminacji i zatrzymaniu dowodów?
Konstruktywna teoria typów z jej podstawową interpretacją w ramach korespondencji curry-howard składa się wyłącznie z całkowitych, obliczalnych funkcji. W literaturze niektórzy mówili o stosowaniu „teorii typów obliczeniowych” w celu przedstawienia nieterminacji w programach funkcjonalnych, ale w artykułach, na które się natknąłem, nie wydaje się to być główną motywacją dla teorii …
1
Klasy wykresów z nadprzyrodzoną szerokością
Istnieje kilka interesujących klas wykresów z ograniczoną szerokością. Na przykład drzewa (treewidth 1), szeregi równoległe wykresy (treewidth 2), zewnętrzne płaszczyzny (treewidth 2), routerplanar wykresy (treewidth O (k)), wykresy szerokości gałęzi (treewidth O (k)), .. .kkkkkk Pytanie: Czy istnieją przykłady interesujących klas wykresów, których szerokość nie jest ograniczona stałą, ale funkcją …
1
Domysł: Wszystkie języki FPT NP-complete mają stały parametr izomorficzny
Hipoteza Bermana – Hartmanisa: wszystkie języki NP-zupełne wyglądają podobnie, w tym sensie, że mogą być ze sobą powiązane przez wielomianowe izomorfizmy czasowe [1]. Interesuje mnie bardziej szczegółowa wersja „czasu wielomianowego”, to znaczy, jeśli zastosujemy sparametryzowane redukcje. Problem sparametryzowany to podzbiór , gdzie jest skończonym alfabetem, a to zbiór liczb nieujemnych. …
1
Dopasowanie maksymalnej masy i funkcje podmodularne
Biorąc pod uwagę dwudzielny wykres G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E) z dodatnimi wagami, niech f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R} z f(S)f(S)f(S) równym maksymalnemu dopasowaniu masy na wykresie .G[S∪V]G[S∪V]G[S\cup V] Czy to prawda, że jest funkcją podmodularną?fff
2
Łatwy w optymalizacji, ale trudny do oceny
Czy są znane naturalne przykłady problemów z optymalizacją, dla których znacznie łatwiej jest stworzyć optymalne rozwiązanie niż ocenić jakość danego rozwiązania kandydującego? Ze względu na konkretność możemy rozważyć rozwiązania problemów optymalizacji w postaci wielomianowej w postaci: „biorąc x, zminimalizuj ”, gdzie f : { 0 , 1 } ∗ × …
2
Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków
Rozważ następujący problem: Biorąc pod uwagę macierz , chcemy zoptymalizować liczbę dodatków w algorytmie mnożenia do obliczania .MMMv↦Mvv↦Mvv \mapsto Mv Uważam ten problem za interesujący ze względu na jego związek ze złożonością mnożenia macierzy (ten problem jest ograniczoną wersją mnożenia macierzy). Co wiadomo o tym problemie? Czy są jakieś interesujące …
1
Na czym polegają twierdzenia o dychotomii?
Powszechnie wiadomo, że pewne klasy NP -Problemy Have dychotomia twierdzeń, które gwarantują, że każde zadanie w klasie jest albo NP -Complete lub jest w P . Najbardziej znanym takim wynikiem jest twierdzenie Schaefera o dychotomii wraz z szeregiem uogólnień. Rozumiem, że udowodnienie tych twierdzeń o dychotomii nie jest naprawdę łatwe. …
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.