Teoretyczne informatyka

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

2
Złożoność homogenizacji łańcucha
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i …
1
Czy ten polytop „podgrupy” jest integralny?
Niech będzie skończoną grupą abelową, i niech będzie polytopem w zdefiniowanym jako punkty spełniające następujące nierówności:P R Γ xΓΓ\GammaP.PPRΓRΓ\mathbb{R}^\Gammaxxx ∑sol∈ G.xsol≤ | G |xsol≥ 0∀ G ≤ Γ∀ g∈ Γ∑g∈Gxg≤|G|∀G≤Γxg≥0∀g∈Γ\begin{array}{cl} \sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\ x_g \ge 0 & \forall g \in \Gamma \end{array} …
1
Klasy złożoności losowości i małych obwodów
Niech będzie klasą złożoności, a będzie losowym odpowiednikiem zdefiniowanego jako w odniesieniu do . Bardziej formalnie podajemy wielomianowo wiele bitów losowych i akceptujemy dane wejściowe, jeśli prawdopodobieństwo akceptacji jest większe niż .Cdo\mathcal{C}BP-CBPdo\textrm{BP-}\mathcal{C}Cdo\mathcal{C}BPPBPP\textrm{BPP}PP.\textrm{P}232)3)\frac{2}{3} Wiadomo, że dla klasy obwodów nierównomiernych mamy :BPAC0= AC0BPAC0=AC0\textrm{BPAC}^0=\textrm{AC}^0 Miklós Ajtai, Michael Ben-Or: Twierdzenie o probabilistycznych obliczeniach stałej …
2
Polimorfizm wyższego rzędu w porównaniu z typami nieopakowanymi
Mam język, w którym typy są domyślnie rozpakowane, a wnioskowanie typu oparte jest na Hindley-Milner. Chciałbym dodać polimorfizm wyższego rzędu, głównie do pracy z typami egzystencjalnymi. Wydaje mi się, że rozumiem, jak sprawdzić te typy, ale nie jestem pewien, co robić podczas kompilacji. Obecnie kompiluję definicje polimorficzne, generując specjalizacje, podobnie …
1
Czy prawdziwą losowość (możliwe do udowodnienia) można zastąpić losowością Kołmogorowa dla RP?
Czy były jakieś próby wykazania, że losowość Kołmogorowa byłaby wystarczająca dla RP ? Czy prawdopodobieństwo użyte w stwierdzeniu „Jeśli prawidłowa odpowiedź brzmi TAK, to wówczas (probabilistyczna maszyna Turinga) zwraca TAK z prawdopodobieństwem ...” zawsze byłoby dobrze zdefiniowane w takim przypadku? Czy byłyby tylko górne i dolne granice tego prawdopodobieństwa? Czy …
1
Czy SAT w ograniczonej szerokości jest rozstrzygalny w przestrzeni logów?
Elberfeld, Jakoby i Tantau 2010 ( ECCC TR10-062 ) dowiodły, że zajmująca mało miejsca wersja twierdzenia Bodlaendera. Wykazali, że w przypadku wykresów o szerokości co najwyżej rozkład drzewa o szerokości k można znaleźć za pomocą przestrzeni logarytmicznej. Stały współczynnik w ograniczonej przestrzeni zależy od k . (Twierdzenie Bodlaendera pokazuje liniowe …
1
Przykłady zastosowania estymatorów stronniczych
Biodrowe estymatory są przydatne w statystykach, ponieważ mogą bardziej zoptymalizować błąd średniokwadratowy niż ten, którym może zarządzać bezstronny estymator . Zastanawiałem się, czy teoretycznie CS, czy istnieją jakieś bardzo godne uwagi przykłady skutecznego wykorzystania stronniczych estymatorów. Zdaję sobie sprawę, że ta lista może być długa i jeśli tak, mogę zmodyfikować …
3
Kiedy różnica w dualności programowania semidefinite (SDP) wynosi zero?
Nie udało mi się znaleźć w literaturze dokładnej charakterystyki zaniku luki dualności SDP. Lub kiedy ma miejsce „silna dualność”? Na przykład, kiedy ktoś porusza się między Lasserre a SOS SDP, w zasadzie ma się lukę w dualności. Jednak wydaje się, że istnieje jakiś „trywialny” powód, dla którego nie ma tej …
1
Status kompletności PP MAJ3SAT
KRÓTKIE PYTANIE: Czy MAJ-3CNF jest problemem kompletnym z PP przy wielu redukcjach? DŁUŻSZA WERSJA: Dobrze wiadomo, że MAJSAT (decydujący, czy większość przypisań zdania zdaniowego spełnia zdanie) jest PP-kompletny przy wielu redukcjach jeden, a #SAT jest # P-kompletny przy redukcjach oszczędnych. Oczywiste jest również, że # 3CNF (czyli #SAT ograniczony do …
1
Niekompletna podstawa kombinacji
Jest to inspirowane tym pytaniem. Niech będzie zbiorem wszystkich kombinacji, które mają tylko dwie powiązane zmienne. Czy kombinatorycznie kompletny?C.dodo\mathcal{C}dodo\mathcal{C} Uważam, że odpowiedź jest przecząca, jednak nie udało mi się znaleźć odniesienia do tego. Byłbym również zainteresowany referencjami na dowody kombinatorycznej niekompletności zestawów kombinatorów (rozumiem, dlaczego zestaw składający się z kombinatorów …
3
Problem najkrótszej odległości z długością jako funkcją czasu
Motywacja Pewnego dnia podróżowałem po mieście środkami transportu publicznego i stworzyłem interesujący problem graficzny, modelujący problem znalezienia najkrótszego połączenia między dwoma miejscami. Wszyscy znamy klasyczny „problem najkrótszej ścieżki”: biorąc pod uwagę ukierunkowany wykres o długości krawędzi i dwóch wierzchołkach , znalezienie najkrótszej ścieżki pomiędzy i (to znaczy ścieżka minimalizację całkowitej …
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.