Obecnie rozpoczynam naukę na uniwersytecie [informatyka] i tam mamy wiele możliwości, aby zacząć od badań. Przed znalezieniem tej witryny nie miałem zamiaru iść tą drogą [chciałem pracować z AI, prawdopodobnie twórcą gry], ale teraz mogę [lub muszę] dokonać wyboru. Czy możesz mnie przekonać do...
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...
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...
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;...
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...
Ogólnie wiemy, że złożoność testowania, czy funkcja przyjmuje określoną wartość na danym wejściu, jest łatwiejsza niż ocena funkcji na tym wejściu. Na przykład: Ocena stałej nieujemnej liczby całkowitej jest # P-trudna, ale powiedzenie, czy taka stała jest zerowa czy niezerowa jest w P...
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...
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...
Zapytaj nawet kogoś, kto ma doświadczenie w informatyce, co to jest wyrażenie regularne, a odpowiedź prawdopodobnie wykroczy poza ograniczenie bycia w zasięgu automatu skończonego. Na przykład „wyrażenie regularne” /^1?$|^(11+?)\1+$/ stworzona przez znaną osobowość Perla Abigail (i część...
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...
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...
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...
Szukam źródła ogromnych zestawów danych do przetestowania implementacji algorytmu grafowego. Proszę również podać informacje o typie / rozkładzie (np. Skierowane / nieukierowane, proste / nie proste, ważone / nieważone) wykresów w źródle, jeśli są one
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...
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...
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ą)?...
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...
G=(V,E,w)G = (V, E, w)w:E→Rw:E\rightarrow \mathbb{R}arg max S ⊂ V ∑ ( u , v ) ∈ E : u ∈ S , v ∉ S w ( u , v ) w ( e ) ≥ 0 e ∈ EargmaxS⊂V∑(u,v)∈E:u∈S,v∉Sw(u,v)\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)w(e)≥0w(e) \geq 0e∈Ee \in E Odbiór losowego podzbioru wierzchołki...
Niech AAA będzie stałą dodatnią liczbą całkowitą o rozmiarze nnn bitów. Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą. Biorąc pod uwagę kolejną dodatnią liczbę całkowitą BBB o rozmiarze mmm bitów, jaka jest złożoność mnożenia ABABAB ? ϵ =...
Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Możesz zrobić czas , stosując FFT w sposób...