Teoretyczne informatyka

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

5
Teoretyczne zastosowania algorytmów aproksymacyjnych
Ostatnio zacząłem szukać algorytmów aproksymacyjnych dla problemów trudnych dla NP i zastanawiałem się nad teoretycznymi przyczynami ich badania. (To pytanie nie ma być zapalne - jestem po prostu ciekawy). Z badań algorytmów aproksymacyjnych wynikła pewna naprawdę piękna teoria - związek między twierdzeniem PCP a twardością aproksymacji, hipoteza UGC, algorytm aproksymacji …
3
Przybliżona suma posortowanej listy
Ostatnio pracowałem nad problemem obliczania przybliżonej sumy listy posortowanych liczb nieujemnych. Dla każdego ustalonego opracowano schemat aproksymacji czasu , który daje przybliżenie dla sumy. Artykuł opublikowano na stronie http://arxiv.org/abs/1112.0520 , który nie został jeszcze sfinalizowany.O ( log n ) ( 1 + ϵ )ϵ>0ϵ>0\epsilon>0O(logn)O(log⁡n)O(\log n)(1+ϵ)(1+ϵ)(1+\epsilon) Szukałem istniejących prac dotyczących tego …
1
Gdzie jest dowód, że Coq + Wykluczone Środek jest spójny
Widziałem (i słyszałem), że twierdził, że można bezpiecznie dodać klasyczny aksjomat wykluczonego środka do Coq, ale nie mogę znaleźć dokumentu potwierdzającego to twierdzenie. Artykuły, które widzę na liście na wiki Coq o wykluczonym środku, wykazują niespójność z impredykatywnym Setem. Rzeczywiście wydaje się, że Coquand stwierdza, że ​​dodanie Wykluczonego Środka (mieszkańca …
2
Kolorowanie płaskich wykresów
Rozważ zestaw płaskich wykresów, w których wszystkie ściany wewnętrzne są trójkątami. Jeśli jest punkt wewnętrzny nieparzystego stopnia, wykres nie może być trójkolorowy. Jeśli każdy punkt wewnętrzny ma równy stopień, czy zawsze może być trójkolorowy? Idealnie chciałbym mały kontrprzykład.
2
Skuteczne znajdowanie 5-cykli na rzadkim wykresie.
(crossposted z MathOverflow) Cześć, Czytałem ten wątek: /mathpro/16393/finding-a-cycle-of-fixed-length Chcę znaleźć 5-cykl na wykresie. Tak naprawdę to, czego naprawdę chcę, to najkrótszy nieparzysty cykl o długości co najmniej 5, ale może to trochę poza tym. Dla moich celów, traktuję i to samo w analizie złożoności. nmmmnnn Czy w takim przypadku możemy …
2
Jak dobry jest kod Huffmana, gdy nie ma dużych liter prawdopodobieństwa?
Kod Huffmana dla rozkładu prawdopodobieństwa jest kodem prefiksu o minimalnej średniej ważonej długości słowa kodowego , gdzie jest długością tego słowa kluczowego. Jest dobrze znanym twierdzeniem, że średnia długość na symbol kodu Huffmana zawiera się między a , gdzie jest entropią Shannona rozkładu prawdopodobieństwa.ppp∑piℓi∑piℓi\sum p_i \ell_iℓiℓi\ell_iiiiH(p)H(p)H(p)H(p)+1H(p)+1H(p)+1H(p)=−∑ipilog2piH(p)=−∑ipilog2⁡piH(p) = -\sum_i \, p_i …
4
Dowód lematu pompowania dla języków bezkontekstowych za pomocą automatów pushdown
Lemat o pompowaniu dla języków regularnych może być udowodnione przez rozważa automat skończony, który rozpoznaje stan języka badanego, zbierając ciąg o długości większej niż jego liczby stanów i stosując zasadę zaszufladkować. Jednak pompowanie lematu dla języków bezkontekstowych (a także lematu Ogdena, który jest nieco bardziej ogólny), zostało udowodnione poprzez rozważenie …
3
Ograniczenia przetwarzania równoległego
Jestem ciekawy w szerokim znaczeniu tego, co wiadomo na temat algorytmów równoległych w P. Znalazłem następujący artykuł w Wikipedii na ten temat: http://en.wikipedia.org/wiki/NC_%28complexity%29 Artykuł zawiera następujące zdanie: Nie wiadomo, czy NC = P, ale większość badaczy podejrzewa, że ​​jest to fałsz, co oznacza, że ​​prawdopodobnie istnieją pewne możliwe do rozwiązania …
3
Jak szybko możemy rozwiązać całkowicie nieimodularny program liniowy liczb całkowitych?
(Jest to kontynuacja tego pytania i odpowiedzi ). Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całkowite:ℓ , m , n1, n2), …
4
Algorytmy DNA i kompletność NP
Jaki jest związek między algorytmami DNA a klasami złożoności określonymi za pomocą maszyn Turinga? Czym są pomiary złożoności, takie jak czas i przestrzeń w algorytmach DNA? Czy można je wykorzystać do rozwiązania problemów związanych z NP-zupełnymi, takich jak TSP, których maszyny von Neumann nie są w stanie rozwiązać w praktyce?
6
Referencje na temat dolnych granic obwodu
Preambuła Interaktywne systemy dowodowe i protokoły Arthura-Merlina zostały wprowadzone przez Goldwassera, Micali i Rackoffa i Babai w 1985 roku. Początkowo sądzono, że ten pierwszy jest potężniejszy od drugiego, ale Goldwasser i Sipser wykazali, że mają taką samą moc ( w odniesieniu do rozpoznawania języka). Dlatego w tym poście użyję tych …
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.