Teoretyczne informatyka

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

2
Status w dolnych granicach obwodu dla obwodów głębokości ograniczonych przez polilog
Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej, stałej głębokości, wielomianu, nieograniczonego wachlarza …
1
Asymptotycznie, ile permutacji
Rozważ permutację σσ\sigma wynoszącą [ 1 .. n ][1 ..n][1..n] . Inwersję definiuje się jako parę ( i , j )(ja,jot)(i, j) indeksów takich, że ja &lt; jja&lt;joti < j i σ( i ) &gt; σ( j )σ(ja)&gt;σ(jot)\sigma(i) > \sigma(j) . Zdefiniuj ZAkZAkA_k jako liczbę permutacji [ 1 .. n …
2
Jakie są przypuszczenia TCS, które zostały udowodnione dla liczb pierwszych i małych wartości, ale okazały się fałszywe?
Czy są jakieś przypuszczenia w informatyce teoretycznej, które dotyczą jakiegoś parametru n i zostały udowodnione dla małych wartości n AND dla liczb pierwszych, ale później okazały się fałszywe? W teorii liczb takie problemy istnieją, np. jak wskazuje Aaron Meyerowitz na temat współczynników wielomianów cyklotomicznych. Z TCS znam tylko takie przykłady, …
17 big-list  primes 
1
Czy PRIMEGAME Conwaya generuje wszystkie podstawowe moce 2?
Większość stron, które odwiedziłem czytając ten interesujący temat, podaje coś podobnego „jedynymi potęgami dwóch (innych niż 2), które występują w tej sekwencji, są te z głównym wykładnikiem potęgi” (MathWorld) lub „Po 2 sekwencja ta zawiera następujące potęgi 2: [...], które są podstawowymi potęgami 2”. (Wikipedia) Te staranne sformułowania sugerowałyby, że …
1
Przyspieszenia wielomianowe z algorytmami opartymi na programowaniu półfinałowym
Jest to kontynuacja ostatniego pytania zadanego przez A. Pala: Rozwiązywanie programów półfinałowych w czasie wielomianowym . Nadal zastanawiam się nad faktycznym czasem działania algorytmów obliczających rozwiązanie programu półfinałowego (SDP). Jak zauważył Robin w swoim komentarzu do powyższego pytania, SDP-ów nie można ogólnie rozwiązać w czasie wielomianowym. Okazuje się, że jeśli …
1
Rozwiązywanie programów półfinałowych w czasie wielomianowym
Wiemy, że programy liniowe (LP) można rozwiązać dokładnie w czasie wielomianowym za pomocą metody elipsoidy lub metody punktu wewnętrznego, takiej jak algorytm Karmarkara. Niektóre LP z super-wielomianową (wykładniczą) liczbą zmiennych / ograniczeń można również rozwiązać w czasie wielomianowym, pod warunkiem, że możemy dla nich zaprojektować wielomianową wyrocznię z separacją czasu. …
7
Wskaźniki dla logicznych aplikacji CS
Jestem studentem matematyki z solidnym doświadczeniem w logice. Wziąłem roczny kurs magisterski z logiki wraz z kursami absolwentów teorii modeli skończonych, a także teorii wymuszania i teorii mnożenia. Większość tekstów CS wydaje się przyjmować jedynie bardzo skromne tło logiki, które w większości obejmuje podstawy logiki zdań i logiki pierwszego rzędu. …
1
Jakie są podrodziny # P-complete z # 2-SAT?
Krótka wersja. Oryginalny dowód, że # 2-SAT jest #P- kompletny, pokazuje w rzeczywistości, że te przypadki # 2-SAT, które są zarówno monotoniczne (nie obejmujące negacji żadnych zmiennych), jak i dwustronne (wykres utworzony przez klauzule nad zmienne to wykres dwustronny) są # P-twarde . Zatem dwa specjalne przypadki # 2-MONOTONE-SAT i …
2
Delikatne wprowadzenie do izomorfizmu grafów dla grafów o ograniczonej wartościowości
Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi referencje o charakterze ekspozycyjnym. Nie mam silnego doświadczenia …
2
Języki jednoargumentowe rozpoznawane przez dwustronne deterministyczne automaty licznikowe
2dca (dwukierunkowe deterministyczne automaty licznikowe) (Petersen, 1994) może rozpoznać następujący jednoargumentowy język: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Czy jest jakiś inny nietrywialny, unary język rozpoznawany przez 2dca? Zauważ, że nadal nie wiadomo, czy 2dca może rozpoznać ?SQUARE={0n2∣n≥0}SQUARE={0n2∣n≥0} \mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq …
1
Które wyniki sprawiają, że przestrzeń kwantowa jest interesująca?
Obliczenia kwantowe ograniczone w czasie są oczywiście bardzo interesujące. A co z obliczeniami kwantowymi ograniczonymi przestrzenią? Znam wiele interesujących wyników obliczeń kwantowych z sublogarytmicznymi granicami przestrzeni i różnego rodzaju modelami automatów kwantowych. Z drugiej strony wykazano, że probabilistyczna i kwantowa przestrzeń bez ograniczeń związanych z błędem jest równoważna dla dowolnej …
2
Czy w praktyce wykorzystywane są teoretycznie generatory pseudolosowe?
O ile mi wiadomo, większość implementacji generowania liczb pseudolosowych w praktyce wykorzystuje metody, takie jak rejestry sprzężenia zwrotnego z przesunięciem liniowym (LSFR) lub te algorytmy „Mersenne Twister”. Chociaż zdają wiele (heurystycznych) testów statystycznych, nie ma teoretycznych gwarancji, że wyglądają pseudolosowo, powiedzmy, na wszystkie skutecznie obliczalne testy statystyczne. Jednak metody te …
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.