Teoretyczne informatyka

1

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 …

12 cc.complexity-theory polynomial-hierarchy

4

Rozpocznij naukę złożoności dowodu

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ś podstawy?

12 cc.complexity-theory lo.logic proof-complexity

1

Minimalizowanie resztkowych automatów skończonych

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 DFA. Jednakże, podczas gdy minimalne stany DFA …

12 cc.complexity-theory ds.algorithms automata-theory lg.learning minimization

3

Podgraf zawierający wszystkie węzły i krawędzie, które są częścią prostych ścieżek st o ograniczonej długości na niekierowanym wykresie

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 zawiera dowolny wierzchołek i dowolną krawędź w solGG …

12 ds.algorithms graph-algorithms shortest-path

5

Motywacja do oszacowania objętości

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ą przykłady całek, które ludzie chcą obliczać w praktyce, które są bardzo trudne do …

12 cg.comp-geom na.numerical-analysis markov-chains

2

Algorytm konwersji bardzo dużego NFA na DFA

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 dość powolny i bardzo zajmuje pamięć. Zdaję sobie sprawę …

12 dfa

1

Wydajny algorytm dla istnienia permutacji z sekwencją różnic?

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 liczbami w permutacji π . Innymi słowy, …

12 cc.complexity-theory co.combinatorics np-hardness permutations

2

Czy hierarchia upada?

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 hierarchia AC0dACd0\mathsf{AC^0_d} się nie zwija?

12 cc.complexity-theory reference-request complexity-classes circuit-complexity bounded-depth

4

znajdowanie najmniejszych k elementów w tablicy w O (k)

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 problemie z przyjaciółmi, ale nikt …

12 sorting

3

Czy istnieje ograniczenie do gier typu „drzwi i płyta dociskowa”, które nie eksplodują długości rozwiązania?

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 z maszyny NPSPACE do takiej gry, …

12 reductions nondeterminism pspace

1

Czy istnieje książka / artykuł przeglądowy przedstawiający hierarchie klas językowych, właściwości zamknięcia itp

Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce lub opracowaniu, które opisuje właściwości tych języków. Większość tego, na …

12 reference-request co.combinatorics fl.formal-languages automata-theory research-practice

1

Jaki jest związek między i ?

Jaki jest związek między i ? Innymi słowy, czy problemy, które dopuszczają wyszukiwanie lokalne w czasie wielomianowym, są przybliżone? Czy problemy z optymalizacją w przybliżeniu sugerują ogólnie lokalny algorytm wyszukiwania?P L SPLS\mathsf{PLS}A P XAPX\mathsf{APX}

12 cc.complexity-theory approximation-algorithms

1

Płynna analiza algorytmów aproksymacyjnych

Wygładzona analiza była stosowana wiele razy, aby zrozumieć czas działania dokładnych algorytmów dla wielu problemów, takich jak programowanie liniowe i k-średnich. Istnieją dość ogólne wyniki w tej dziedzinie, na przykład Heiko Röglin i Berthold Vöcking, Analiza wygładzania programowania liczb całkowitych , 2005. Niektóre z tych ogólnych wyników wydają się polegać …

12 cc.complexity-theory approximation-algorithms approximation-hardness smoothed-analysis

2

Złożoność częściowych gier informacyjnych o skończonym stanie

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 ?ϵϵ\epsilon W szczególności nie mogę wymyślić żadnego algorytmu do tego. Pozostała …

12 cc.complexity-theory gt.game-theory

1

Jak trudna jest binarna łamigłówka Sudoku?

Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i 1 . Zasady są następujące.000111 Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek. Każdy wiersz i każda kolumna jest unikalny. Żaden wiersz ani kolumna nie zawiera kolejnych potrójnych …

12 cc.complexity-theory np-hardness puzzles