Zainspirowany tym pytaniem, a w szczególności ostatnim akapitem odpowiedzi Or, mam następujące pytanie: Czy znasz jakieś zastosowania teorii reprezentacji grupy symetrycznej w TCS? Grupa symetryczna SnSnS_n jest grupą wszystkich permutacji {1,…,n}{1,…,n}\{1, \ldots, n\} o składzie operacji...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Biorąc pod uwagę grupę symetrii i dwie podgrupy i , czy ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset O ile mi wiadomo, problem ten znany jest jako problem przecięcia cosetów. Zastanawiam się, jaka jest złożoność? W szczególności, czy wiadomo, że ten problem...
Nie mam wiedzy w zakresie teorii złożoności z udziałem grup, więc przepraszam, jeśli jest to dobrze znany wynik. Pytanie 1. Niech będzie prostym nieukierowanym grafem rzędu . Jaka jest złożoność obliczeniowa (w kategoriach ) ustalania, czy jest przechodnie dla
Od dawna wiadomo, że przy dowolnym stopniu reuringu istnieje dobrze przedstawiona grupa, której problem słowny jest w tym stopniu. Moje pytanie brzmi, czy to samo dotyczy dowolnych stopni Turinga w czasie wielomianowym . W szczególności, biorąc pod uwagę rozstrzygalny zestaw, , czy istnieje...
Czy istnieje , język NP lub P-zupełny, który ma pewną rodzinę grup symetrii G n (lub groupoid , ale wtedy pytania algorytmiczne stają się bardziej otwarte) działając (w czasie wielomianowym) na zbiorach L n = { l ∈ L ∣ | l | = n } tak, że jest kilka orbit, tj. taki, że | L n / G n | < n c dla...
Eliminacja Gaussa sprawia, że wyznacznik macierzy obliczany jest w czasie wielomianowym. Zmniejszenie złożoności obliczania wyznacznika, które w przeciwnym razie jest sumą terminów wykładniczych, wynika z obecności alternatywnych znaków ujemnych (których brak sprawia, że obliczenia są trwałe,...
Rozważ następujący problem testowania członkostwa w podgrupie abelian . Wejścia: Skończona grupa abelowa G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} o dowolnie dużych didid_i . Wytwarzające osadzone {h1,…,hn}{h1,…,hn}\lbrace...
Jestem głównym matematykiem zainteresowanym TCS. Chcę samemu przestudiować algorytmy i ich złożoność w celu rozwiązania grupowych problemów teoretycznych, takich jak znajdowanie porządku elementów, wyliczanie zbioru, wyszukiwanie generatora, testowanie, czy dany podzbiór generuje grupę. Jaką...
Mam trudności ze zrozumieniem ostatnich kroków algorytmu AHSP. Niech GGG była grupą abelowa i fff jest funkcją, która ukrywa podgrupy HHH . Niech G∗G∗G^* reprezentują podwójną grupę GGG . Oto kroki algorytmu Najpierw przygotuj państwo, I=1|G|∑g∈G|g⟩|0⟩I=1|G|∑g∈G|g⟩|0⟩\qquad \displaystyle...
Mówi się, że dwie grupy (G,⋅)(G,⋅)(G,\cdot) i (H,×)(H,×)(H, \times) są izomorficzne, jeśli istnieje homomorfizm od GGG do HHH który jest bijectywny. Problem z izomorfizmem grupowym jest następujący: biorąc pod uwagę dwie grupy, sprawdź, czy są izomorficzne, czy nie. Istnieją różne sposoby...
Interesują mnie algorytmy dla grup skończonych zaimplementowane w pakiecie GAP. Wydaje się, że wszystkie znane algorytmy w tej dziedzinie dotyczą grup permutacji / grup matryc; dwa podstawowe to Schreier-Sims [1970] i Butler [1979], patrz np. „Algorytmy dla grup permutacyjnych” Alice Niemeyer jako...
Algorytmy czasu wielomianowego znane są ze znajdowania generujących zestawów grup permutacji, co jest interesujące, ponieważ możemy następnie przedstawić te grupy zwięźle, nie rezygnując z algorytmów czasu wielomianowego do odpowiedzi na wiele interesujących pytań związanych z tymi...
Babai i Seress okazało się , że ze względu podgrupa i agregatem S z G , każdy permutacyjny G może być zapisana jako produkt generatorów i ich odwrotności długości e ( 1 + O ( 1 ) ) √G≤SnG≤SnG \leq S_nSSSGGGGGG . Ta granica jest optymalna, ponieważSnma element rzędue(1+o(1))...
Biorąc pod uwagę dwie permutacje i nad elementami (tj. ), jaka jest złożoność obliczania kolejności podgrupy generowanej przez ? Albo po prostu decydując, czy podgrupa jest rzędu(tj. wszystkie )?h n S n g , h n ! S nsolgghhhnnnS.nSnS_nsol, hg,hg,hn
Niech będzie skończoną grupą abelową, i niech będzie polytopem w zdefiniowanym jako punkty spełniające następujące nierówności:P R Γ xΓΓ\GammaP.PPRΓRΓ\mathbb{R}^\Gammaxxx ∑sol∈ G.xsol≤ | G |xsol≥ 0∀ G ≤ Γ∀ g∈ Γ∑g∈Gxg≤|G|∀G≤Γxg≥0∀g∈Γ\begin{array}{cl} \sum_{g\in G} x_g \le |G| & \forall G \le \Gamma...
Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o .GGGHHHrrrnnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla...
Biorąc pod uwagę silne generatory dla grupy działającej na ciągach bitów o długości i elemencie , jak trudno jest obliczyć leksykograficznie minimalny element , orbity w ?( G ≤S.n, ∗ )(sol≤S.n,∗)(G \leq S_n, *)nnns ∈ { 0 , 1}ns∈{0,1}ns \in \{0, 1\}^nG .
Czy istnieje znana rodzina działań grupowych z wyznaczonym elementem w zestawie, na którym działa się, gdzie wiadomo, jak skutecznie \: próbkuj (zasadniczo jednolicie) z grup, oblicz operacje odwrotne, \: oblicz operacje grupowe i oblicz działania grupowe i nie ma znanego wydajnego algorytmu...
Biorąc pod uwagę funkcję boolowską , mamy grupę automorfizmów .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Czy są jakieś znane granice dla ? Czy jest coś znanego dla ilości postaci dla jakiejś grupy...