Teoretyczne informatyka

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

3
Czy
Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj. Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak A C 0 / P O l y , czyli niejednolity C 0 ), czy to oznacza, że funkcja ta …
1
Referencyjne gry z niepowiązanymi półprywatnymi monetami
Byłem (i nadal jestem) bardzo zainteresowany odpowiedzią na to pytanie, ponieważ jest to interesująca odmiana złożoności gier, która nie została jeszcze rozwiązana, więc zaoferowałem nagrodę. Pomyślałem, że pierwotne pytanie jest prawdopodobnie zbyt trudne, więc zamieściłem trzy powiązane pytania, które również byłyby warte nagrody. Nikt nie opublikował żadnych odpowiedzi przed wygaśnięciem …
9
Randomizowany algorytm, który „wygląda” deterministycznie?
Czy istnieje interesujący przykład losowego algorytmu dla problemu wyszukiwania, który zawsze generuje tę samą (poprawną) odpowiedź, niezależnie od wewnętrznej losowości, ale który wykorzystuje losowość, dzięki czemu jej oczekiwany czas działania jest lepszy niż czas działania najszybszego znanego algorytm deterministyczny dla problemu? W szczególności zastanawiałem się, czy istnieje taki algorytm do …
5
co jest łatwe dla niewielkich wykluczonych wykresów?
Przybliżenie liczby kolorów wydaje się łatwe na niewielkich wykluczonych wykresach przy użyciu algorytmu Jung / Shah. Jakie są inne przykłady problemów, które są trudne na ogólnych wykresach, ale łatwe na niewielkich wykluczonych wykresach? Aktualizacja 10/24 Wydaje się, że podąża za wynikami Grohe, że wzór, którym jest FPT do testowania na …
2
Jak trudno jest zastosować podejście GCT Mulmuley-Sohoni do pokazania * znanych * separacji złożoności?
W tym poście Josh Grochow na blogu o złożoności relacjonuje ostatnie warsztaty poświęcone GCT, które odbyły się w lipcu w Princeton. Kilku uczestników argumentowało, że powinniśmy używać GCT do atakowania łatwiejszych problemów niż PP.\mathsf{P} vs. NPN.P.\mathsf{NP} w celu zbudowania intuicji i sprawdzenia, czy metoda ma potencjał. Pytanie, które mnie denerwuje: …
6
Odwrotna granica Chernoffa
Czy istnieje odwrotna granica Chernoffa, która ogranicza, że ​​prawdopodobieństwo ogona jest co najmniej tak duże. tj. jeśli X 1 , X 2 , … , X nX1,X2,…,XnX_1,X_2,\ldots,X_n są niezależnymi dwumianowymi zmiennymi losowymi, a μ = E [ ∑ n i = 1 X i ]μ=E[∑ni=1Xi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Czy możemy zatem …
3
Czy ta odmiana TQBF jest wciąż kompletna z PSPACE?
Decydowanie, czy skwantyfikowana formuła boolowska, taka jak ∀ x1∃ x2)∀ x3)⋯ ∃ xnφ ( x1, x2), … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), zawsze ocenia na prawdę, to klasyczny problem z PSPACE. Można to postrzegać jako grę między dwoma graczami, z naprzemiennymi …
2
Czy istnieje taka wyrocznia, że ​​SAT nie jest nieskończenie często w czasie sub wykładniczym?
Zdefiniuj ioioio - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości n . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”).SUBEXPSUBEXPSUBEXPL ′ ∈ ∩ ε > 0LLLL′∈∩ε>0TIME(2nε)L′∈∩ε>0TIME(2nε)L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})nnnLLLL′L′L'nnn Czy istnieje wyrocznia …
1
Problem satysfakcji z ograniczeń (CSP) vs. teoria modulo satysfakcji (SMT); z kodą na temat programowania ograniczeń
Czy ktoś odważy się wyjaśnić, jaki jest związek tych kierunków studiów, czy może nawet bardziej konkretną odpowiedź na poziomie problemów? Który obejmuje, który obejmuje niektóre powszechnie akceptowane formulacje. Jeśli dobrze to zrozumiałem, przechodząc z SAT do SMT, po prostu wchodzisz w pole CSP; i na odwrót, jeśli ograniczysz CSP do …
1
Czy można zdecydować o izomorfizmie grafowym za pomocą niedeterminizmu opartego na pierwiastku kwadratowym?
Ograniczonym nondeterminism łączy funkcję z klasy języków akceptowanych przez deterministycznych maszyny Turinga zasobach ograniczona, w celu utworzenia nowej klasy - . Ta klasa składa się z tych języków, które są akceptowane przez jakąś niedeterministyczną maszynę Turinga przestrzegającą tych samych granic zasobów, jakie są używane do zdefiniowania , ale gdzie może …
2
Jak trudno policzyć liczbę czynników całkowitych?
Biorąc pod uwagę liczbę całkowitą długości n bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) N ?N.NNnnnN.NN Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników ogólnych, nie jest jasne, w jaki sposób ustalilibyśmy faktyczne czynniki pierwsze.NNN Czy …
2
Pijane ptaki kontra pijane mrówki: losowe spacery między dwoma a trzema wymiarami
Powszechnie wiadomo, że losowy spacer w dwuwymiarowej siatce powróci do początku z prawdopodobieństwem 1. Wiadomo również, że ten sam losowy spacer w TRZY wymiarach ma prawdopodobieństwo mniej niż 1 powrotu do początku . Moje pytanie brzmi: Czy jest coś pomiędzy? Załóżmy na przykład, że moja przestrzeń była w rzeczywistości ograniczonym …
7
Najbardziej wpływowe wyniki Liptona
Richard J. Lipton został wybrany zwycięzcą nagrody Knuth Prize 2014 „za wprowadzenie nowych pomysłów i technik”. Jakie są według Ciebie główne nowe pomysły i techniki opracowane przez Lipton? Uwaga. To pytanie stanie się wiki społeczności, proszę podać jeden taki pomysł, technikę lub wynik na odpowiedź.
30 big-list 
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.