Biorąc pod uwagę deterministyczną grę z sumą zerową z częściową informacją i tylko skończoną liczbą stanów, których możliwymi rezultatami są odpowiednio [przegrana, remis, wygrana] o wartościach odpowiednio [-1,0, + 1], jaka jest złożoność przybliżenia wartości takich gra w dodatku...
Czy wiemy, że hierarchia się nie zwija ( dla wszystkich d )?TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd Wpis do zoo dla TC0TC0\mathsf{TC^0} wspomina tylko o separacji między głębokością 2 i 3. Czy istnieje również standardowe odniesienie do faktu, że...
To interesujące pytanie znalazłem w Internecie. Biorąc pod uwagę tablicę zawierającą n liczb (bez informacji o nich), powinniśmy wstępnie przetworzyć tablicę w czasie liniowym, abyśmy mogli zwrócić k najmniejszych elementów w czasie O (k), gdy otrzymamy liczbę 1 <= k <= n Dyskutowałem o tym...
Czy możemy udowodnić ostry wynik koncentracji na sumie niezależnych wykładniczych zmiennych losowych, tj. Niech będą niezależnymi zmiennymi losowymi takimi, że . Niech . Czy możemy udowodnić granice postaci . Wynika to bezpośrednio, jeśli użyjemy formy wariancji granic chernoffa i dlatego uważam,...
To pytanie jest motywowane tym postem. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? oraz moje zainteresowanie obliczeniowymi właściwościami permutacji. Sekwencja różnic permutacji π liczb 1 , 2 , … n + 1 jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi...
Mam naprawdę duży niedeterministyczny automat skończony i muszę go przekonwertować na DFA. Przez duże rozumiem ponad 40 000 stanów. Do tej pory przeprowadziłem kilka eksperymentów i zaprogramowałem domyślny algorytm, który przeszukuje tabelę (jak opisano tutaj ), ale nawet po optymalizacji jest...
Jakie są konkretne i przekonujące zastosowania do szacowania objętości wypukłych wielościanów tego rodzaju, rozważanych w nowszych artykułach na temat metod losowego chodzenia? W tych pracach dotyczących szacowania objętości jako jedną z motywacji wymieniono integrację numeryczną. Jakie są...
Ten dokument stanowi dowód, że w grze z drzwiami i płytkami dociskowymi trudno jest ustalić, czy awatar (gracza) może dotrzeć do danego miejsca. Dowodzi tego redukcja z TQBF , a długość powstałych rozwiązań zależy wykładniczo od liczby uniwersalnych kwantyfikatorów we wzorze. Czy istnieje redukcja...
Nauczyłem się czegoś o implementowaniu typów zależnych, takich jak ten samouczek , ale większość z nich to implementacja tłumaczy. Moje pytanie brzmi: wydaje się, że implementacja kompilatora dla typu zależnego jest znacznie trudniejsza niż kompilator, ponieważ naprawdę można ocenić argumenty typu...
Czy w kolejce liczb całkowitych priorytetowych, która używa słów spacji z następującymi operacjami, wszystko w najgorszym przypadku i bez dostępu do losowości:O(n)O(n)O(n) createEmptyQueuew dla pewnej stałej c .O(lgcU)O(lgcU)O(lg^c U)ccc insertw
Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w...
Zawarte w między każdym poziomie hierarchii wielomianowej złożoności są różne klasy, w tym , DP , BH k oraz Σ P I ∩ Õ P ja . Z powodu braku lepszej terminologii będę odwoływał się do tych i innych klas pośrednich między poziomami i i i + 1 w hierarchii wielomianowej. Dla celów tego pytania,...
Niedawno zacząłem dużo czytać o złożoności dowodów i bardzo podobało mi się to, co czytałem. Naprawdę chciałbym dowiedzieć się więcej na ten temat, ale mam trudności ze znalezieniem dobrego materiału dla początkujących. Czy ktoś mógłby polecić jakieś
Całkiem podobne do mojego wcześniejszego pytania . Tym razem jednak wykres nie jest przekierowany. Dany Nieukierunkowane wykres solGG bez wielu krawędzie lub pętli Źródło wierzchołek sss , Docelowy wierzchołek ttt , Maksymalna długość ścieżki lll , Szukam sol′G′G' - podgraf solGG który...
Próbuję zrozumieć, do której klasy złożoności należy następujący problem: Wykładniczy wielomianowy problem z korzeniem (EPRP) Niech będzie wielomianem o deg ( p ) ≥ 0 ze współczynnikami wyciągniętymi z pola skończonego G F ( q ) z q liczbą pierwszą, a r pierwotnym pierwiastkiem dla tego pola....
Jakie są znane granice rozstrzygalności porównania szybkości wzrostu funkcji z ? Mam na myśli rozstrzygalność pytań takich jak „Czy x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?” lub „Czy 2 lg ∗ x ∈ O ( lg lg x ) ?”.N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg(x+2)⌋x^x \sim 2^{\lfloor x \lg (x+2)...
Szukam odniesień bibliograficznych dla następującego algorytmu / problemu: nazwałem go „BiSelect” lub „t-ary Select” lub „Select in Union of Sorted Arrays”, ale myślę, że został wprowadzony wcześniej pod inną nazwą? Problem Rozważ następujący problem: Biorąc pod uwagę kkk rozłożonych tablic...
Przeczytałem artykuł Freyda „Algebraicznie kompletne kategorie” w słynnym Como90 i mam dwa pytania dotyczące pojęcia zwartości algebraicznej zdefiniowanej w tym artykule. (Jeśli nie znasz tej definicji, oto ona: Kategoria nazywa się zwartą algebraicznie, jeśli każdy endofunkor ma początkową algebrę...
Instancja: Niekierowany wykres GsolG z dwoma wyróżniającymi się wierzchołkami i liczbą całkowitą .s≠ts≠ts\neq tk≥2k≥2)k\geq 2 Pytanie: Czy istnieje ścieżka w , taka, że ścieżka dotyka co najwyżej wierzchołków? (Ścieżka dotyka wierzchołka, jeśli wierzchołek znajduje się na ścieżce lub ma ścieżkę...
Definicja „zestawu algebraicznego” w ciągłych sieciach i domenach , definicja I-4.2, mówi, że dla wszystkich ,x ∈ L.x∈Lx \in L zbiór powinien być zbiorem ukierunkowanym, iA ( x ) = ↓ x ∩ K( L )A(x)=↓x∩K(L)A(x) = {\downarrow} x \cap K(L) .x = ⨆ ( ↓ x ∩ K( L )x=⨆(↓x∩K(L)x = \bigsqcup ({\downarrow}...