Teoretyczne informatyka

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

2
Sprawdzanie równoważności dwóch polytopów
Rozważmy wektor zmiennych i zestaw wiązań liniowych określonych przez A → x ≤ b .x⃗ x→\vec{x}Ax⃗ ≤bAx→≤bA\vec{x}\leq b Ponadto rozważ dwa polytopy P1P2={(f1(x⃗ ),⋯,fm(x⃗ ))∣Ax⃗ ≤b}={(g1(x⃗ ),⋯,gm(x⃗ ))∣Ax⃗ ≤b}P1={(f1(x→),⋯,fm(x→))∣Ax→≤b}P2={(g1(x→),⋯,gm(x→))∣Ax→≤b}\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*} gdzie ' ig ' s są odwzorowaniami afinicznymi . Mianowicie …
3
Nietrudne problemy do rozwiązania w stałym czasie?
Stały czas jest absolutnie niskim stopniem złożoności czasu. Można się zastanawiać: czy jest coś nietypowego, co można obliczyć w stałym czasie? Jeśli trzymamy się modelu maszyny Turinga, niewiele można zrobić, ponieważ odpowiedź może zależeć tylko od początkowego odcinka wejścia o stałej długości, ponieważ dalsze części wejścia nie mogą być osiągnięte …
1
Jak drogie może być zniszczenie wszystkich długich ścieżek w DAG?
Uważamy DAG (skierowane wykresy acykliczne) z jednym węzłem źródłowym jeden docelowego węzła ; dozwolone są równoległe krawędzie łączące tę samą parę wierzchołków. - cięcie jest zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek dłuższe niż ; krótsze - szlaki, a także wydłużone „wewnętrzny” (te, które nie ścieżki pomiędzy i ), …
1
Jaki jest stan wiedzy w teorii algorytmów pamięci podręcznej?
Niedawno zainteresowałem się ogólnym problemem optymalizacji wykorzystania pamięci w sytuacji, gdy dostępny jest więcej niż jeden rodzaj pamięci, i istnieje kompromis między pojemnością danego segmentu pamięci a szybkością dostępu do niego. Znanym przykładem jest program decydujący, kiedy odczytywać / zapisywać w pamięci podręcznej procesora, pamięci RAM i dysku twardym (za …
5
Przydatność entropii Renyi?
Większość z nas zna - lub przynajmniej słyszała - entropię Shannona zmiennej losowej, H(X)=−E[logp(X)]H(X)=−E[log⁡p(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] oraz wszystkie powiązane miary teoretyczne, takie jak entropia względna, wzajemna informacja i tak dalej. Istnieje kilka innych miar entropii, które są powszechnie stosowane w informatyce teoretycznej i teorii informacji, takich jak …
1
Porównanie złożoności teorii Kołmogorowa
Twierdzenie Chaitina o niekompletności mówi, że żadna wystarczająco silna teoria arytmetyki nie może udowodnić, że gdzie K ( s ) to złożoność Kołmogorowa ciągów s, a L jest wystarczająco dużą stałą. L jest wystarczająco duży, jeśli jest większy niż rozmiar w bitach maszyny sprawdzającej proof (PCM). PCM dla teorii T …
1
Kurs do nauki złożoności algebraicznej
Chcę się dowiedzieć o algorytmach algebraicznych i złożoności tysiąca. W szczególności interesuje mnie PIT. Czy istnieje zestaw notatek z wykładów, książek, prac i ankiet dla studentów, którzy przeczytali standardowy podręcznik o teorii, taki jak książka Sipsera lub podręcznik złożoności Arory-Baraka. Zestaw referencji będzie zawierał najnowsze zaawansowane wyniki.
1
Obliczeniowa wersja równowagi Nasha?
Zastanawiam się, czy istnieje obliczeniowa wersja koncepcji równowagi Nasha, coś podobnego do tego. Wyobraź sobie jakąś idealną grę informacyjną dla dwóch graczy, która jest rozgrywana na planszy , i która jest złożona w tym sensie, że optymalna gra jest trudna WYGODNIE. Załóżmy również dla uproszczenia, że ​​losowanie nie jest możliwe. …
2
Czy automaty XOR (NXA) dla języków skończonych korzystają z cykli?
Niedeterministyczne automaty Xor (NXA) są składniowo NFA, ale mówi się, że słowo jest akceptowane przez NXA, jeśli ma nieparzystą liczbę ścieżek akceptacji (zamiast co najmniej jednej ścieżki akceptacji w przypadku NFA). Łatwo zauważyć, że dla skończonego języka regularnego LLL istnieje minimalny NFA, który nie zawiera żadnych cykli (jeśli cykl był …
1
Czy kompletność PSPACE oznacza twardość aproksymacyjną?
W komentarzu w innym poście z cstheorySE wspomniano, że kompletność PSPACE implikuje twardość APX. Czy ktoś może wyjaśnić / udostępnić referencję? Czy to jest „ciasne”? (tj. czy istnieją problemy kompletne z PSPACE, których problem optymalizacji dopuszcza stałe przybliżanie współczynnika w czasie wielopunktowym? Co z kompletnością dla pewnego poziomu PH? Czy …
1
Random 3-SAT: Jaki jest eksperymentalny zakres progowy?
Krytyczny stosunek klauzul do zmiennych dla losowej 3-SAT jest większy niż 3 i mniejszy niż 6, i wydaje się być powszechnie opisywany jako „około 4,2” lub „około 4,25”. Mezard, Parisi i Zecchina udowadniają (w sensie fizyki), że współczynnik krytyczny wynosi 4,256, podczas gdy autorzy pierwszego i trzeciego dowodzą , że …
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.