Teoretyczne informatyka

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

3
Kiedy odprężenie się liczy?
Załóżmy, że rozwiązujemy problem zliczania prawidłowych zabarwień, licząc ważone zabarwienia w następujący sposób: każde prawidłowe zabarwienie otrzymuje wagę 1, a każde niewłaściwe zabarwienie otrzymuje wagę gdzie jest w pewnym stopniu stałe, a to liczba krawędzi z punktami końcowymi ma ten sam kolor. Gdy zmienia się na 0, sprowadza się to …
3
Problemy pośrednie między L i NL
Jest dobrze wiadomo, że skierowane st-łączność jest -Complete. Przełom wynik Reingold wykazała, że nieukierunkowane st-łączność jest w L . Płaskie skierowane st-łączności jest znany w U L ∩ C O U L . Cho Huynh zdefiniowano sparametryzowanego problemu plecakowego i wykazywał hierarchię problemów między L i N l .NLNLNLLLLUL∩coULUL∩coULUL \cap …
3
Czy NP jest trudny do prawidłowego grania w drafty międzynarodowe?
Czy następujący problem jest trudny NP? Biorąc pod uwagę konfigurację forum dla międzynarodowych projektów , znajdź jeden legalny ruch.n×nn×nn\times n Odpowiedni problem dla amerykańskich warcabów (inaczej angielskich wersji roboczych) można w prosty sposób rozwiązać w czasie wielomianowym. Istnieją trzy główne różnice między tymi dwiema grami.n×nn×nn\times n Pierwszą i najbardziej znaczącą …
3
Problemy naturalne w
Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w U P ∩ c o U P ?N.P.∩ c o NP.NP∩coNPNP \cap coNPUP.∩ c o UP.UP∩coUPUP \cap coUP Oczywiście wielki każdy wie o w jest wersja decyzja faktoringu (czy n mają …
4
Zakres ograniczonej liczności ograniczonej obejmuje: twardość aproksymacji
Rozważ problem minimalnego pokrycia zestawu z następującymi ograniczeniami: każdy zestaw zawiera co najwyżej kkk elementów, a każdy element wszechświata występuje w co najwyżej zestawach fff Na przykład: w przypadku k=4k=4k = 4 i f=2f=2f = 2 odpowiada minimalnej wierzchołek problemu pokrywy na wykresach z maksymalnym stopniem 4. Niech a(k,f)>1a(k,f)>1a(k,f) > …
3
Tłumaczenie SAT z HornSAT
Czy można przetłumaczyć wzór B logiczny na równoważną kombinację klauzul Horna? Artykuł w Wikipedii na temat HornSAT wydaje się sugerować, że tak, ale nie byłem w stanie ścigać żadnego odniesienia. Zauważ, że nie mam na myśli „w czasie wielomianowym”, ale raczej „w ogóle”.
5
Czy istnieją adnotowane formalne systemy weryfikacji dla czysto funkcjonalnych języków programowania?
ACSL (Ansi C Specification Language), to specyfikacja kodu C, opatrzona specjalnymi komentarzami, która pozwala na formalną weryfikację kodu C. Nie przyjrzałem się temu, ale wyobrażam sobie, że metody formalne stosowane w weryfikatorach ACSL byłyby podobne do Hoare Logic. Jednak w przypadku czysto funkcjonalnych języków, takich jak Haskell, nie mogę sobie …
5
Matematyczne implikacje teorii złożoności przypuszcza poza TCS
Czy znasz ciekawe konsekwencje (standardowych) przypuszczeń w teorii złożoności w innych dziedzinach matematyki (tj. Poza informatyką teoretyczną)? Wolałbym odpowiedzi gdzie: hipoteza teorii złożoności jest tak ogólna i standardowa, jak to możliwe; Nie przeszkadzają mi również konsekwencje twardości określonych problemów, ale byłoby miło, gdyby powszechnie uważano, że problemy są trudne (lub …
3
Kryptografia bez założeń - szukanie przeglądu
Załóżmy, że i jutro pojawi się szybki algorytm czasu liniowego dla SAT. Nagle RSA jest niepewny, znaczna część naszego nowoczesnego systemu komunikacji jest zepsuta i musimy ponownie rozważyć, jak zachować przed sobą tajemnice.P.= NP.P.=N.P.P = NP Pytanie: Czy istnieje dobre pojedyncze odniesienie (lub krótka lista), aby uzyskać ogólny obraz tego, …
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.