Teoretyczne informatyka

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

3
Dlaczego różnicowe współczynniki aproksymacji nie są dobrze zbadane w porównaniu ze standardowymi pomimo deklarowanych korzyści?
Istnieje standardowa teoria aproksymacji, w której stosunek aproksymacji wynosi supAOPTsupAOPT\sup\frac{A}{OPT} (dla problemów zcelamiMINMINMIN),AAA- wartość zwracana przez niektóre algorytmyAAAiOPTOPTOPT- wartość optymalna. I inna teoria, żeprzybliżenie różnicowe,gdzie stosunek przybliżenia wynosiinfΩ−AΩ−OPTinfΩ−AΩ−OPT\inf\frac{\Omega-A}{\Omega-OPT} ,ΩΩ\Omega- najgorsza wartość wykonalnego rozwiązania dla danego wystąpienia. Doautorówz tego twierdzenia teorii, że ma jakieś konkretne korzyści w stosunku do klasycznego jednego. …
2
Złożoność czasowa algorytmu Bellmana-Helda-Karpa dla TSP, weź 2
Ostatnie pytanie dotyczyło teraz klasycznego algorytmu programowania dynamicznego dla TSP, niezależnie od Bellmana i Held-Karpa . Algorytm jest powszechnie zgłaszany do działania w czasie . Jednak, jak niedawno zauważył jeden z moich studentów, ten czas działania może wymagać nieracjonalnie silnego modelu obliczeń.O(2nn2)O(2nn2)O(2^n n^2) Oto krótki opis algorytmu. Dane wejściowe składają …
2
Znalezienie największego zestawu punktów o ograniczonej średnicy
Biorąc pod uwagę punkty w i odległość znajduję największy podzbiór tych punktów, tak że odległość euklidesowa nie jest większa niż .p1, … , Snp1,…,pnp_1,\ldots,p_nRreRre\mathbb{R}^{d}llllll Jaka jest złożoność tego problemu? Na wykresie nad punktami, które mają krawędź, ilekroć odległość dwóch punktów wynosi co najwyżej , problem jest równoznaczny ze znalezieniem maksymalnej …
1
Złożoność decydowania, czy rodzina jest rodziną Sperner
Otrzymujemy rodzinę składającą się z m podzbiorów {1, ..., n}. Czy można znaleźć nietrywialną dolną granicę złożoności decydowania, czy F jest rodziną Spernerów? Trywialna dolna granica to O ( n m ) i mocno podejrzewam, że nie jest ciasna.FF\mathcal{F}mmmFF\mathcal{F}O(nm)O(nm)O(n m) Przypomnij sobie, że zestaw jest rodziną Spernerów, jeśli dla X …
5
Czy „Funkcje jednokierunkowe” mają jakieś aplikacje poza kryptografią?
Funkcja jest jednokierunkowa, jeśli f można obliczyć za pomocą algorytmu wielomianowego czasu, ale dla każdego losowego algorytmu wielomianowego czasu A ,f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^*fffAAA Pr[f(A(f(x)))=f(x)]&lt;1/p(n)Pr[f(A(f(x)))=f(x)]&lt;1/p(n)\Pr[f(A(f(x))) = f(x)] < 1/p(n) dla każdego wielomianu i wystarczająco dużego n , przy założeniu, że x jest wybrany równomiernie z { 0 …
7
Organizacja danych badawczych
To pytanie w duchu tego , na które odpowiedziałem, że ważne jest, aby śledzić, co zrobiłeś, dlaczego to zrobiłeś, a co nie działa. Osobiście używam do tego celu notebooków, ale ma to kilka wad: po pierwsze potrzebuję dużo miejsca do przechowywania, po drugie, kiedy podróżuję, nie mam dostępu do moich …
2
Co wiemy o ograniczonych wersjach problemu zatrzymania
( AKTUALIZACJA : postawiono tutaj lepiej sformułowane pytanie , ponieważ komentarze do przyjętej odpowiedzi poniżej pokazują, że to pytanie nie jest dobrze zdefiniowane) Klasyczny dowód na niemożność problemu zatrzymania zależy od wykazania sprzeczności przy próbie zastosowania algorytmu wykrywania zatrzymania jako danych wejściowych. Aby uzyskać więcej informacji, zobacz tło poniżej. Wykazana …
1
Znaczenie P = NP? zależy od geometrii czasoprzestrzennej?
To pytanie dotyczy strony 125 książki „Automaty komórkowe w przestrzeniach hiperbolicznych: tom 2” Maurice Margenstern, Archiwa wydawców współczesnych, 2008. http://books.google.com/books?id=eEgvfic3A4kC&amp;pg=PA125 Zdaniem autora pytanie P = NP jest źle postawione, ponieważ w ustawieniu hiperbolicznym P = NP lub w notacji używanej później w książce P h = NP h . Nie …
2
Czy zaangażowanie bitowe daje nieświadomy transfer w modelu bezpieczeństwa opartym na teorii informacji?
Załóżmy, że masz dwóch arbitralnie silnych uczestników, którzy sobie nie ufają. Mają dostęp do bitowego zaangażowania (np. Zapieczętowane koperty zawierające dane, które jeden gracz może przekazać drugiemu, ale których nie można otworzyć, dopóki pierwszy gracz nie da drugiemu klucza). Czy możesz to wykorzystać do zbudowania nieświadomego protokołu przesyłania. Czy to …
2
Lawina jak proces stochastyczny
Rozważ następujący proces: Istnieje nnn pojemników ułożonych od góry do dołu. Początkowo każdy pojemnik zawiera jedną kulkę. Na każdym kroku my wybierz losowo piłkę równomiernie ibbb przenieś wszystkie kule z pojemnika zawierającego bbb do pojemnika poniżej. Jeśli był to już najniższy kosz, usuwamy kulki z procesu. Ile kroków wymaga oczekiwania …
1
Odniesienia do wykresów wolnych od (nieparzystych, dziurawych)?
Wykresy wolne od X to te, które nie zawierają wykresu z X jako indukowanego podgrupy. Otwór jest cykl co najmniej 4 wierzchołków. Odd-dziura jest dziura z nieparzystej liczby wierzchołków. Antihole jest dopełnieniem otworem. Wykresy wolne od (nieparzystej dziury, nieparzystej antihole) są dokładnie idealnymi grafami; to jest twierdzenie Strong Perfect Graph …
1
Złożoność heksów z losową kolejnością tur.
Myślałem o wariancie heksowym , w którym zamiast dwóch graczy wykonujących ruchy na przemian, każda kolej losowo wybrana przez gracza wykonuje ruch. Jak trudno jest określić szanse wygranej każdego gracza? Ten problem występuje oczywiście w PSPACE, ale nie może być trudny do NP, a tym bardziej kompletny w PSPACE. Trudności …
1
Separacja między zgrubnie skorelowanych równowag i skorelowanych równowag
Szukam przykładów technik dowodzenia ceny granic anarchii, które mogą oddzielić cenę anarchii od zgrubnie skorelowanych równowag (ograniczający zestaw dynamiki bezżałowania zewnętrznego) od ceny anarchii nad skorelowanymi równowagami (ograniczenie zestaw dynamiki bez żalu). Czy znane są naturalne separacje tego typu? Jedną z przeszkód w rozdzielaniu tych dwóch klas jest to, że …
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.