Quelles langues non régulières sont dans ?

11

Par exemple, je sais que la langue non régulière est en . J'aimerais en savoir plus d'exemples comme celui-ci.anbnAC0

Alex Grilo
la source
Palindromes ( ){wwR}
Vor
Qu'est-ce que ? AC0
vonbrand
@vonbrand, est la classe de circuits à profondeur constante contenant et / ou des portes de fan-in illimité. C'est-à-dire que chaque porte d'un circuit est soit une porte "et" soit une porte "ou" et autorise un nombre illimité d'entrées.AC0
Nicholas Mancuso

Réponses:

9

Les langues en peuvent être plus compliquées que ne le suggère l'intuition naïve.AC0

  • De toute évidence, contient , qui n'est pas sans contexte.AC0{anbncn}
  • Chaque langue unaire est en non uniforme ; par exemple, le problème d'arrêt exprimé en unaire.AC0
  • L'addition peut être implémentée dans avec un additionneur d'anticipation. Ici, l'entrée est de bits représentant deux nombres, et la sortie contient fils (de manière équivalente, chaque bit de sortie peut être réalisé en )AC02nn+1AC0
  • Multiplexage: est en .{wx:|w|=2n,|x|=n,w[x]=1}AC0

    Un multiplexeur est une fonction sur variables qui délivre la valeur de l'une des variables, où l'indice est déterminé par les variables. (Il en va de même si l'index est écrit en unaire.)2n+n2nn

  • Le calcul des formules 3SAT est en .AC0

    L'entrée se compose de variables, suivies de quelques clauses, chacune contenant trois littéraux, où chaque littéral est un index de la variable (unaire ou binaire, peu importe) et un bit indiquant une éventuelle négation. Vous pouvez évaluer les littéraux avec des multiplexeurs, puis ajouter une couche de blocs opératoires, puis un grand ET en haut.n

  • AC0 ne contient pas la majorité, mais il contient la majorité approximative: une fonction qui est égale à la majorité si la sortie est zéros ou uns. Voir "Comptage approximatif avec des circuits uniformes à profondeur constante" par Ajtai.12+ε

AC0 est fermé sous opérations logiques, concaténation et composition, vous pouvez donc combiner les exemples ci-dessus. Maintenant, vous devriez ressentir du respect pour et les autres limites inférieures du circuit!ParityAC0

sdcvvc
la source
Avez-vous des références à cela? Surtout que le problème d'arrêt unaire est dans . Puisque , je ne comprends pas (il est tard où je suis, cela pourrait être mon excuse). AC0AC0AC=NCP
Pål GD
1
C'est non uniforme (comme ), où le circuit peut varier arbitrairement avec la longueur d'entrée. AC0P/poly
sdcvvc
@ PålGD, il est présenté dans le texte Arora et Barak.
Nicholas Mancuso
Avez-vous une référence pour une preuve que le multiplexage est en AC0?
Alex Grilo
1
@Alex Grilo, malheureusement non; Je pense que c'est du folklore. simplement . i=02n1(x=iw[i]=1)
sdcvvc