Teoretyczne informatyka

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

5
Trudne do rozwiązania podkluczowe problemy z grafem twardym
W świetle ostatnich wyników Arory , Baraka i Steurera , Subexponential Algorytmy dla unikalnych gier i powiązanych problemów , interesują mnie problemy z grafem, które mają algorytmy czasu podwykładniczego, ale uważam, że nie jest to rozwiązanie wielomianowe. Znanym przykładem jest izomorfizm grafów, który ma algorytm subklonencjalny . Innym przykładem jest …
5
Weryfikacja unikalnych rozwiązań SAT
Rozważ następujący problem: biorąc pod uwagę formułę CNF i zadanie spełniające tę formułę, czy istnieje inne zadowalające przypisanie dla tej formuły? Jaka jest złożoność tego problemu? (Z pewnością jest w NP, ale czy to jest NP-trudne?) Co się stanie, jeśli nie otrzymasz zadania i chcesz po prostu zdecydować, czy formuła …
4
Dowody, bariery i P vs NP
Powszechnie wiadomo, że każdy dowód rozwiązujący pytanie P vs NP musi pokonać relatywizację , dowody naturalne i bariery algebrizacyjne . Poniższy schemat dzieli „przestrzeń próbną” na różne regiony. Na przykład RNRNRN odpowiada zestawowi dowodów relatywizujących i naturalizujących. GCTGCTGCT (Teoria złożoności geometrycznej) jest oczywiście ściśle poza regionem. Wymień kilka dowodów wraz …
4
Przecięcie DFA w przestrzeni subkwadratowej?
Przecięcie dwóch (minimalnych) DFA ze stanami n można obliczyć przy użyciu O (n 2 ) czasu i przestrzeni. Jest to ogólnie optymalne, ponieważ otrzymany (minimalny) DFA może mieć n 2 stanów. Jeśli jednak wynikowy minimalny DFA ma stany z, gdzie z = O (n), czy można go obliczyć w przestrzeni …
4
Dlaczego równości między klasami złożoności przekładają się w górę, a nie w dół?
Cześć chłopaki, rozumiem, że sztuczka dopełniania pozwala nam tłumaczyć klasy złożoności w górę - na przykład . Wypełnianie polega na „nadmuchiwaniu” danych wejściowych, uruchamianiu konwersji (powiedzmy od powiedzmy na ), co daje „magiczny” algorytm, który można uruchomić na wypełnionym wejściu. Chociaż ma to sens techniczny, nie mogę zrozumieć, jak to …
4
Jakie konkretne dowody istnieją dla P = RP?
RP to klasa problemów rozstrzyganych przez niedeterministyczną maszynę Turinga, która kończy się w czasie wielomianowym, ale dopuszczalny jest również błąd jednostronny. P jest zwykłą klasą problemów rozstrzyganych przez deterministyczną maszynę Turinga, która kończy się w czasie wielomianowym. P = RP wynika z zależności w złożoności obwodu. Impagliazzo i Wigderson wykazali, …
5
Problem z minimalną łącznością z klapką
Podczas gry z moim GPS sformułowałem następujący problem. Oto on: Niech będzie grafem ukierunkowanym, tak że jeśli to , tj. jest orientacją leżącego u jego podstaw wykresu niekierowanego. Rozważ następujące operacje:e = ( u , v ) ∈ E ( v , u ) ∉ E GG ( V, E)G(V,E)G(V,E)e …
4
Dlaczego potrzebujemy formalnej semantyki dla logiki predykatów?
Rozważ to pytanie rozwiązane. Nie wybiorę najlepszej odpowiedzi, ponieważ wszystkie one przyczyniły się do mojego zrozumienia tego tematu. Nie jestem pewien, jakie korzyści przyniesie nam formalne zdefiniowanie semantyki logiki predykatów. Ale widzę wartość posiadania formalnego rachunku próbnego. Chodzi mi o to, że nie potrzebowalibyśmy formalnej semantyki, aby uzasadnić reguły wnioskowania …
1
Odrzucenie dowodu: amatorskie recenzje ambitnych artykułów KR-u
Myślę, że przeczytałem zbyt wiele ambitnych artykułów KR-u . Problem polega na tym, że dokumenty te nie są recenzowane, ale często brzmią interesująco i przechodzą podstawowe kontrole wiarygodności. A może nie, a ja muszę tylko poprawić swoje kontrole wiarygodności. Oto ostatnia próbka takich dokumentów: Drzewa wyjątkowości: możliwe podejście wielomianowe do …
2
Czy można rozstrzygnąć, czy dany kształt może pokryć płaszczyznę?
Wiem, że nierozstrzygalne jest ustalenie, czy zestaw kafelków może kafelkować płaszczyznę, w wyniku Bergera korzystającego z kafelków Wanga . Moje pytanie brzmi: czy wiadomo również, że nierozstrzygalne jest ustalenie, czy pojedyncza dana płytka może ułożyć płytkę, monoedryczną płytkę. Jeśli to pozostanie nierozwiązane, chciałbym wiedzieć, jaka jest minimalna liczność zbioru płytek, …
4
Podręcznik zaawansowanych struktur danych
Szukam książki o zaawansowanych strukturach danych, która wykracza poza to, co jest zawarte w standardowych podręcznikach, takich jak Cormen, Leiserson, Rivest i „Wprowadzenie do algorytmów” Steina. Książka, która może być wykorzystana do nauczania kursów na poziomie zaawansowanym na temat zaawansowanych struktur danych, takich jak Erik Demaine i André Schulz, na …
2
Dlaczego Agda i Coq nie zgadzają się co do ścisłej pozytywności?
Natknąłem się na mylące spory między Agdą i Coq, które nie są oczywiście związane z najbardziej znanymi różnicami między ich teoriami typów (np. (Im) predykatywność, indukcja-rekurencja itp.). W szczególności Agda akceptuje następującą definicję: data Ty : Set0 -> Set0 where c1 : Ty ℕ c2 : Ty (Ty ℕ) podczas …
24 type-theory  coq 
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.