Teoretyczne informatyka

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

1
Pytanie do nauki parzystości
Zdefiniujmy klasę funkcji w zbiorze bitów. Napraw dwa rozkłady które są „rozsądnie” różne od siebie (jeśli chcesz, ich odległość wariacyjna wynosi co najmniej lub coś podobnego).nnnp,qp,qp, qϵϵ\epsilon Teraz każda funkcja w tej klasie jest zdefiniowana przez zbiór indeksów i jest oceniana w następujący sposób: Jeśli parzystość wybranych bitów wynosi 0, …
1
Literatura na temat analizy aliasów
Piszę pracę magisterską w CS i pracuję nad analizą aliasów. To, co mnie interesuje, to intraproceduralne, wrażliwe na przepływ analizy must-may-may-alias dla języków podobnych do Java. Poszukuję tekstów, które szczegółowo opisują podstawy tego tematu, ale nie udało mi się znaleźć niczego naprawdę odpowiedniego. Przeżyłem wiele podręczników na temat kompilatorów i …
1
Czy pseudolosowość deterministyczna jest prawdopodobnie silniejsza niż przypadkowość równolegle?
Niech klasa BPNC (kombinacja i ) będzie algorytmami równoległymi głębokości dziennika z ograniczonym prawdopodobieństwem błędu i dostępem do losowego źródła (nie jestem pewien, czy to ma inną nazwę). Podobnie zdefiniuj klasę DBPNC, z tym wyjątkiem, że wszystkie procesy mają losowy dostęp do losowego strumienia bitów ustalonego przy uruchomieniu algorytmu.N CBPPBPP\mathsf{BPP}NCNC\mathsf{NC} …
1
Bilansowanie formuł boolowskich w
Szukam referencji na temat złożoności problemu równoważenia formuł logicznych . W szczególności, Czy było wiadomo, że formuły logiczne można wyważyć w AC0AC0\mathsf{AC^0} ? Czy istnieje prosty dowód na to, że równoważenie boolowskiej formuły jest w AC0AC0\mathsf{AC^0} ? Przez „proste” mam na myśli dowód prostsze niż ten wspominam poniżej, w szczególności …
1
Dlaczego dolne granice dla obwodów boolowskich nie implikują niższych granic obwodów arytmetycznych
Moje pytanie brzmi: dlaczego dolne granice dla głębokości 3 Obwody logiczne z bramkami „i” i „xor” dla wyznacznika nie oznaczają takich samych dolnych granic dla obwodów arytmetycznych w ?ZZ\mathbb{Z} Co jest nie tak z następującym argumentem: Niech będzie wyznacznikiem obliczającym obwód arytmetyczny, a następnie biorąc wszystkie zmienne mod 2 otrzymamy …
3
Jaka jest najszybciej znana symulacja BPP z wykorzystaniem algorytmów Las Vegas?
BPPBPP\mathsf{BPP} iZ P PZPP\mathsf{ZPP} to dwie podstawowe probabilistyczne klasy złożoności. B P PBPP\mathsf{BPP} jest klasą języków ustaloną przez probabilistyczne algorytmy Turinga w czasie wielomianowym, w których prawdopodobieństwo zwrotu nieprawidłowej odpowiedzi przez algorytm jest ograniczone, tzn. Prawdopodobieństwo błędu wynosi maksymalnie13)13\frac{1}{3} (zarówno dla wystąpień TAK, jak i NIE). Z drugiej strony, algorytmy …
1
Ile rozcięć krawędzi musi mieć DAG?
Następujące pytanie jest związane z optymalności Bellmana-Forda - najkrótsza droga algorytm programowania dynamicznego (patrz ten post dla połączenia). Pozytywna odpowiedź sugerowałaby również, że minimalny rozmiar monotonicznego niedeterministycznego programu do rozgałęziania dla problemu STCONN to . tssstttΘ(n3)Θ(n3)\Theta(n^3) Niech być DAG (skierowane acykliczny wykres) z jednym węzłem źródłowym jeden docelowego węzła . …
1
Błędy jednostronne w probablistycznych systemach dowodowych
W większości probabilistycznych systemów dowodowych (na przykład twierdzenie PCP) prawdopodobieństwa błędów są zwykle definiowane po stronie fałszywie dodatnich, tj. Typowa definicja może wyglądać tak: jeśli to weryfikator zawsze przyjmuje, ale w w innym przypadku prawdopodobieństwo odrzucenia wynosi co najmniej 1/2.x∈Lx∈Lx \in L Czy istnieje problem z dopuszczeniem wystąpienia błędu po …
2
O Inverse 3-SAT
Kontekst : Kavvadias i Sideri wykazali, że odwrotny problem 3-SAT jest coNP zakończony: Biorąc pod uwagę ϕϕ\phi zestaw modeli nnn zmiennych, czy istnieje wzór 3-CNF taki, że ϕϕ\phi jest jego dokładnym zestawem modeli? Powstaje formuła bezpośredniego kandydata, która jest połączeniem wszystkich 3-klauzul spełnionych przez wszystkie modele w ϕϕ\phi . Ponieważ …
1
Czy
W literaturze nie znalazłem stwierdzenia dotyczącego i ; wskazówki będą mile widziane.N P R PMAMA\mathsf{MA}NPRPNPRP\mathsf{NP}^\mathsf{RP} Wierzę, że są równi: N P R PMA⊆NPRPMA⊆NPRP\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP} : Maszyna zgaduje ciąg Merlina, a wyrocznia weryfikuje ciąg tak, jak Arthur.NPNP\mathsf{NP}RPRP\mathsf{RP} NPRP⊆MANPRP⊆MA\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA} : Merlin zgaduje obliczenia akceptujące maszyny , w tym wszystkie …
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.