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

27

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

Un circuit booléen est appelé circuit NC 0 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 0 k avec entrée à n bits et sortie à n bits.
Question : Le circuit donné calcule-t-il une permutation sur {0, 1} n ? En d'autres termes, la fonction calculée par le circuit est-elle une bijection de {0, 1} n à {0, 1} n ?

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} n » signifie une cartographie bijective de {0, 1} n à 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.

Tsuyoshi Ito
la source
1
Note personnelle: Lorsque j'ai posté une réponse à la question de QiCheng, je l'ai fait simplement parce que le problème semblait intéressant, sans application particulière à l'esprit. Plusieurs mois après cela, je me trouvais dans une situation où je devais expliquer à quelqu'un qu'il était loin d'être trivial de décider si un programme donné calculait une permutation ou non. Grâce à la question de QiCheng, j'ai eu un exemple parfait (quelle coïncidence!). Après cela, je suis devenu plus curieux des cas de k = 3 et k = 4. Je soupçonne que le cas de k = 3 est déjà coNP-complet, mais je n'ai pas pu prouver de toute façon.
Tsuyoshi Ito
ce problème semble être un cas particulier du problème du Circuit de Pigeonhole défini par Papadimitriou ( sciencedirect.com/science/article/pii/S0022000005800637 ) qui est complet pour PPP en ce qui concerne les réductions de poly-temps entre les problèmes de recherche.
Marcos Villagra
@Marcos Villagra: Merci pour le commentaire, mais je crains qu'en disant «cas particulier de», vous changiez considérablement la définition du problème du circuit des colombages. Une propriété importante du problème du circuit Pigeonhole est qu'il s'agit d'un problème de recherche total , alors que le problème actuel (considéré comme un problème de recherche pour deux entrées qui produisent la même sortie) n'est pas un problème de recherche total.
Tsuyoshi Ito du

Réponses:

3

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).NC30

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 ϕ ϕϕmGϕϕ

   |
   |               |
   |               |
   |               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 tϕGϕNC30n+vnϕvGϕGxϕxxin 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 .xoutll=xlin=xinll=¬xlin=¬xinvGvvinvout

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 nxϕxout=xin

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 nu i nv(u,v)vout=vinuin

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 nl i n ) l i n x i n x lv(u,v)lvout=vin(uinlin)linxinxl

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 nw i n )v(u,v)(w,v)vout=vin(uinwin)

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

Cas de preuve d'exactitude 1: est satisfiableϕ

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

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.Gϕ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.Gϕ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.NC30

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 nxϕxout=xinxin

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 nu i n G v o u t = v i nu i n = 0 0 = 0 v o u t = v i nu i n = 1 1 = 0v(u,v)vout=vinuinGvout=vinuin=00=0vout=vinuin=11=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 nl ) l v i n v o u t = v i n( u i nl ) = v i n( u i n0 ) = v i n = 0v(u,v)lvout=vin(uinl)lvinvout=vin(uinl)=vin(uin0)=vin=0v 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 nl ) = v i n( u i n1 ) = v i nu i n = vlvin(u,v)uuin=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.uin=vinlvout=vin(uinl)=vin(uin1)=vinuin=vinvin=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 nw i n )v(u,v)(w,v)vout=vin(uinwin)

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 nw 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 =vuwvout=vin(uinwin)=0(00)=0uin ); 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 nw i n ) = (uin=L1winwin=L2vinvin=L1L2 . Ainsi, les sorties de cette forme seront toujours les mêmes (et en fait zéro) entre les deux ensembles d'entrées.vout=vin(uinwin)=(L1L2)(L1L2)=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 nw 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 = Lvuwvout=vin(uinwin)=0(00)=0uin ); 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 nw i n ) = 1 ( ( L 1 L 2 ) L 3 )uin=L1L2winwin=L3vin=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.vout=vin(uinwin)=1((L1L2)L3)=1(L1L2L3)=11=0(L1L2L3)=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.NC30

Cas de preuve d'exactitude 2: n'est pas satisfaisantϕ

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.ϕNC30

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 .xinxϕ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.SvGvin

Nous prouverons les lemmes suivants ci-dessous:

SS

SS

SGSS

(L1L2L3)(u,v)Lvout=vin(uinL)L=0vout=vin(uinL)=vin(uin0)=vin0=vinvinvSS

SNC30

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 nX X v S X v i n = v o u tX v SGSSvout=vinXXvSXvin=voutXvest 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.SSS

Mikhail Rudoy
la source
-1

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?

Chad Brewbaker
la source
Hmm. Je ne sais pas si le (01) *, (10) * est suffisant. Vous devrez peut-être essayer toutes les configurations 2 ^ p pour chaque cycle principal.
Chad Brewbaker
2
Désolé, Chad, tu m'as perdu. Vous savez que la question est de savoir si la fonction est bijective? (Il y a telles fonctions bijectives.) Il ne s'agit pas de savoir si les bits de sortie sont une permutation (réorganisation) des bits d'entrée - c'est un problème beaucoup plus facile, auquel on peut répondre simplement en exécutant la commande circuit sur toutes les entrées possibles avec zéros et un. n - 1 1(2n)!n11
DW
2
Chad, oui, je crois que vous manquez peut-être quelque chose. L'affiche demande si la fonction est une fonction bijective (c'est-à-dire qu'il n'existe pas tel que et ). Il ne demande pas si la fonction permute (mélange / réorganise / réordonne) les bits d'entrée. Voyez-vous la différence? Je soupçonne que vous avez répondu à la mauvaise question. x , x { 0 , 1 } n C ( x ) = C ( x ) x C:{0,1}n{0,1}nx,x{0,1}nC(x)=C(x) CxxC
DW
2
Merci d'avoir essayé d'aider, mais comme DW l'a expliqué, je crains que la question à laquelle vous avez répondu soit différente de celle que j'ai posée. "Une permutation sur {0,1} ^ n" signifie une fonction bijective de {0,1} ^ n à elle-même, et cela ne signifie pas de réarranger les n bits.
Tsuyoshi Ito
3
Chad, cela vous dérangerait-il de supprimer cette réponse ou au moins d'ajouter une note en haut que cela ne répond pas à la question de Tsuyoshi?
Kaveh