Teoretyczne informatyka

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

3
Nierówność typu Chernoffa dla niezależnych zmiennych losowych parami
Nierówności typu Chernoffa służą do wykazania, że ​​prawdopodobieństwo, że suma niezależnych zmiennych losowych znacznie odbiega od wartości oczekiwanej, jest wykładniczo małe w wartości oczekiwanej i odchyleniu. Czy istnieje jakakolwiek nierówność typu Chernoffa dla dowolnej sumy niezależnych parami zmiennych losowych? Innymi słowy, czy istnieje wynik, który pokazuje, co następuje: prawdopodobieństwo, że …
2
Partycja wolna od H.
To jest pytanie, zainspirowany problemu cięcia H-darmo . Biorąc pod uwagę wykres, podział jego zbioru wierzchołków na r części V 1 , V 2 , … , V r jest wolny od H, jeśli G [ V i ] nie indukuje kopii H dla wszystkich i , 1 ≤ i …
1
Odniesienie do dolnej granicy separatora w siatce?
Łatwo jest zweryfikować, że biorąc pod uwagę wymiarową siatkę punktów całkowitych , przy regularnym sąsiedztwie można znaleźć separator o rozmiarze (wystarczy wybrać dowolny środkowy hiperpłaszczyzna i usuń wszystkie jego wierzchołki). Nie jest też zbyt trudne (ale zdecydowanie nie natychmiastowe) sprawdzenie, czy każdy separator musi mieć rozmiar \ Omega (n ^ …
2
Hierarchia naprzemienna
Dzięki Immerman i Szelepcsényi wiadomo, że jeśli f = Ω ( log ) (nawet w przypadku funkcji niemożliwych do zbudowania w przestrzeni).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) W tym samym artykule Immerman stwierdza, że ​​naprzemienna hierarchia przestrzeni logicznej się zawala, co oznacza, że (definicja ograniczonej naprzemiennej maszyny Turinga i tego, co jest hierarchię …
3
Bezpieczeństwo pamięci oparte na typach bez ręcznego zarządzania pamięcią lub zbierania elementów w czasie wykonywania?
Powiedzmy, że chcieliśmy typowego, czysto funkcjonalnego języka programowania, takiego jak Haskell lub Idris, który jest przeznaczony do programowania systemów bez wyrzucania elementów bezużytecznych i nie ma środowiska wykonawczego (a przynajmniej nie więcej niż „środowiska wykonawcze” C i Rust). Coś, co może działać mniej więcej na gołym metalu. Jakie są niektóre …
2
Czym dokładnie są klasy FP, FNP i TFNP?
W swojej książce Computational Complexity Papadimitriou definiuje FNP w następujący sposób: Załóżmy, że jest językiem w NP . Propozycja według 9.1 jest rozstrzygalne wielomianowego razem wielomianowo zrównoważony stosunek R L takie, że dla wszystkich ciągów x : jest łańcuch Y z R L ( x , y ) , wtedy …
13 complexity 
2
Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie ukierunkowanym występuje niewyważony wierzchołek, musi istnieć inny. Ale zazwyczaj klasa jest …
4
Czy możemy szybko wygenerować idealnie jednolicie mod 3 lub rozwiązać problem NP?
Szczerze mówiąc, nie wiem zbyt wiele o tym, jak generowana jest liczba losowa (komentarze są mile widziane!), Ale załóżmy następujący model teoretyczny: Możemy uzyskać liczby całkowite jednolicie losowe z a naszym celem jest wyprowadza liczbę całkowitą jednolicie losową z [1,3].[ 1 , 2 n ][1,2n][1,2^n] Oto proste rozwiązanie, którego oczekiwany …
1
Delikatne wprowadzenie do algorytmicznych aspektów głębokości drzewa
Szerokość i szerokość ścieżki są popularnymi parametrami, mierzącymi odpowiednio bliskość wykresu do drzewa lub ścieżki. Rzeczywiście wydaje się, że szerokość jest tak popularna, że ​​pojawia się w wielu artykułach, książkach i notatkach z wykładów, które dają (nawet bardzo delikatne) wprowadzenie do algorytmicznych aspektów szerokości (patrz np. Książka Downey & Fellows). …
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.