Teoretyczne informatyka

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

2
Określanie, co można osiągnąć przez permutację elementów grupy nieprzemiennej
Ustalić skończoną grupę . Interesuje mnie następujący problem decyzyjny: dane wejściowe to niektóre elementy G z częściowym porządkiem na nich, a pytanie brzmi, czy istnieje permutacja elementów, która spełnia porządek i jest taka, że ​​skład elementów w tym porządek daje neutralny element grupy e .GGGGGGeee Formalnie problem testu GGG jest …
2
Konsekwencja PIT w stosunku do bez wydajnego algorytmu
Biorąc pod uwagę tak, że współczynniki są ograniczone przez , czy trzymać?p , q B p ≡ qp(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.Z⊂QZ⊂Q\Bbb Z\subset\Bbb Q Oczekujemy, że ten problem będzie miał skuteczną derandomizację. Jakie …
3
Złożoność obliczania parzystości odczytu dwukrotnego przeciwnego do wzoru CNF (
W dwukrotnej, przeciwnej do odczytu formule CNF, każda zmienna pojawia się dwukrotnie, raz dodatnia, a raz ujemna. Jestem zainteresowany w problem, który polega na obliczaniu parytetu liczby spełniających zadania o przeciwnej wzoru CNF odczytu dwukrotnie.⊕ Rtw-Opp-CNF⊕Rtw-Opp-CNF\oplus\text{Rtw-Opp-CNF} Nie udało mi się znaleźć odniesienia do złożoności takiego problemu. Najbliższe, jakie udało mi …
1
W jakim stopniu zdolność obliczeniowa trudnych zadań pomaga w rozwiązywaniu łatwych zadań
Krótko mówiąc, pytanie brzmi: w jakim stopniu zdolność obliczeniowa do trudnych zadań naprawdę pomaga w rozwiązywaniu łatwych zadań. (Mogą istnieć różne sposoby uczynienia tego pytania interesującym i nietrywialnym, a oto jedna z takich prób). Pytanie 1: Rozważ obwód rozwiązywania SAT dla formuły z n zmiennymi. (Lub do znalezienia cyklu hamiltonowskiego …
1
Oblicz najniższy wymiarowy polytop z danego zestawu wektorów znakowych
Biorąc pod uwagę zestaw hiperpłaszczyzn określonych przez wektory normalne , wszystkie typy komórek (lub wektory znakowe) to wszystkie wektory t ∈ { + , - } m, dla których istnieje wektor tak, że i dla wszystkich . W tym przypadku oznacza wewnętrzny produkt, a oznacza znak ( lubh1,…,hm∈Rdh1,…,hm∈Rdh_1,\dots,h_m \in \mathbf …
2
Ograniczona liczba zmiennych wystąpień w SAT 1-w-3
Czy jest znany wynik dotyczący klasy złożoności 1-w-3-SAT z ograniczoną liczbą zmiennych zdarzeń? Wymyśliłem następującą oszczędną redukcję u Petera Nightingale'a, ale chcę zacytować coś, jeśli jest to znane. Oto sztuczka, którą wymyśliliśmy. To pokazuje, że 1-w-3-SAT ograniczony do 3 wystąpień na zmienną jest NP kompletny i #P zakończony (ponieważ 1-w-3-SAT …
6
Czy w teoretycznym CS są jakieś tematy, które bardziej dotyczą czystej matematyki?
Jestem absolwentem informatyki teoretycznej, aw szczególności algorytmów aproksymacyjnych. Teraz uważam, że bardziej interesuje mnie czysta matematyka (mogę to powiedzieć, ponieważ wydaje mi się, że bardziej podobały mi się kursy matematyki niż kursy CS). Chciałbym zapytać, czy istnieją obszary w informatyce teoretycznej, które są prawie czystą matematyką (mówiąc ściślej, dziedziną, która …
3
Rozgałęzienie teorii typu impredykatywnego
Większość teorii typów, które znam, są predykcyjne, przez co mam na myśli to Void : Prop Void = (x : Prop) -> x nie jest dobrze wpisany w większość dowodów twierdzeń, ponieważ ten typ pi należy do tego samego wszechświata co Propi tak nie jest Prop : Prop. To czyni …
4
Czy istnieje algorytmiczna analiza matematyczna?
Istnieją teorie grafów algorytmicznych / teoria liczb / kombinatoryka / teoria informacji / teoria gier. Czy istnieje algorytmiczna analiza matematyczna? Według wiki analiza matematyczna obejmuje teorie różniczkowania, całkowania, miary, limitów, szeregów nieskończonych i funkcji analitycznych. Można skupić się na analizie rzeczywistej (wiki), która zajmuje się liczbami rzeczywistymi i funkcjami wartości …
2
Zabawa z odwrotnym Ackermannem
Odwrotna funkcja Ackermanna występuje często podczas analizy algorytmów. Świetna prezentacja tego jest tutaj: http://www.gabrielnivasch.org/fun/inverse-ackermann . i [Notacja: [x] oznacza, że ​​zaokrąglamy w górę x do najbliższej liczby całkowitej, podczas gdy log ∗ omówiono tutaj iterowaną funkcję dziennika: http://en.wikipedia.org/wiki/Iterated_logarithm ]α1(n)=[n/2]α1(n)=[n/2]\alpha_1(n) = [n/2] α2(n)=[log2n]α2(n)=[log2⁡n]\alpha_2(n) = [\log_2 n] α3(n)=log∗nα3(n)=log∗⁡n\alpha_3(n) = \log^* n ......... …
1
Ramy logiczne a teoria typów
Jaka jest różnica między strukturą logiczną a teorią typów? Oba mają typy, terminy i są oparte na rachunku lambda zależnym od typu. Mamy Edinburg LF, który opiera się na rachunku lambda-pi, jednak wydaje mi się, że istnieje tam subtelna różnica.
1
Co to jest „pseudo-czas” w porównaniu z semaforami
Obecnie słucham przemówienia Alana Kaysa „Czy to naprawdę skomplikowane, czy tylko skomplikowaliśmy?” ( Https://www.youtube.com/watch?v=ubaX1Smg6pY&= ), w którym mówi, że „semafory były złym pomysłem i nie było coś, co nazywa czas pseudo że była lepsza” (at 51:40 na połączonego materiału wideo). Może źle zrozumiałem słowo „pseudo-czas”, ale czy wiesz coś o …
1
Słowa Fibonacciego
W moim starym czeskim podręczniku algorytmów natknąłem się na następujący problem, niestety przyszedł bez wskazówek i rozwiązania. „Określamy Fibonacciego słów , , , gdzie i są ogólnie literami. Jak w danej ciąg (ponad potencjalnie dużym alfabetem) czy możesz znaleźć najdłuższe pod-słowo Fibonacciego w czasie liniowym? ”F 1 = b F …
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.