Określanie, co można osiągnąć przez permutację elementów grupy nieprzemiennej

Ustalić skończoną grupę . Interesuje mnie następujący problem decyzyjny: dane wejściowe to niektóre elementy G z częściowym porządkiem na nich, a pytanie brzmi, czy istnieje permutacja elementów, która spełnia porządek i jest taka, że ​​skład elementów w tym porządek daje neutralny element grupy e .$G$$G$$e$

Formalnie problem testu $G$ jest następujący: grupa jest naprawiona:$G$

• Wejście: skończoną częściowo uporządkowanym o funkcji znakowania ľ od P do G .$(P, <)$$\mu$$P$$G$
• Wyjście: czy istnieje liniowe rozszerzenie (tj. Całkowity porządek ( P , < ′ ) taki, że dla wszystkich x , y ∈ P , x < y implikuje x < ′ y ), tak że zapis elementów P zgodnie z całkowitym rzędem < ′ jako x 1 , … , x n , mamy μ ( x 1 ) ⋅ ⋯ ⋅ μ $P$$(P, <')$$x, y \in P$$x < y$$x <' y$$P$$<'$$x_1, \ldots, x_n$ .$\mu(x_1) \cdot \cdots \cdot \mu(x_n) = e$

Dla każdej grupy , w G Problem -test jest wyraźnie w NP. Moje pytanie brzmi: czy istnieje grupa G , w której problem z testem G jest trudny do NP?$G$$G$$G$$G$

Kilka uwag na temat równoważnych stwierdzeń problemów:

• Język posetów i rozszerzeń liniowych może być równoważnie zastąpiony przez język DAG i porządków topologicznych. To znaczy, jeśli wolisz, możesz myśleć o danych wejściowych jako DAG z wierzchołkami oznaczonymi elementami grupy, a jako danych wyjściowych jako o pytaniu, czy jakiś topologiczny rodzaj danych wejściowych DAG osiąga .$e$
• Można zamiast rozważyć trudniejszy problem, gdzie otrzymują poset i g ∈ G , i zapytać, czy g (zamiast e ) może być zrealizowane. W rzeczywistości silniejszy problem sprowadza się do powyższego: możemy zapytać, czy e może być zrealizowane przez ( P ' , < ) , gdzie P ' oznacza P, ale z elementem oznaczonym g - 1, który jest mniejszy niż wszystkie inne. Stąd naturalny wybór e w powyższej definicji.$(P, <)$$g \in G$$g$$e$$e$$(P', <)$$P'$$P$$g^{-1}$$e$

Teraz o moich próbach rozwiązania problemu:

• Oczywiście, jeśli grupa jest przemienna, problem z testem G jest wyraźnie w czasie PTIME, ponieważ wszystkie rozszerzenia liniowe osiągają ten sam element grupy, więc możemy po prostu wybrać dowolny z nich według sortowania topologicznego i sprawdzić, czy jest on e, czy nie. Więc ciekawy przypadek nie jest przemienne G . Mówiąc bardziej ogólnie, jeśli G ma homomorfizm do jakiejś nietrywialnej grupy przemiennej (np. Podpis , dla permutacji), koniecznym, ale niewystarczającym warunkiem jest przyjrzenie się problemowi przez homomorfizm i sprawdzenie go w PTIME na obrazie przemiennym . Nie widzę, czy można to uogólnić na schemat rozkładu dla wszystkich grup skończonych.$G$$G$$e$$G$$G$
• Jeśli relacja kolejności jest pusta (tzn. Otrzymujemy zbiór elementów w i możemy użyć dowolnej permutacji), problem można rozwiązać za pomocą programowania dynamicznego, gdzie stany są liczbą wystąpień każdego elementu w G, które są nadal nieużywany (pamiętaj, że G jest stały, więc liczba stanów jest wówczas wielomianowa na wejściu).$G$$G$$G$
• Dla danych wejściowych, które są zestawami o stałej szerokości, możemy użyć algorytmu dynamicznego po rozkładzie łańcucha. Tak więc, jeśli twardość się utrzymuje, musi to być użycie zestawów wejściowych, które są dowolnie szerokie. Zauważ, że w przypadku szerokich zestawów liczba możliwych „stanów” w podejściu programowania dynamicznego byłaby liczbą ustawień zestawu, który ogólnie jest wykładniczy, a nie wielomianowy, więc to podejście nie działa bezpośrednio.
• Ten sam problem można badać raczej w przypadku monoidów niż grup, ale w przypadku monoidów już wiem, że jest trudny, dzięki dość skomplikowanemu argumentowi, który obejmuje przejście monoidu automatu i sprowadza się do wariantu poprzedniego pytania CStheory . Pełny dowód tego znajduje się w tym przedruku , załącznikach D.1.3 i D.1.4, chociaż terminologia jest bardzo różna. Dlatego gdy testowanie to PTIME, musi on wykorzystywać odwracalność elementów grupy.$G$
• $e$

$G$$G$$G$$G$$\Sigma$$A$$\Sigma$$A$$\Sigma$$A$

$G$$G$

dowód

$f(x) = -x$$g_a(x) = x + a$

$G$$f$$g_a$

$G$$\{f \circ g_a | a \in \mathbb{Z} \} \cup \{g_a | a \in \mathbb{Z} \}$

$G$

$a_1, a_2, ..., a_n$

$P$$n+2$$f$$n$$g_{a_i}$$i = 1,..., n$

$g_p \circ g_q = g_{p+q}$$f \circ g_p \circ f = g_{-p}$$P$$g_{\sum_{i \not\in I}a_i - \sum_{i \in I}a_i}$$I$$g_{a_i}$$f$$g_0$$P$$\sum_{i \not\in I}a_i - \sum_{i \in I}a_i = 0$$\sum_{i \not\in I}a_i = \sum_{i \in I}a_i$

$G$$I$$\sum_{i \not\in I}a_i = \sum_{i \in I}a_i$

$G$$G$

Z moim współautorem właśnie opublikowaliśmy przedruk, który bada ten problem bardziej ogólnie dla zwykłych języków. W przypadku grup skończonych twierdzimy, że problem jest możliwy do rozwiązania (w NL) w przypadku, gdy częściowa kolejność elementów składa się z połączenia łańcuchów: patrz Twierdzenie 6.2. Możemy przypuszczać, że problem ogólnych DAG dotyczy również NL, i istnieje nadzieja na rozszerzenie techniki na to ustawienie, ale brakuje nam do tego składnika związanego z tym pytaniem - szczegółowe informacje znajdują się w przedruku, sekcja 6, akapit „Ograniczenia” na końcu, drugie ograniczenie.