Décider si un circuit

27

Quelle est la complexité de décider si un circuit avec bits d'entrée et bits de sortie calcule une permutation de ? en d'autres termes, si chaque chaîne de bits dans est une sortie du circuit pour une entrée? Cela ressemble à un problème qui a été étudié, mais je ne trouve aucune référence. nn{0,1 } n {0,1 } nNC0nn{0,1}n{0,1}n

QiCheng
la source
1
La limite évidente est qui fonctionne également pour (vérifiez si la fonction est injective). PcoNPP
Kaveh
Qu'entendez-vous par «un circuit NC0»? L'expression habituelle est «famille de circuits NC0», qui est (peut-être malheureusement) souvent abrégée en «circuit NC0», mais je ne pense pas que vous vouliez parler d'une famille de circuits NC0 dans votre question.
Tsuyoshi Ito
1
Par un circuit , je veux dire que chaque bit de sortie du circuit dépend uniquement du nombre constant de bits d'entrée. NC0
QiCheng
3
Oui, je pose des questions sur une famille. Pour clarifier les choses, vous pouvez remplacer par où chaque bit de sortie ne dépend que de bits d'entrée dans la famille. N C 0 5 5NC0NC505
QiCheng
1
Cela ne répond pas à votre question, mais si le problème est généralisé de sorte que chaque bit de sortie soit autorisé à dépendre des bits d'entrée O (log n), alors je pense que le problème est coNP-complet sous Turing réductibilité. Cela découle de l'exhaustivité de la coNP de la réversibilité finie des automates cellulaires bidimensionnels ( Durand, 1994 ) en représentant chaque cellule d'un automate cellulaire bidimensionnel comme une chaîne binaire à O (log n) bits.
Tsuyoshi Ito du

Réponses:

29

Dureté

Suite à votre commentaire sur la question, nous appellerons un circuit où chaque bit de sortie dépend au plus de k bits d'entrée un « circuit NC 0 k ». En utilisant ce terme, votre problème est coNP-complet dans le cas de circuits NC 0 5 . Autrement dit, le problème suivant est coNP-complet.

Par exemple : un circuit booléen C avec n bits d'entrée et de n bits de sortie , où chaque bit de sortie dépend d'au plus cinq bits d'entrée.
Question : Le mappage de {0,1} n à lui-même est-il calculé par la bijective C ?

Comme l'a commenté Kaveh, il est clairement en coNP, même sans limite sur le nombre de bits d'entrée dont dépend chaque bit de sortie. Pour prouver la dureté coNP, nous allons réduire 3SAT au complément du problème actuel. L'idée clé de la réduction est la même que celle utilisée dans le document [Dur94] de Durand, que j'ai mentionné dans un commentaire sur la question, mais la réduction globale est beaucoup plus simple dans notre cas.

Étant donné une formule 3CNF φ avec n variables et m clauses, nous construisons un circuit booléen C avec ( n + m ) bits d'entrée et ( n + m ) bits de sortie comme suit. Nous étiquetons les bits d'entrée comme x 1 ,…, x n , y 1 ,…, y m et les bits de sortie comme x1 ,…, xn , z 1 ,…, z m . On considère que les bits d'entrée x1 ,…, x n spécifient une affectation de vérité aux n variables dans φ .

  • xi = x i pour 1≤ in . C'est-à-dire que les n premiers bits d'entrée sont toujours copiés sur les n premiers bits de sortie.
  • Pour 1≤ im , si la i ème clause de φ est satisfaite, alors z i = y iy i +1 , où l'indice est interprété modulo m . Sinon, z i = y i .

Notez que chaque bit de sortie dépend d'au plus cinq bits d'entrée. J'omets la preuve de l'exactitude de la réduction, mais l'idée clé (que j'ai empruntée à [Dur94]) est que si φ est satisfaisable et que les bits d'entrée x 1 ,…, x n sont définis sur une affectation satisfaisante de φ , alors les m bits de sortie z 1 ,…, z m sont contraints d'avoir la parité paire, et donc le circuit ne peut pas être une permutation. D'autre part, si les bits d'entrée x 1 , ..., x n sont définis sur une affectation de non-satisfaction de φ , alors les bits de sortie z1 ,…, z m peut être réglé sur n'importe quoi; de ce fait, si φ n'est pas satisfaisant, alors le circuit est une permutation.

Tractabilité

Côté tractable, votre problème est en P pour les circuits NC 0 2 . Ceci est illustré comme suit. En général, chaque bit de sortie dans un circuit booléen pour une permutation est équilibré ; c'est-à-dire, exactement la moitié des chaînes d'entrée définissent le bit de sortie sur 1. Cependant, chaque fonction booléenne équilibrée de {0,1} 2 à {0,1} est affine ; c'est-à-dire une copie d'un seul bit d'entrée, le XOR des deux bits d'entrée, ou leur négation. Par conséquent, nous pouvons d'abord vérifier que chaque bit de sortie est équilibré, puis vérifier la bijectivité par élimination gaussienne.

Je ne connais pas la complexité en cas de circuits NC 0 3 ou en cas de circuits NC 0 4 .

Les références

[Dur94] Bruno Durand. Inversion des automates cellulaires 2D: quelques résultats de complexité. Informatique théorique , 134 (2): 387–401, novembre 1994. DOI: 10.1016 / 0304-3975 (94) 90244-5 .

Tsuyoshi Ito
la source
3
J'ai posté une question de suivi sur le cas des circuits NC ^ 0_3.
Tsuyoshi Ito