Teoretyczne informatyka

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

1
Czy istnieje lepsza niż liniowa dolna granica dla faktoringu i dziennika dyskretnego?
Czy istnieją odniesienia, które zawierają szczegółowe informacje na temat dolnych granic obwodu dla konkretnych trudnych problemów pojawiających się w kryptografii, takich jak faktoring liczb całkowitych, problem logarytmu dyskretnego z liczbami pierwszymi / złożonymi i jego wariant nad grupą punktów krzywych eliptycznych (i ich wielowymiarowych odmian abelowych) i ogólne ukryty problem …
1
Czy kryptografia ma nieodłączny koszt termodynamiczny?
Obliczenia odwracalne to model obliczeniowy, który pozwala jedynie na operacje odwracalne termodynamicznie. Zgodnie z zasadą Landauera, która stwierdza, że ​​usunięcie części informacji uwalnia ciepło dżuli, wyklucza to funkcje przejścia, które nie są jeden do jednego (np. Operatory logiczne AND i OR). Powszechnie wiadomo, że obliczenia kwantowe są z natury odwracalne, …
4
Złożoność obliczeniowa w finansach ilościowych
Prognozowanie rynku akcji jest trudne! Czy TCS może uczynić ten sentyment bardziej formalnym? Ostatnio zacząłem trochę myśleć o finansach i zastanawiałem się, w jaki sposób wiedza TCS może pomóc. Fundusze hedgingowe i firmy inwestycyjne wydają się cały czas korzystać z handlu algorytmicznego, uczenia maszynowego i sztucznej inteligencji, ale wyniki TCS …
2
Struktura danych dla zapytań o minimalną liczbę kropek
RnRn\mathbb{R}^n⟨⋅,⋅⟩⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmmv1,v2,…,vmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx∈Rnx \in \mathbb{R}^nmini⟨x,vi⟩mini⟨x,vi⟩\min_i \langle x, v_i \rangleO(nm)O(nm)O(nm)n=2n=2n = 2O(log2m)O(log2⁡m)O(\log^2 m) Jedyne, co mogę wymyślić, to: Bezpośrednią konsekwencją lematu Johnsona-Lindenstraussa jest to, że dla każdego i rozkładu na występuje liniowe mapowanie (które można ocenić w czasie ) tak, że . Tak więc w czasie O …
2
Czy znane są problemy NP-zupełne, ani trudne NP w silnym znaczeniu, ani algorytm pseudopolinomalny?
W swoim artykule (s. 503) Garey i Johnson zauważają: ... może istnieć problem NP-zupełny, który nie jest ani NP-zupełny w sensie silnym, ani rozwiązany przez algorytm pseudo-wielomianowy ... Czy ktoś zna problemy z kandydatami dotyczące wyżej wymienionych właściwości? Myślę, że możliwą odpowiedzią na to pytanie może być lista problemów NP-zupełnych …
5
Dlaczego w ogóle działają relacyjne bazy danych, biorąc pod uwagę teoretyczną wykładniczą złożoność wyszukiwania odpowiedzi (w wielkości zapytania)?
Wydaje się znane, że aby znaleźć odpowiedź na zapytanie w relacyjnej bazie danych , potrzebny jest czas i nie można pozbyć się wykładnika.D | D | | Q | | Q |QQQrereD| D || Q ||re||Q||D|^{|Q|}| Q ||Q||Q| Ponieważ może być bardzo duży, zastanawiamy się, dlaczego bazy danych w ogóle …
2
utrzymywanie zrównoważonego drzewa opinającego rosnącego niekierowanego wykresu
Poszukuję sposobów na utrzymanie względnie zrównoważonego drzewa opinającego wykresu, gdy dodam do niego nowe węzły / krawędzie. Mam nieukierunkowany wykres, który zaczyna się jako pojedynczy węzeł, „root”. Na każdym kroku dodaję do wykresu albo nowy węzeł i krawędź łączącą go z wykresem, albo tylko nową krawędź łączącą dwa stare węzły. …
4
Jaka jest „właściwa” definicja górnej i dolnej granicy?
Niech będzie najgorszym czasem działania problemu na wejściu wielkości . Uczyńmy ten problem nieco dziwnym, ustalając dla ale dla .f(n)f(n)f(n)nnnf(n)=n2f(n)=n2f(n) = n^2n=2kn=2kn=2kf(n)=nf(n)=nf(n) = nn=2k+1n=2k+1n=2k+1 Więc jaka jest dolna granica problemu? Zrozumiałem, że to tylko dolna granica . Ale wiemy, że oznacza, że ​​istnieje stała , taka, że ​​dla wszystkich , …
11
Modele losowych wykresów dla rzeczywistych sieci komputerowych
Interesują mnie modele losowych wykresów, które są podobne do wykresów rzeczywistych sieci komputerowych. Nie jestem pewien, czy wspólny dobrze zbadany model ( wierzchołków, każda możliwa krawędź jest wybierana z prawdopodobieństwem ) nadaje się do badania rzeczywistych sieci komputerowych (prawda?).n pG ( n , p )sol(n,p)G(n,p)nnnppp jakie modele losowych wykresów są …
3
Czy istnieje związek między normą diamentową a odległością stanów powiązanych?
W teorii informacji kwantowej odległość między dwoma kanałami kwantowymi jest często mierzona za pomocą normy diamentowej. Istnieje również wiele sposobów pomiaru odległości między dwoma stanami kwantowymi, takich jak odległość śladu, wierność itp. Izomorfizm Jamiołkowskiego zapewnia dualność między kanałami kwantowymi a stanami kwantowymi. Jest to dla mnie interesujące, ponieważ norma diamentowa …
1
Konsekwencje UP są równe NP
EDYCJA na 2011/02/08: Po znalezieniu i przeczytaniu niektórych odniesień postanowiłem rozdzielić oryginalne pytanie na dwa osobne. Oto część dotycząca UP vs NP, w części dotyczącej klas syntaktycznych i semantycznych zobacz Korzyści dla klas syntaktycznych i semantycznych . UPUP\mathsf{UP} (jednoznaczny czas wielomianowy, patrzwikiizoodla odniesienia) jest zdefiniowany jako języki ustalone przez maszynyNPNP\mathsf{NP} …
1
Problem Warrena Buffetta
Oto streszczenie problemu nauki online / bandyty, nad którym pracowałem latem. Nie widziałem wcześniej takiego problemu i wygląda całkiem interesująco. Jeśli znasz jakieś powiązane prace, byłbym wdzięczny za referencje. Problem Ustawienie dotyczy wielorękich bandytów. Masz N. broni. Każde ramię ma nieznany, ale stały rozkład prawdopodobieństwa nad nagrodami, które można zdobyć, …
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.