Welche nicht regulären Sprachen sind in ?

11

Zum Beispiel weiß ich, dass die nicht reguläre Sprache anbn in AC0 . Ich würde gerne weitere Beispiele wie dieses kennenlernen.

Alex Grilo
quelle
Palindrome ( {wwR} )
Vor dem
Was ist ? AC0
vonbrand
@vonbrand, ist die Klasse von Schaltkreisen mit konstanter Tiefe, die unbegrenztes Fan-In enthalten und / oder Gates. Das heißt, jedes Gate in einer Schaltung ist entweder ein "und" oder ein "oder" Gate und erlaubt eine unbegrenzte Anzahl von Eingängen.AC0
Nicholas Mancuso

Antworten:

9

Sprachen in können komplizierter sein, als es die naive Intuition vermuten lässt.AC0

  • Offensichtlich enthält { a n b n c n } , was nicht kontextfrei ist.AC0{anbncn}
  • Jede unäre Sprache ist in ungleichmäßigem ; Zum Beispiel das Stoppproblem in unary ausgedrückt.AC0
  • Die Addition kann in mit einem Carry-Lookahead-Addierer implementiert werden . Hier besteht der Eingang aus 2 n Bits, die zwei Zahlen darstellen, und der Ausgang enthält n + 1 Drähte (äquivalent kann jedes Ausgangsbit in A C 0 realisiert werden ).AC02nn+1AC0
  • Multiplexing: ist in A C 0 .{wx:|w|=2n,|x|=n,w[x]=1}AC0

    Ein Multiplexer ist eine Funktion für Variablen, die den Wert einer von 2 n Variablen ausgibt , wobei der Index durch die n Variablen bestimmt wird. (Gleiches gilt, wenn der Index unär geschrieben ist.)2n+n2nn

  • Die Berechnung der 3SAT-Formeln erfolgt in .AC0

    Die Eingabe besteht aus Variablen, gefolgt von einigen Klauseln. Jede enthält drei Literale, wobei jedes Literal ein Index der Variablen ist (unär oder binär, spielt keine Rolle) und ein Bit, das eine mögliche Negation anzeigt. Sie können die Literale mit Multiplexern auswerten und dann eine Schicht von ODERs und dann ein großes UND darüber hinzufügen.n

  • enthält keine Mehrheit, aber eine ungefähre Mehrheit: eine Funktion, die der Mehrheit entspricht, wenn die Ausgabe1 istAC0Nullen oder Einsen. Siehe "Ungefähre Zählung mit gleichmäßigen Schaltungen mit konstanter Tiefe" von Ajtai.12+ε

wird unter logischen Operationen, Verkettung und Zusammensetzung geschlossen, sodass Sie die obigen Beispiele kombinieren können. Jetzt sollten Sie etwas Respekt vor P a r i t y A C 0 und anderen unteren Grenzen der Schaltung haben!AC0ParityAC0

sdcvvc
quelle
Haben Sie Hinweise darauf? Insbesondere das unäre Halteproblem liegt in . Da A C 0A C = N C P ist , verstehe ich das nicht (es ist spät, wo ich bin, das könnte meine Entschuldigung sein). AC0AC0AC=NCP
Pål GD
1
Es ist ungleichmäßig (wie P / p o l y ), wobei die Schaltung beliebig mit der Eingangslänge variieren kann. AC0P/poly
SDCVVC
@ PålGD, es ist im Text von Arora und Barak angelegt.
Nicholas Mancuso
Haben Sie eine Referenz für einen Beweis, dass Multiplexing in AC0 ist?
Alex Grilo
1
@ Alex Grilo, leider nein; Ich denke es ist Folklore. Mach . i=02n1(x=iw[i]=1)
SDCVVC