Complexité des problèmes liés à la permutation

Étant donné un groupe de permutations sur [ n ] = { 1 , ⋯ , n } , et deux vecteurs u , v ∈ Γ n où Γ est un alphabet fini qui n'est pas tout à fait pertinent ici, la question est de savoir s'il existe des π ∈ G tel que π ( u ) = v où π ( u ) signifie appliquer la permutation π sur u de manière attendue.$G$$[n]=\{1, \cdots, n\}$$u,v\in \Gamma^n$$\Gamma$$\pi\in G$$\pi(u)=v$$\pi(u)$$\pi$$u$

Supposons en outre que soit donné, en entrée, par un ensemble fini S de générateurs. Quelle est la complexité du problème? En particulier, est-ce en NP?$G$$S$

Soit où S n est le groupe de permutation sur n éléments. Vérifier si g ∈ ⟨ g 1 , ... , g k ⟩ peut être fait dans NC ⊆ P par [1]. Soit u , v ∈ Γ n , puis devinez simplement g ∈ S n , testez en temps polynomial si g ∈ $g_1, \ldots, g_k, g \in S_n$$S_n$$n$$g \in \langle g_1, \ldots, g_k \rangle$$\text{NC} \subseteq \text{P}$$u, v \in \Gamma^n$$g \in S_n$$g \in G$et si . Cela donne une limite supérieure NP .$g(u) = v$$\text{NP}$

Pour compléter cette réponse:

Il a été démontré que l'appartenance à un groupe appartenait à (Furst et al. 1980), puis à NC 3 pour les groupes abéliens (McKenzie & Cook 1987; Mulmuley 1987), à NC pour les groupes nilpotents (Luks & McKenzie 1988), groupes résolubles (Luks & McKenzie 1988), des groupes avec des facteurs de composition non abéliens bornés (Luks 1986), et enfin tous les groupes (Babai et al. 1987). Une classification similaire de la complexité de l'appartenance aux monoïdes apériodiques est due à (Beaudry 1988; Beaudry et al. 1992; Kozen 1977), qui montrent que l'appartenance à toute variété monoïde apériodique fixe est soit en AC 0 , en P , en NP ou en $\text{P}$$\text{NC}^3$$\text{NC}$$\text{AC}^0$$\text{P}$$\text{NP}$$\text{PSPACE}$ (et complet pour cette classe à quelques exceptions près).

[1] L. Babai, EM Luks et A. Seress. Groupes de permutation en NC. Proc. symposium annuel de l'ACM sur la théorie de l'informatique, pp. 409-420, 1987.$19^\text{th}$

Votre problème est connu sous le nom ( -) chaîne G -isomorphisme. Il est dans une classe assez étroite de problèmes autour Graphique Isomorphisme: il est au moins aussi dur que GI, et est en N P de la c o A M .$\Gamma$$G$$\mathsf{NP} \cap \mathsf{coAM}$

Réduction de GI: soit , et soitG≤SNl'action induite deSnsur les paires.$N = \binom{n}{2}$$G \leq S_N$$S_n$

protocole M : Arthur choisit au hasard un élément de G (je ne suis pas sûr que cela puisse être fait de manière uniforme, mais je pense que les algorithmes connus se rapprochent suffisamment de l'uniformité pour ce résultat) et l'appliquent à la fois à u et à v . Avec une probabilité 1/2, il échange u et v , puis les présente à Merlin et demande lequel était lequel.$\mathsf{coAM}$$G$$u$$v$$u$$v$

Malgré mes commentaires, j'ajouterai également une réponse.

Dans le cas où les deux vectros donnés sont connus pour être une permutation l'un de l'autre (et la permutation est connue / supposée être dans le groupe donné ). Alors la permutation qui transforme v → u peut être trouvée en temps linéaire comme telle:$G$$v \to u$

1. Alignez les 2 vecteurs l'un sous l'autre

2. La permutation est trouvée en partant du 1er élément de qui se transforme en 1er élément de $v$$u$

3. Obtenez la position de l'élément dans l'étape précédente (de en v ) et répétez l'étape (2), puis c'est le 2e élément de la permutation et ainsi de suite, jusqu'à ce que tous les éléments soient traversés.$u$$v$

Si vous ne savez pas si les deux vecteurs sont positivement la permutation l'un de l'autre (ou pour des cas plus généraux où il peut y avoir plusieurs transformations, comme par exemple un jeu de sudoku), vérifiez le Another Solution Problem qui est en général NP-difficile. Cela nécessite d'utiliser certaines transformations de symétrie (par exemple permutations) qui satisfont aux contraintes d'un problème donné pour générer une autre solution du problème étant donné une solution initiale.

De plus, cela fait partie des problèmes connus sous le nom de problèmes inverses (à la Jaynes)