Die Grenzen ...
Wir haben tatsächlich , siehe Satz 4 in (Gruber & Holzer 2006). Für eine Obergrenze haben wir 2 C o v ( M ) + C o v ( N ) ≥ D F A ( L ) ≥ N F A ( L ) , siehe Satz 11 in derselben Veröffentlichung. NFA(L)≥Cov(M)+Cov(N)2Cov(M)+Cov(N)≥DFA(L)≥NFA(L)
... kann nicht wesentlich verbessert werden
Zwischen und N F A ( L ) kann eine subexponentielle Lücke bestehen . Das folgende Beispiel und der Beweis der Lücke ist eine Anpassung eines ähnlichen Beispiels, das die Einschränkungen von 2-Parteien-Protokollen zum Nachweis von Untergrenzen für die Komplexität nichtdeterministischer Zustände aus (Hromkovič et al. 2009) veranschaulicht:Cov(M)+Cov(N)NFA(L)
Wir verwenden das Alphabet . Sei L = {[n]={1,2,…,n} .L={xyz∈[n]3∣x=y∨x≠z}
Wir kümmern uns zuerst um . Beachten Sie, dass , wenn w = x y z mit y = z , dann
w ∈ L : Bei x = y , w ∈ L und im Fall x ≠ y , wir haben auch
x ≠ z und damit w ∈ L . Auch wenn w die Form x y z mit
y ≠ z hat , dannCov(M)w=xyzy=zw∈Lx=yw∈Lx≠yx≠zw∈Lwxyzy≠zw∈Lx≠zL=L′∪L′′L′={xyz∈[n]3∣y=z}L′′={xyz∈[n]3∣y≠z∧x≠z}
Betrachten Sie nun die zweigeteilten Graphen mit , , sowie mit , ,
und . Dann führt eine biclique Kantenabdeckung für den Graphen
zu einer Abdeckung von mit monochromatischen Submatrizen,G′=(U′,V′,E′)U′=[n]V′={yz∈[n]2∣y=z}E′=U′×V′G′′=(U′′,V′′,E′′)U′′=[n]V′′={yz∈[n]2∣y≠z}E′′={(x,yz)∣x≠z}G=(U′∪U′′,V′∪V′′,E′∪E′′)GM1
Ein einfacher Kernelisierungstrick zum Berechnen einer Biclique-Kantenabdeckung für
besteht darin, die Zwillingsscheitelpunkte von in Äquivalenzklassen einzuteilen. Dann machen wir dasselbe im resultierenden Graphen für die Zwillingsscheitelpunkte von . Zwillingsscheitelpunkte sind solche mit identischer Nachbarschaft. Dieser Schritt ändert nicht die Mindestanzahl von Bicliques, die erforderlich sind, um alle Kanten im jeweiligen Diagramm abzudecken.G′U′V′
Der Kernelisierungsschritt reduziert zu einem Graphen mit zwei Eckpunkten und einer einzelnen Kante. Somit können die Kanten von mit einem einzigen Fahrrad bedeckt werden. Anwenden der Problemkern Schritt eine Ausbeuten crown Graphen
auf Scheitelpunkte , deren bipartite Dimension (die minimale biclique Randabdeckung Nummer) bekannt sein , wobei die inverse Funktion des mittleren Binomialkoeffizient ist ( De Caen et al. 1981). Beachten Sie, dass . Somit wird die Dimension des bipartite ist , die gleich ist .G′G′G′′2nσ(n)σσ(n)=O(logn)G1+σ(n)Cov(M)
Betrachten Sie nun . Beachten Sie, dass , wenn mit , dann . Wenn , dann iff . Wir können also
mit und . Fast das gleiche Argument wie oben ergibt
.Cov(N)w=xyzx=yw∈Lx≠yx∈Lx≠zL=L′′′∪L′′′′L′′′={xyz∈[n]3∣x=y}L′′′′={xyz∈[n]3∣x≠y∧x≠z}Cov(N)=1+σ(n)
Es bleibt eine Untergrenze für die nichtdeterministische Zustandskomplexität von . Beachten Sie, dass alle Wörter der Form
mit . für jedes dieser Wörter eine akzeptierende Berechnung einer minimalen NFA fest, die akzeptiert . Es sei der Zustand, der nach dem Lesen des Präfixes , und der Zustand, der nach dem Lesen des Präfixes des Eingabeworts . Dann müssen alle Paare unterschiedlich sein. Aus Gründen des Widerspruchs sei
für einigeLLxxxx∈[n]xxxLpxxqxxxxxx(px,qx)(px,qx)=(py,qy)x≠y. Dann können wir eine akzeptierende Berechnung auf Eingabe konstruieren , derart , dass der NFA im Zustand nach dem Lesen des Präfix , und in Zustand nach dem Präfix Lesen . Aber die Zeichenfolge ist nicht in . Für die Zustandsmenge der NFA zeigt dies, dass . Somit erhalten wir für großes eine subexponentielle Trennung zwischen und(die nichtdeterministische Zustandskomplexität von ).xyxpx=qxxqy=qxxyxyxLQ|Q|2≥nnCov(M)+Cov(N)|Q|L
Verweise
Dominique de Caen, David A. Gregory, Norman J. Pullman: Der boolesche Rang der Null-Eins-Matrizen, in: Cadogan, Charles C. (Hrsg.), 3. Karibische Konferenz für Kombinatorik und Informatik, Fakultät für Mathematik, Universität West Indies, S. 169–173 (1981)
Hermann Gruber und Markus Holzer. Es ist schwierig, Untergrenzen für die Komplexität nichtdeterministischer Zustände zu finden . Bericht TR06-027, Elektronisches Kolloquium über Computerkomplexität (ECCC), März 2006. Kurzfassung erschienen in: Oscar H. Ibarra und Zhe Dang, Herausgeber, 10. Internationale Konferenz über Entwicklungen in der Sprachtheorie (DLT 2006), Santa Barbara (CA) , USA, Band 4036 von LNCS, Seiten 363-374. Springer, Juni 2006.
Juraj Hromkovic, Holger Petersen, Georg Schnitger: Über die Grenzen der Kommunikationskomplexitätstechnik zum Nachweis von Untergrenzen für die Größe minimaler NFAs . Theor. Comput. Sci. 410 (30–32): 2972–2981 (2009)