Teoretyczne informatyka

3

Najpierw zapytany na stronie math.SE bez odpowiedzi Załóżmy, że mam wykres płaski z osadzeniem planarnym, jak znaleźć rozkład drzewa? Jaki jest optymalny rozkład drzewa siatki kwadratowej -by- ? Nie do końca pewny, jak zdefiniować „optymalny”, ale powinien odróżniać rozkład z jedną dużą torbą od rozkładu z wieloma dużymi torbami.dddddd

9 ds.algorithms graph-theory graph-algorithms treewidth integer-lattice

1

Czy problem tworzenia kopii zapasowej NP jest kompletny?

Czy następujący problem decyzyjny NP-zupełny: Niech będzie nieukierowanym wykresem i dwiema liczbami całkowitymi. Czy można wybrać dla każdego wierzchołka dokładnie różnych sąsiadów, tak że żaden węzeł nie zostanie wybrany więcej niż razy.GGGb≤cb≤cb \le cGGGbbbccc Przypadek można rozwiązać dla dowolnego czasie wielomianowym, stosując maksymalne dopasowanie.b=1b=1b = 1ccc Motywacja: każdy węzeł chce …

9 cc.complexity-theory np-hardness graph-algorithms

2

Wymuszanie uczciwego zachowania

Jak zmusić drużynę do uczciwości (przestrzegać zasad protokołu)? Widziałem pewne mechanizmy, takie jak zobowiązania, dowody itp., Ale wydaje się, że nie rozwiązują one całego problemu. Wydaje mi się, że struktura projektu protokołu i takie mechanizmy muszą działać. Czy ktoś ma dobrą klasyfikację tego. Edytuj Podczas projektowania bezpiecznych protokołów, jeśli zmusisz …

9 cr.crypto-security gt.game-theory

2

Jaka jest optymalna struktura danych dla drzewa map.

Szukam struktury danych, która jest w zasadzie drzewem map, w których mapa w każdym węźle zawiera nowe elementy, a także elementy w mapie jego węzła nadrzędnego. Przez mapę rozumiem tutaj mapę programowania z kluczami i wartościami, taką jak mapa w STL lub dict w python. Na przykład może istnieć węzeł …

9 ds.data-structures tree hash-function

1

Jaka jest złożoność tej gry o podziale nieruchomości?

Alice i Bob dzielą majątek zmarłego wuja Charliego (zbiór skończony XXXelementów dyskretnych) zgodnie z jego życzeniem. Najpierw A wybiera przedmiot, potem B, potem A i tak dalej. Alice i Bob mają dodatkowe funkcje narzędziowe uZA,ubuA,uBu_A, u_B, więc jeśli Alice skończy z zestawem Y⊆ XY⊆XY \subseteq X, jej użyteczność to ∑y∈ …

9 gt.game-theory

2

Złożoność czasowa algorytmu Held-Karp dla TSP

Kiedy przejrzałem „ Dynamiczne podejście programistyczne do problemów z sekwencjonowaniem ” autorstwa Michaela Helda i Richarda M. Karpa, wpadłem na następujące pytanie: dlaczego złożoność ich algorytmu dla TSP jest (s. 199), mam na myśli skąd biorą współczynnik ? Jeśli dobrze zrozumiałem, k-1 oznacza liczbę dodatków dla każdego podzbioru miast. To …

9 ds.algorithms tsp exp-time-algorithms

1

Złożoność znalezienia składowej składowej macierzy * symetrycznej *

To jest wyspecjalizowana wersja poprzedniego pytania: Złożoność znalezienia składowej macierzy . W przypadku macierzy symetrycznych NxN wiadomo, że czas O (N ^ 3) wystarcza do obliczenia rozkładu własnego. Pytanie brzmi: czy możemy osiągnąć sub-sześcienną złożoność? Dzięki.

9 ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis

1

Czy istnieje związek między teorią złożoności obliczeniowej a teorią systemów złożonych?

Teoria złożoności obliczeniowej klasyfikuje problemy według ich nieodłącznej trudności. Teoria złożonych systemów dotyczy systemów, które wykazują zachowania, które oczywiście nie wynikają z właściwości poszczególnych części systemu. Przykłady obejmują systemy chaotyczne, złożone systemy adaptacyjne lub systemy nieliniowe. Czy istnieje formalny pomost między tymi polami? Co do tego, co jest warte, koncepcja …

9 cc.complexity-theory soft-question big-picture

2

Testowanie właściwości dla niezależnych zestawów

Załóżmy, że otrzymaliśmy wykres GGG i parametry k,ϵk,ϵk,\epsilon. Czy istnieją zakresy wartości dlakkk (czy jest to wykonalne dla wszystkich kkk), dla których można sprawdzić, czy GGG jest ϵϵ\epsilon-dużo posiadania niezależnego zestawu przynajmniej wielkości kkk w samą porę O(n+poly(1/ϵ))O(n+poly(1/ϵ))O(n + \text{poly}(1/\epsilon)) ? Jeśli użyjemy zwykłego pojęcia ϵϵ\epsilon-dale (tj. co najwyżej ϵn2ϵn2\epsilon …

9 ds.algorithms graph-theory reference-request property-testing

8

Czy jest jakiś inny algorytm, którego najgorszy czas działania jest wykładniczy, podczas gdy działa on bardzo dobrze w praktyce, inny niż algorytm Simplex?

Na ogół algorytm nazywamy „dobrym algorytmem”, jeśli jego czas działania jest w najgorszym przypadku wielomianowy. Ale w niektórych przypadkach (na przykład algorytm Simplex), chociaż najgorszy przypadek algorytmu ma charakter wykładniczy, może on działać bardzo dobrze w praktyce. Czy są jakieś (deterministyczne) przykłady tej sytuacji inne niż algorytm Simplex?

9 ds.algorithms

1

Czy istnieje jakiś szczególny problem z PSPACE, który ma algorytm FPTAS?

Dobrze wiadomo, że NP-Complete Problem o nazwie Subset Sum ma FPTAS. Zastanawiałem się, czy istnieje problem z PSPACE Complete, który ma także FPTAS? Z góry dziękuję.

9 ds.algorithms space-bounded big-picture

2

Złożoność Hamiltonianów podlegających prawu obszarowemu

Ostatnio pomyślałem o „zaimportowaniu” niektórych pytań związanych z fizyką do kwantowego CS: Pojęcie zjawiska prawa obszarowego w układach hamiltonowskich zwykle oznacza lokalnego hamiltonianu na pewnej sieci, którego stan naziemny wykazuje właściwość, w której uwikłanie dowolnego zamkniętego regionu jest proporcjonalne do powierzchni regionu, a nie jego objętości (jak by to było …

9 quantum-computing big-picture

2

Nierówność typu Chernoffa dla zmiennej losowej z 3 wynikami

Załóżmy, że mamy zmienną losową, która przyjmuje wartości nienumeryczne a, b, c i chce określić ilościowo, w jaki sposób rozkład empiryczny nnnpróbki tej zmiennej odbiegają od rozkładu rzeczywistego. W tym przypadku obowiązuje następująca nierówność (z Cover & Thomas ). Twierdzenie 12.4.1 (twierdzenie Sanowa): Niech X1,X2,…,XnX1,X2,…,XnX_1, X_2, \ldots, X_n bądź tam …

9 pr.probability chernoff-bound

5

Przykłady, w których znaczenie ma rozmiar alfabetu ( ) użyty do kodowania

Niech będzie alfabetem, czyli niepustym zbiorem skończonym. Łańcuch to dowolna skończona sekwencja elementów (znaków) z . Na przykład to alfabet binarny, a to ciąg znaków dla tego alfabetu.ΣΣ\SigmaΣΣ\Sigma{ 0 , 1 }{0,1} \{0, 1\}011001100110 Zazwyczaj, dopóki zawiera więcej niż 1 element, dokładna liczba elementów w nie ma znaczenia: w najlepszym …

9 big-list encoding examples

1

Rzeczywista złożoność bitowa mnożenia macierzy wynosi

Mnożenie macierzy przy użyciu techniki regularnej (iloczyn wewnętrzny rzędów i kolumn) O (n3))O(n3))O(n^{3}) mnożenia i O (n3))O(n3))O(n^{3})wzbogacenie. Jednak przy założeniu, że wpisy o jednakowej wielkości (liczba bitów w każdym wpisie obu macierzy jest mnożona) o wielkościmmm bitów, operacja dodawania faktycznie się dzieje O (n3)n m ) = O (n4m )O(n3)nm)=O(n4m)O(n^{3}nm) …

9 cc.complexity-theory algebraic-complexity