Décider si un circuit NC calcule ou non une permutation

Je voudrais poser une question sur un cas particulier de la question « Décider si un circuit NC ⁰ donné calcule une permutation » par QiCheng qui est resté sans réponse.

Un circuit booléen est appelé circuit NC ⁰ _k si chaque porte de sortie dépend syntaxiquement d'au plus k portes d'entrée. (Nous disons qu'une porte de sortie g dépend syntaxiquement d' une porte d'entrée g 'quand il y a un chemin dirigé de g ' à g dans le circuit vu comme un graphe acyclique dirigé.)

Dans la question susmentionnée, QiCheng a posé des questions sur la complexité du problème suivant, où k est une constante:

Instance : un circuit NC ⁰ _k avec entrée à n bits et sortie à n bits.
Question : Le circuit donné calcule-t-il une permutation sur {0, 1} ⁿ ? En d'autres termes, la fonction calculée par le circuit est-elle une bijection de {0, 1} ⁿ à {0, 1} ⁿ ?

Comme Kaveh l'a commenté sur cette question, il est facile de voir que le problème est en coNP. Dans une réponse, j'ai montré que le problème est coNP-complet pour k = 5 et qu'il est en P pour k = 2.

Question . Quelle est la complexité de k = 3?

Précision le 29 mai 2013 : «Une permutation sur {0, 1} ⁿ » signifie une cartographie bijective de {0, 1} ⁿ à elle-même. En d'autres termes, le problème demande si chaque chaîne à n bits est la sortie du circuit donné pour une chaîne d'entrée à n bits.

Ce problème avec est coNP-dur (et donc coNP-complet).$k=3$

Pour le prouver, je vais réduire de 3-SAT au complément de ce problème (pour un circuit donné , le circuit -t-il une fonction non bijective).$NC_3^0$

D'abord une définition préliminaire qui sera utile:

Nous définissons un graphe étiqueté comme un graphe orienté, dont certaines arêtes sont étiquetées avec des littéraux, avec la propriété que chaque sommet a soit une arête entrante non étiquetée, soit une arête entrante étiquetée, soit deux arêtes entrantes non étiquetées.

La réduction

Supposons que nous ayons une formule 3-SAT composée de clauses, chacune contenant trois littéraux. La première étape consiste à construire un graphe étiqueté partir de . Ce graphique étiqueté contient une copie du gadget suivant (désolé pour le terrible diagramme) pour chaque clause dans . Les trois bords étiquetés L1, L2 et L3 sont plutôt étiquetés avec les littéraux de la clause.m G ϕ $\phi$$m$$G$$\phi$$\phi$

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

Les gadgets (un pour chaque clause) sont tous disposés en un grand cycle avec le bas d'un gadget lié au haut du suivant.

Notez que cet arrangement de gadgets forme en fait un graphique étiqueté (chaque sommet a un indegree 1 ou 2 avec seulement des arêtes menant à des sommets d'indegree 1 étiquetés).

A partir de la formule et du graphe étiqueté (qui a été construit à partir de ), nous construisons ensuite un circuit (ceci conclura la réduction). Le nombre d'entrées et de sorties de ce circuit est , où est le nombre de variables dans et est le nombre de sommets dans . Une entrée et une sortie est affectée à chaque variable et à chaque sommet dans . Si est une variable dans alors nous ferons référence aux bits d'entrée et de sortie associés à commeG ϕ N C 0 3 n + v n ϕ v G ϕ G x ϕ x x i n x o u t l l = x l i n = x i n l l = ¬ x l i n = ¬ x i n v G v v i n v o u $\phi$$G$$\phi$$NC_3^0$$n+v$$n$$\phi$$v$$G$$\phi$$G$$x$$\phi$$x$$x_{in}$ et . De plus, si est un littéral avec alors nous définissons et si est un littéral avec alors nous définissons . Enfin, si est un sommet dans alors nous ferons référence aux bits d'entrée et de sortie associés à comme et .$x_{out}$$l$$l = x$$l_{in} = x_{in}$$l$$l = \neg x$$l_{in} = \neg x_{in}$$v$$G$$v$$v_{in}$$v_{out}$

Il existe quatre types de bits de sortie:

1) Pour chaque variable in , . Notez que cette sortie dépend d'un seul bit d'entrée.ϕ x o u t = x i $x$$\phi$$x_{out} = x_{in}$

2) Pour chaque sommet dans le graphe étiqueté avec exactement un bord entrant tel que le bord ne soit pas étiqueté, . Notez que cette sortie ne dépend que de deux bits d'entrée.( u , v ) v o u t = v i n ⊕ u i $v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$

3) Pour chaque sommet dans le graphe étiqueté avec exactement une arête entrante telle que l'arête est étiquetée , . Notez que cette sortie ne dépend que de trois bits d'entrée puisque ne dépend que de pour la variable utilisée dans le littéral .( u , v ) l v o u t = v i n ⊕ ( u i n ∧ l i n ) l i n x i n x $v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l_{in})$$l_{in}$$x_{in}$$x$$l$

4) Pour chaque sommet dans le graphe étiqueté avec exactement deux arêtes entrantes et , . Notez que cette sortie ne dépend que de trois bits d'entrée.( u , v ) ( w , v ) v o u t = v i n ⊕ ( u i n ∨ w i n$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

Comme dans tous les cas, la sortie ne dépend que de trois entrées, le circuit que nous construisons est en comme souhaité.$NC_3^0$

Cas de preuve d'exactitude 1: est satisfiable$\phi$

Supposons qu'il existe une affectation satisfaisante pour . Construisez ensuite les deux ensembles de valeurs suivants pour les entrées.$\phi$

1) Les entrées associées aux variables de reçoivent les valeurs de l'affectation satisfaisante. Toutes les entrées associées aux sommets de reçoivent la valeur 0.$\phi$$G$

2) Les entrées associées aux variables de reçoivent les valeurs de l'affectation satisfaisante. Considérez les sommets dans un gadget clause . Si la valeur d'une étiquette est 0 (sous l'affectation satisfaisante), l'entrée associée au sommet au point d'extrémité cible de l'arête étiquetée avec cette étiquette reçoit une valeur de 0. Si L1 et L2 ont la valeur 0, alors la seconde -Le sommet du gadget (comme indiqué ci-dessus) reçoit également une valeur de 0. Tous les autres sommets reçoivent une valeur de 1.$\phi$$G$

Nous souhaitons montrer que ces deux ensembles d'entrées produisent des sorties identiques et donc que le circuit ne code pas une permutation.$NC_3^0$

Considérez les quatre types de bits de sortie:

1) Pour chaque variable in , . Comme est le même pour les deux ensembles d'entrées, les sorties de ce formulaire seront toujours les mêmes pour les deux ensembles d'entrées.ϕ x o u t = x i n x i $x$$\phi$$x_{out} = x_{in}$$x_{in}$

2) Pour chaque sommet dans le graphe étiqueté avec exactement un bord entrant tel que le bord ne soit pas étiqueté, . En examinant le gadget dont les copies constituent , nous voyons que toutes ces arêtes ne sont constituées que de paires de sommets dont les valeurs d'entrée sont toujours 1s sous le deuxième ensemble d'entrées. Ainsi sous le premier ensemble d'entrées et sous le deuxième ensemble d'entrées. Ainsi, les sorties de cette forme seront toujours les mêmes (et en fait zéro) entre les deux ensembles d'entrées.( u , v ) v o u t = v i n ⊕ u i n G v o u t = v i n ⊕ u i n = 0 ⊕ 0 = 0 v o u t = v i n ⊕ u i n = 1 ⊕ 1 = $v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$$G$$v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$$v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$

3) Pour chaque sommet dans le graphe étiqueté avec exactement une arête entrante telle que l'arête est étiquetée , . Si est faux sous l'affectation, alors est 0 sous les deux ensembles d'entrées; alors sous les deux ensembles d'entrées. Si est vrai sous l'affectation, est 0 sous le premier ensemble d'entrées et 1 sous le second; notez également que dans le gadget, les seuls bords étiquetés ont des sommets qui ont toujours( u , v ) l v o u t = v i n ⊕ ( u i n ∧ l ) l v i n v o u t = v i n ⊕ ( u i n ∧ l ) = v i n ⊕ ( u i n ∧ 0 ) = v i n = $v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l)$$l$$v_{in}$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$v i n ( u , v ) u u i n = 1 u i n = v i n l V o u t = v i n ⊕ ( u i n ∧ l ) = v i n ⊕ ( u i n ∧ 1 ) = v i n ⊕ u i n = $l$$v_{in}$$(u, v)$$u$$u_{in} = 1$ sous le deuxième ensemble d'entrées. En conséquence, nous voyons que sous les deux ensembles d'entrées, chaque fois que est vrai; alors . Ainsi, les sorties de cette forme seront toujours les mêmes (et en fait zéro) entre les deux ensembles d'entrées.$u_{in} = v_{in}$$l$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$

4) Pour chaque sommet dans le graphe étiqueté avec exactement deux arêtes entrantes et , . Il existe deux sommets de ce type dans chaque gadget. Le sommet supérieur et le deuxième sommet supérieur. Nous considérons ces deux cas séparément.( u , v ) ( w , v ) v o u t = v i n ⊕ ( u i n ∨ w i n$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

4a) Lorsque est le deuxième sommet du gadget, u et w sont les deux extrémités cibles des arêtes étiquetées L1 et L2. Dans le premier ensemble d'entrées, v o u t = v i n ⊕ ( u i n ∨ w i n ) = 0 ⊕ ( 0 ∨ 0 ) = 0 . Sous le deuxième ensemble d'entrées, u i n est 0 si L1 a la valeur 0 sous l'affectation satisfaisante (aka u i n$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$ ); de même, w i n est 0 si L2 a la valeur 0 sous l'affectation satisfaisante (alias w i n = L 2 ); et enfin, v i n est défini comme étant 0 si L1 et L2 ont la valeur 0 (alias v i n = L 1 ∨ L 2 ). Ainsi, sous le deuxième ensemble d'entrées, v o u t = v i n ⊕ ( u i n ∨ w i n ) = $u_{in} = L1$$w_{in}$$w_{in} = L2$$v_{in}$$v_{in} = L1 \lor L2$ . Ainsi, les sorties de cette forme seront toujours les mêmes (et en fait zéro) entre les deux ensembles d'entrées.$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$

4b) Lorsque est le sommet supérieur d'un gadget, u est le deuxième sommet supérieur et w est l'extrémité cible de l'arête étiquetée L3. Dans le premier ensemble d'entrées, v o u t = v i n ⊕ ( u i n ∨ w i n ) = 0 ⊕ ( 0 ∨ 0 ) = 0 . Sous le deuxième ensemble d'entrées, u i n est égal à 0 si L1 et L2 ont la valeur 0 (alias u i n = $v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$ ); w i n est 0 si L3 a la valeur 0 (alias w i n = L 3 ); et enfin v i n = 1 . Ainsi, sous le deuxième ensemble d'entrées, v o u t = v i n ⊕ ( u i n ∨ w i n ) = 1 ⊕ ( ( L 1 ∨ L 2 ) ∨ L 3 $u_{in} = L1 \lor L2$$w_{in}$$w_{in} = L3$$v_{in} = 1$ où l'égalité ( L 1 ∨ L 2 ∨ L 3 ) = 1 est définie par définition dans une affectation satisfaisante pour chaque clause. Ainsi, les sorties de cette forme seront toujours les mêmes (et en fait zéro) entre les deux ensembles d'entrées.$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$$(L1 \lor L2 \lor L3) = 1$

On voit bien que les sorties sont les mêmes pour deux ensembles d'entrées différents et donc que le circuit une fonction non bijective.$NC_3^0$

Cas de preuve d'exactitude 2: n'est pas satisfaisant$\phi$

Supposons maintenant qu'il n'existe aucune affectation satisfaisante pour . Supposons ensuite, par souci de contradiction, que deux ensembles d'entrées différents conduisent au circuit N C 0 3 ayant la même sortie.$\phi$$NC_3^0$

Il est clair que les deux entrées doivent avoir les mêmes valeurs pour pour chaque variable x dans ϕ . Ainsi, nous pouvons maintenant nous référer sans ambiguïté à la valeur de x .$x_{in}$$x$$\phi$$x$

Définissez comme étant l'ensemble des sommets v dans G de telle sorte que v i n soit différent dans les deux ensembles de valeurs d'entrée.$S$$v$$G$$v_{in}$

Nous prouverons les lemmes suivants ci-dessous:

$S$$S$

$S$$S$

$S$$G$$S$$S$

$(L1 \lor L2 \lor L3)$$(u, v)$$L$$v_{out} = v_{in} \oplus (u_{in} \land L)$$L = 0$$v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$$v_{in}$$v$$S$$S$

$S$$NC_3^0$

Il ne reste plus qu'à prouver les lemmes.

Pour ce faire, nous notons que pour chaque type de sommet en (indegree 1 avec étiquette, indegree 1 sans étiquette et indegree 2), si toutes les arêtes entrantes proviennent de sommets qui ne sont pas en alors le sommet en question n'est pas non plus en . En effet, dans les trois cas, où est une fonction des entrées associées aux variables et / ou aux sommets avec des arêtes à . Étant donné que tous ces sommets ne sont pas dans par hypothèse, la valeur de doit être la même sous les deux ensembles d'entrées. Par conséquent, est également le même sous les deux ensembles d'entrées. En d'autres termesS S v o u t = v i n ⊕ X X v S X v i n = v o u t ⊕ X v $G$$S$$S$$v_{out} = v_{in} \oplus X$$X$$v$$S$$X$$v_{in} = v_{out} \oplus X$$v$est pas en .$S$

Maintenant que nous avons la règle qu'un sommet n'est pas dans lorsque tous ses prédécesseurs ne sont pas dans , les lemmes suivent simplement en appliquant la règle à plusieurs reprises au diagramme de gadget ci-dessus.$S$$S$

Pas la réponse que l'auteur cherchait, voir les commentaires qui clarifient ce qu'est la «permutation» dans ce contexte.

J'ai augmenté la taille de l'ensemble dominant minimum pour le digraphe d'inclusion de groupe de permutation monogénique: https://oeis.org/A186202

Tout ce que vous avez à faire est de tester un membre de chaque décomposition du cycle principal.

Pour chaque cycle principal, il devrait suffire de coder les éléments comme (10101010 ...), puis (01010101 ..)?

------ Clarification ------ Le but de cette approche est de modéliser vos 2 ^ n cas de test sous forme de digraphe. Si un scénario de test réussi implique un autre scénario de test réussi, alors il vous suffit de tester l'ensemble dominant minimal de ce digraphe d'espace de test. Dans l'espace des permutations, OEIS A186202 est le maximum que vous devez tester pour détecter un sous-groupe non trivial ou prouver qu'aucun n'existe; ce nombre est encore grand mais beaucoup plus petit que n !.

- Utilisation - En utilisant n-1 zéros et 1 une en n itérations, vous pouvez détecter la permutation fixe que vous recherchez. Après cela, dans O (n {(n-1) \ choose (k-1)} (2 ^ (k-1)), vous pouvez tester que chaque ensemble de variables (k-1) n'affecte pas chaque index du shuffle . Puisque k est fixe c'est polynomial. Suis-je en train de manquer quelque chose?