Teoretyczne informatyka

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

3
Czy „Gdzie są naprawdę trudne problemy”? Jakie są aktualne pomysły na ten temat?
Uważam ten artykuł za bardzo interesujący. Podsumowując: omawia, dlaczego w praktyce rzadko znajduje się najgorszy przypadek problemu NP-zupełnego. Idea tego artykułu polega na tym, że przypadki są zwykle bardzo niedostatecznie lub bardzo przeciążone, a oba są stosunkowo łatwe do rozwiązania. Następnie proponuje dla kilku problemów miarę „ograniczenia”. Wydaje się, że …
2
Złożoność n-królowych?
Klasyczne problemy z kolejką pytają, biorąc pod uwagę dodatnią liczbę całkowitą n , czy istnieje tablica Q [ 1 .. n ] liczb całkowitych spełniająca następujące warunki:nnnnnnQ [ 1 .. n ]Q[1..n]Q[1..n] dla wszystkich i1 ≤ Q [ i ] ≤ n1≤Q[i]≤n1\le Q[i] \le njaii dla wszystkich i ≠ jQ …
3
Problemy z nie są znane z ?
Jakie problemy należą do ale nie są znane z ?BPPBPP\mathsf{BPP}PP\mathsf P Mówiąc dokładniej, interesują mnie niezależne problemy, czyli takie, których derandomizacje nie są znane jako równoważne. Na przykład wiadomo, że derandomizacja PIT i wieloczynnikowe wielomianowe rozkładanie na czynniki są równoważne i uważałbym je za jeden problem. Motywacją mojego pytania jest …
2
Powody, by wierzyć
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 6 lat temu . Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do rozwiązania. (Shiva Kintali wymienił tutaj kilka …
7
Nietrywialne członkostwo w NP
Czy jest przykładem języka, który jest w NPNPNP , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku? Zamiast tego fakt, że język znajduje się w NPNPNP , można udowodnić, redukując go do innego języka w NPNPNP , gdzie powiązanie …
27 reductions  np 
3
Zdecyduj, czy jądro macierzy zawiera jakiś niezerowy wektor, którego wszystkie wpisy to -1, 0 lub 1
Biorąc pod uwagę mmm o nnn binarnego macierzy MMM (wartość wynosi 000 lub 111 ), problemem jest ustalenie, czy istnieje dwoma wektorami binarnymi v1≠v2v1≠v2v_1 \ne v_2 w taki sposób, Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (wszystkie operacje wykonywane przez ZZ\mathbb{Z} ). Czy ten problem jest trudny NP? Widać to wyraźnie w NP, ponieważ …
5
Ekologia i ewolucja poprzez soczewkę algorytmiczną
Badanie ekologii i ewolucji staje się coraz bardziej matematyczne, ale wydaje się, że większość narzędzi teoretycznych pochodzi z fizyki. Jednak w wielu przypadkach problemy mają bardzo dyskretny charakter (patrz na przykład SLBS00 ) i mogą skorzystać z perspektywy informatyki . Jednak wiem tylko o kilku poważnych wynikach TCS, które próbują …
10
Algorytmy probabilistyczne (randomizowane) przed pojawieniem się „nowoczesnej” informatyki
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy algorytm losowy (rok ???). Lipton wprowadził algorytm Rabina jako początek ery …
3
Pojęcie monotonicznych obwodów kwantowych
W złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że ​​3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich. Moje pytanie jest proste: czy istnieje analog kwantowy dla obwodów monotonicznych (lub więcej niż jednego)? Czy istnieje kwantowe twierdzenie Razborowa?
2
Decyzja, czy NC
Chciałbym zapytać o szczególny przypadek pytania „ Decyzja, czy dany obwód NC 0 oblicza permutację ” QiCheng, na który nie udzielono odpowiedzi. Obwód boolowski nazywa się obwodem NC 0 k , jeżeli każda bramka wyjściowa syntaktycznie zależy od co najwyżej k bramek wejściowych. (Mówimy, że bramka wyjściowa g syntaktycznie zależy …
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.