Teoretyczne informatyka

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

2
Dolne granice dla formuł o stałej głębokości?
Wiemy dużo o ograniczeniach obwodów o stałej głębokości (rozmiar wielomianowy). Ponieważ formuły o stałej głębokości (rozmiar wielomianowy) są jeszcze bardziej ograniczonym modelem obliczeń, wszystkie problemy, o których wiadomo, że nie występują w AC 0, również nie są obliczalne na podstawie wzoru o stałej głębokości. Ponieważ jednak jest to łatwiejszy model, …
1
Grupowanie konsensusowe za pomocą ustawionej unii
Zadałem już to pytanie jakiś czas temu na MathOverflow , ale zgodnie z moją najlepszą wiedzą jest ono nadal otwarte, więc zamieszczam je ponownie w nadziei, że ktoś o nim usłyszy. Opis problemu Niech , i będą trzema partycjami w niepustych częściach (oznaczonych przez , i ) zestawu { }. …
2
Ogranicza się do
Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy istnieje jakieś standardowe ograniczenie, które określa …
6
Jaki jest najlepszy sposób na uzyskanie rzutu monetą zbliżoną do uczciwej z identycznych monet tendencyjnych?
(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą jest zobowiązany.) Załóżmy, że mamy nnn identycznych monet o nastawieniu δ=P[Head]−P[Tail]δ=P[Head]−P[Tail]\delta=P[Head]-P[Tail] . …
10
Pobieranie #SAT Solver
Czy ktoś mógłby wskazać jedną lub więcej stron internetowych, z których można pobrać działającą implementację solvera #SAT? Interesują mnie osoby zwracające dokładną liczbę rozwiązań, a nie przybliżenie.
4
Które wyniki teorii złożoności istotnie wykorzystują jednolitość?
Dowód separacji klas złożoności używa jednorodności klas złożoności zasadniczo, jeśli dowód nie dowodzi wyniku dla wersji niejednorodnej, na przykład dowody oparte na przekątnej (takie jak twierdzenia dotyczące hierarchii czasu i przestrzeni) w istotny sposób wykorzystują jednolitość, ponieważ muszą symulować programy w mniejsza klasa. Które wyniki teorii złożoności (inne niż dowody …
6
Różnica między teorią a praktyką bezpieczeństwa i kryptografii?
Jakie są interesujące różnice między teorią a praktyką bezpieczeństwa i kryptografii? Najciekawsze będą oczywiście przykłady sugerujące nowe kierunki badań teoretycznych w oparciu o praktyczne doświadczenia :). Odpowiedzi mogą obejmować (ale nie wyłącznie): Przykłady, w których teoria sugeruje, że coś jest możliwe, ale nigdy nie jest wykorzystywane w praktyce Przykłady, w …
2
Czy semantyka TeXa (jako języka programowania) została kiedykolwiek sformalizowana?
Wydaje mi się, że język makr używany przez może być postrzegany jako pewnego rodzaju system przepisywania terminów lub jakiś język programowania z określaniem zakresu według nazw.T.miXT.miX\TeX Nawet współczesne implementacje silnika (np. ) interpretują kod w dość bezpośredni sposób i nie jestem świadomy żadnej próby optymalizacji wykonania (tak jak mogą to …
3
Wykorzystanie złożoności Kołmogorowa jako wejściowego „rozmiaru”
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Zdefiniujmy teraz zbiory wszystkich danych wejściowych o złożoności Kołmogorowa , i zdefiniujmy sekwencję Tutaj jest średnią sekwencją czasu pracy dla , z wyjątkiem przypadków, gdy „rozmiar” danych wejściowych jest złożonością Kołmogorowa, a nie ich długością.n …
6
Czy istnieje naturalny problem w czasie quasi-wielomianowym, ale nie w czasie wielomianowym?
László Babai niedawno udowodnił, że problem z izomorfizmem grafowym występuje w quasipolomomialnym czasie . Zobacz także jego przemówienie na Uniwersytecie w Chicago, notatkę z przemówień Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Zgodnie z twierdzeniem LADNER, o ile P.≠NP.P≠N.P.P \neq NP , a …
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.