De combien de négations avons-nous besoin pour calculer les fonctions monotones?

14

Razborov a prouvé que la correspondance de fonction monotone n'est pas en mP . Mais peut-on calculer l'appariement en utilisant un circuit de taille polynomiale avec quelques négations? Existe-t-il un circuit P / poly avec des négations qui calcule la correspondance? Quel est le compromis entre le nombre de négations et la taille pour l'appariement?O(nϵ)

Anonyme
la source

Réponses:

21

Markov a prouvé que toute fonction de n entrées peut être calculée avec seulement Journal(n+1) négations. Fisher a décrit une version constructive efficace. Voir aussi une exposition du résultat du blog GLL .

Plus précisément:

Théorème: Supposons que est calculé par un circuit C avec g portes, puis il est également calculé par un circuit C avec 2 g + O ( n 2 log 2 n ) portes et log ( n + 1 ) négations.F:{0,1}n{0,1}mCgC2g+O(n2Journal2n)Journal(n+1)

L'idée principale est d'ajouter pour chaque fil en C un fil parallèle w en C qui porte toujours le complément de w . Le cas de base est pour les fils d'entrée: Fisher décrit comment construire un circuit d'inversion I ( x ) = ¯ x avec O ( n 2 log 2 n ) portes et seulement log ( n + 1 ) négations. Pour les portes ET du circuit C , on peut augmenter unwCwCwje(X)=X¯O(n2log2n)log(n+1)C avec a = b c , et de même pour les portes OU. Les portes NOT en C ne coûtent rien, nous échangeons simplement les rôles de w et w ′ en aval de la porte NOT. De cette façon, l'ensemble du circuit en plus du sous-circuit de l'onduleur est monotone.a=bca=bcCww

AA Markov. Sur la complexité d'inversion d'un système de fonctions. J. ACM , 5 (4): 331–334, 1958.

MJ Fischer. La complexité des réseaux limités par la négation - Un bref aperçu. Dans la théorie des automates et les langages formels , 71–82, 1975

mikero
la source
Est-ce un circuit P / poly?
Anonyme
2
Oui, la taille du circuit passe de à 2 g + O ( n 2 log 2 n )n est le nombre d'entrées. J'ai élargi la réponse pour inclure un énoncé plus précis du résultat et le rendre plus autonome. g2g+O(n2log2n)n
mikero
4
Et certaines fonctions monotones explicites (multi-sorties) en P / poly nécessitent au moins négations pour rester en P / poly. lognO(loglogn)
Stasys
2
Pour cette ligne de questions (puissance des négations dans les circuits / formules / etc.), les éléments suivants peuvent être pertinents: eccc.hpi-web.de/report/2014/144 , eprint.iacr.org/2014/902 et eccc. hpi-web.de/report/2015/026 .
Clement C.
2
est suffisant pardimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html. 2g+O(nlogn)
Emil Jeřábek soutient Monica le
1

Comment calculer l'inversion de bits en utilisant n négations2n1n

Soit les bits triés dans l'ordre décroissant, c'est-à-dire que i < j implique x ix j . Ceci peut être réalisé par un réseau de tri monotone comme le réseau de tri Ajtai – Komlós – Szemerédi.x0,,x2n1i<jxixj

Nous définissons le circuit d'inversion pour bits I n ( x ) inductivement: Pour le cas de base, nous avons n = 1 et I 1 0 ( x ) : = ¬ x 0 . Soit m = 2 n - 1 . On réduit I n (pour 2 m + 1 ) bits à une porte I n - 1 (pour m2n1In(x)n=1I01(x):=¬x0m=2n1In2m+1In1mbits) et une porte de négation utilisant les portes et . Nous utilisons la négation pour calculer ¬ x m . Pour i < m soit y i : = ( x i¬ x m ) x m + i . Nous utilisons I n - 1 pour inverser y . Maintenant, nous pouvons définir I n comme suit:¬xmi<myi:=(xi¬xm)xm+iIn1yIn

Iin:={Iin1(y)¬xmi<m¬xmi=mIin1(y)¬xmi<m

xxnx

De Michael J. Fischer, La complexité des réseaux à négation limitée - une brève enquête, 1975.

Anonyme
la source