Je suis intéressé par le problème suivant. On nous donne en entrée une "permutation cible" , ainsi qu'une liste ordonnée d'indices . Ensuite, en commençant par la liste (c'est-à-dire la permutation d'identité), à chaque pas de temps nous l' dans avec le élément, avec probabilité indépendante . Soit...
En gros, l'appariement des modèles de permutation traite des problèmes du type suivant: Étant donné les permutations dans et dans , avec , contient-il une sous- séquence de longueur dont les éléments sont ordonnés selon ?ππ\piSnSnS_nσσ\sigmaSmSmS_mm≤nm≤nm\leq nππ\pi ττ\taummmσσ\sigma Par exemple,...
Soit un polynôme symétrique , c'est-à-dire un polynôme tel que pour tous les et toutes les permutations . Pour plus de commodité, nous pouvons supposer que est un champ fini, pour éviter de résoudre les problèmes avec le modèle de calcul. f ( x ) = f ( σ ( x ) ) x ∈ K n σ ∈ S n KF: Kn→...
Voici l'arrière-plan de cette question. Des amis et moi jouions à un jeu où tout le monde devait offrir un cadeau à une autre personne. Afin de déterminer qui doit offrir un cadeau à qui, nous décidons de tirer au sort. Mais le problème est que quelqu'un pourrait finir par se donner des cadeaux, ce...
Étant donné des générateurs puissants pour un groupe agissant sur des chaînes de bits de longueur et un élément , combien est-il difficile de calculer l'élément lexicographiquement minimal de , le orbite de en ?( G ≤ Sn, ∗ )(g≤Sn,∗)(G \leq S_n, *)nnns ∈ { 0 , 1 }ns∈{0,1}ns \in \{0, 1\}^nG ....