Teoretyczne informatyka

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

3
Sparametryzowana złożoność zestawu uderzeń w skończonym wymiarze VC
Interesuje mnie sparametryzowana złożoność problemu, który nazywam d-Dimensional Hitting Set: biorąc pod uwagę przestrzeń zakresu (tj. Układ zestawu / hipergraph) S = (X, R) mający wymiar VC co najwyżej d dodatnia liczba całkowita k, czy X zawiera podzbiór wielkości k, który uderza w każdy zakres w R? Sparametryzowana wersja problemu …
3
Wyjaśnienie klas P i NP za pomocą rachunku lambda
We wstępie i wyjaśnieniach klasy złożoności P i NP często podawane przez maszynę Turinga. Jednym z modeli obliczeń jest rachunek lambda. Rozumiem, że wszystkie modele obliczeń są równoważne (i jeśli możemy wprowadzić coś w kategoriach maszyny Turinga, możemy wprowadzić to w kategoriach dowolnego modelu obliczeń), ale nigdy nie widziałem wyjaśnienia …
3
Techniki pokazujące, że problemem jest twardość „otchłani”
Biorąc pod uwagę nowy problem w którego prawdziwa złożoność jest gdzieś pomiędzy P a ukończeniem NP, istnieją dwie metody, o których wiem, że mogą być wykorzystane do udowodnienia, że ​​rozwiązanie tego jest trudne:N P.N.P.\mathsf{NP}P.P.\mathsf{P} Pokaż, że problem dotyczy GI (GI = Graph Isomorphism) Pokazują, że problem w . Według znanych …
4
Twardość aproksymacji bez twierdzenia PCP
Ważnym zastosowaniem twierdzenia PCP jest to, że daje wyniki typu „twardość aproksymacji”. W niektórych stosunkowo prostszych przypadkach można udowodnić taką twardość bez PCP. Czy jest jednak jakikolwiek przypadek, w którym twardość wyniku aproksymacji została najpierw udowodniona przy użyciu twierdzenia PCP, tj. Wynik nie był wcześniej znany, ale później znaleziono bardziej …
3
Dlaczego losowość ma większy wpływ na redukcje niż na algorytmy?
Przypuszcza się, że losowość nie rozszerza potęgi algorytmów wielomianu czasowego, co oznacza, że jest przypuszczalny do utrzymania. Z drugiej strony losowość wydaje się mieć zupełnie inny wpływ na skrócenie czasu wielomianu . Według dobrze znanego wyniku Valiant i Vazirani, redukuje się do poprzez losowe wielomianowe skrócenie czasu. Jest mało prawdopodobne, …
3
Czy istnieje zapasowe / zastępcze zoo złożoności?
To pytanie nietechniczne, ale z pewnością istotne dla społeczności TCS. Jeśli zostanie to uznane za niewłaściwe, możesz je zamknąć. Witryna Zoo Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) z pewnością od lat cieszy się dużą popularnością wśród społeczności TCS. Wygląda na to, że od dłuższego czasu nie działa. Zastanawiałem się, czy ktoś nadal go …
6
Czasopisma z szybką recenzją
Tło: Motywacja tego pytania jest dwojaka. Po pierwsze, chciałbym uzyskać pewne twarde fakty, aby lepiej zrozumieć toczące się konferencje vs. debata w czasopismach . Po drugie, jeśli informacje te byłyby gdzieś dostępne, mógłbym podjąć bardziej świadomą decyzję, przesyłając dokumenty do przeglądu; Z przyjemnością faworyzuję czasopisma, których redaktorzy wykonują dobrą robotę, …
6
Złożoność algorytmu simpleks
Jaka jest górna granica algorytmu simpleks dla znalezienia rozwiązania dla programu liniowego? Jak mam znaleźć dowód na taką sprawę? Wydaje się, że najgorszym przypadkiem jest konieczność odwiedzenia każdego wierzchołka, czyli . Jednak w praktyce algorytm simpleks będzie działał znacznie szybciej niż w przypadku bardziej standardowych problemów.O ( 2n)O(2n)O(2^n) Jak mogę …
6
Czy zdałeś sobie kiedyś sprawę, że nie możesz rozwiązać zadania domowego, które przypisałeś?
To pytanie jest skierowane do osób, które przypisują problemy: nauczycieli, asystentów studentów, opiekunów itp. Zdarzyło mi się to kilka razy w mojej 12-letniej karierze profesora: pośpiesznie przypisałem jakiś problem z tekstu, myśląc, że „wygląda dobrze”. Później zrozumiał, że nie mogę tego rozwiązać. Niewiele rzeczy jest bardziej zawstydzających. Oto ostatni przykład: …
4
Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?
Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej: Wykorzystuje spację O (1) Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1) Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej …
3
Złożoność funkcji wykładniczej
Wiemy, że funkcja wykładnicza nad liczbami naturalnymi nie jest obliczalna w czasie wielomianowym, ponieważ wielkość wyjścia nie jest wielomianowo ograniczona wielkością danych wejściowych.exp( x , y) = xyexp⁡(x,y)=xy\exp(x,y) = x^y Czy jest to główny powód trudności w obliczeniu funkcji wykładniczej, czy też wykładnictwo wykładnicze jest z natury trudne do obliczenia, …
8
Wspólne narzędzia dla manekinów / profesorów
Załóżmy, że współautorzy z dwóch lub więcej różnych instytucji piszą papier w lateksie i chcieliby zrobić coś lepszego niż wielokrotne przesyłanie szkiców w tę iz powrotem. Zdają sobie sprawę, że mogą bezpłatnie otworzyć konto Dropbox, udostępnić hasło i zsynchronizować wersję papierową na swoim komputerze z wersją na Dropbox. Jeśli dwie …
7
Jaki jest najstarszy otwarty problem w TCS?
Ten problem jest inspirowany pytaniem MO , które moim zdaniem było bardzo interesujące. Jaki jest najstarszy otwarty problem w TCS? To pytanie wymaga wyjaśnienia. Po pierwsze, czym jest TCS? Myślę, że istnienie liczb nieparzystych idealnych nie jest TCS. Powiedziałbym, że dziesiątym problemem Hilberta jest TCS. Myślę, że problemy takie jak …
13
Łatwy problem decyzyjny, trudny problem wyszukiwania
Decyzja, czy istnieje równowaga Nasha, jest łatwa (zawsze tak jest); jednak znalezienie takiego uważa się za trudne (jest to PPAD-Complete). Jakie są inne przykłady problemów, w których wersja decyzyjna jest łatwa, ale wersja wyszukiwania jest stosunkowo trudna (w porównaniu z wersją decyzyjną)? Byłbym szczególnie zainteresowany problemami, w których wersja decyzyjna …
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.