Teoretyczne informatyka

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

6
Program: Logiczne / formalne metody bezpieczeństwa
Obecnie prowadzę mały kurs (cztery dwugodzinne wykłady na poziomie magisterskim) na temat metod logicznych w zakresie bezpieczeństwa , chociaż tytuł Formalne metody w zakresie bezpieczeństwa może być bardziej trafny. Obejmuje krótko następujące tematy (wraz z powiązanymi metodami logicznymi): Cyfrowe zarządzanie prawami i egzekwowanie zasad (ogólna formalizacja, logika modalna, egzekwowanie za …
7
Znajdowanie bliźniaczych wierzchołków na wykresach
Niech będzie wykresem. Przez wierzchołek , określa za (otwarty) sąsiedztwie w . To znaczy, . Zdefiniuj dwa wierzchołki w aby były bliźniakami, jeżeli i mają ten sam zestaw sąsiadów, to znaczy, jeśli .G=(V,E)G=(V,E)G=(V,E)x∈Vx∈Vx\in VN(x)N(x)N(x)xxxGGGN(x)={y∈V|{x,y}∈E}N(x)={y∈V|{x,y}∈E}N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}u,vu,vu,vGGGuuuvvvN(u)=N(v)N(u)=N(v)N(u)=N(v) Biorąc pod uwagę wykres na wierzchołkach i krawędziach jako dane wejściowe, jak …
2
Czy do nieświadomego wykonania kodu można zastosować w pełni homomorficzne szyfrowanie?
Po przeczytaniu tej odpowiedzi jakiś czas temu zainteresowałem się w pełni homomorficznym szyfrowaniem. Po przeczytaniu wstępu pracy Gentry'ego zacząłem się zastanawiać, czy jego schemat szyfrowania może zostać użyty do nieświadomego wykonania kodu, jak określono w trzecim akapicie. W całkowicie homomorficznym schemacie szyfrowania zazwyczaj szyfrujemy niektóre dane, wysyłamy je do wrogiego …
1
Ile mocy obliczeniowej mieści się w centymetr sześcienny?
To pytanie stanowi odpowiedź na pytanie o algorytmy DNA zadane przez Aaditę Mehrę . W komentarzach Joe Fitzsimmons powiedział częściowo: Promień układu musi być skalowany proporcjonalnie do masy, aby tego uniknąć. Moc obliczeniowa jest skalowana co najwyżej liniowo w masie. Zatem twoja wykładnicza ilość maszyn ma wykładniczy promień. Ponieważ nie …
1
Mnożenie binarne i splot parzystości
To pytanie dotyczy związku między normalnym mnożeniem liczb binarnych a wielomianowym mnożeniem mod 2. Aby uczynić pytanie konkretnym, idealnie chciałbym wiedzieć, czy istnieje lepsze rozwiązanie pytania z Knuth vol. 2, wydanie trzecie, strona 420 niż podano w książce. „Czy mnożenie wielomianów modulo 2 można ułatwić, stosując zwykłe operacje arytmetyczne na …
4
Wybór społeczny, twierdzenie strzały i otwarte problemy?
W ostatnich miesiącach zacząłem wykładać na temat wyboru społecznego, twierdzenia strzały i powiązanych wyników. Po przeczytaniu o przełomowych wynikach zadałem sobie pytanie, co dzieje się z częściowymi preferencjami porządku, odpowiedź znajduje się w pracy Pini i in. : Agregowanie częściowo uporządkowanych preferencji: wyniki niemożliwości i możliwości . Następnie zastanawiałem się, …
2
Czy można zaniedbać koszt GC, analizując czas działania najgorszych struktur danych określonych w zbędnym języku programowania?
Właśnie zdałem sobie sprawę, że zakładam, że odpowiedź na moje pytanie brzmi „tak”, ale nie mam dobrego powodu. Wyobrażam sobie, że może istnieje śmieciarz, który prawdopodobnie wprowadza tylko spowolnienie w najgorszym przypadku. Czy istnieje ostateczne odniesienie, które mogę zacytować? W moim przypadku pracuję nad czysto funkcjonalną strukturą danych i używam …
2
Multiplikatywna wersja 3-SUM
Co wiadomo na temat złożoności czasowej następującego problemu, który nazywamy 3-MUL? Biorąc pod uwagę zestaw z liczb całkowitych, czy są elementami taki sposób, że ?SSSnnna,b,c∈Sa,b,c∈Sa,b,c\in Sab=cab=cab=c Ten problem jest podobny do problemu 3-SUM, który pyta, czy istnieją trzy elementy tak, że (lub równoważnie ). Przypuszcza się, że 3-SUM wymaga czasu …
2
Algorytmy aproksymacji czasu wielomianowego do planowania maszyny: ile pozostało otwartych problemów?
W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc świetnie i przydatne, gdyby każdy z nas mógł sporządzić …
2
Czy istnieją lokalne maksima w liczbie ruchów wymaganych do rozwiązania Kostki Rubika?
Peter Shor poruszył interesujący punkt w związku z próbą odpowiedzi na wcześniejsze pytanie dotyczące złożoności rozwiązania kostki Rubika n×n×nn×n×nn \times n \times n . Podjąłem dość naiwną próbę wykazania, że ​​musi być zawarta w NP. Jak zauważył Peter, moje podejście w niektórych przypadkach zawodzi. Jednym z potencjalnych przypadków takiego wystąpienia …
2
Czy „teoria złożoności eksperymentalnej” jest używana do rozwiązywania otwartych problemów?
Scott Aaronson zaproponował interesujące wyzwanie : czy możemy dziś wykorzystać superkomputery, aby pomóc rozwiązać problemy z CS w taki sam sposób, w jaki fizycy używają zderzaczy dużych cząstek? Mówiąc konkretniej, moja propozycja polega na poświęceniu części światowej mocy obliczeniowej na całkowitą próbę odpowiedzi na następujące pytania: czy obliczenie stałej macierzy …
8
Inne rodzaje analizy czasu pracy oprócz najgorszego przypadku, średniego przypadku itp.?
Oto kilka sposobów analizy czasu działania algorytmu: 1) Analiza najgorszego przypadku: czas działania w najgorszym przypadku. 2) Analiza średnich przypadków: oczekiwany czas działania w przypadkowej instancji. 3) Amortyzowana analiza: średni czas działania w najgorszej sekwencji przypadków. 4) Wygładzona analiza: oczekiwany czas działania w najgorszym przypadkowo zaburzonym wystąpieniu. 5) Analiza przypadków …
2
W jaki sposób podejście geometryczne Mulmuleya-Sohoniego do wytwarzania dolnych granic unika tworzenia naturalnych dowodów (w sensie Razborowa-Rudicha)?
Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód występujących w pytaniu P / poli kontra NP (brak relatywizacji, brak algebrazowania, prawdopodobnie …
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.