Untergrenzen für die Komplexität des monotonen Raums

Die monotone Raumkomplexität einer Sprache kann in Form von monotonen Vermittlungsnetzwerken definiert werden (siehe z. B. "Average Case Lower Bounds for Monotone Switching Networks" von Filmus et al.). Dieser Begriff ist mit der monotonen verknüpft N C Hierarchie und kann Anwendungen auf die nicht-monotone Einstellung hat , für die die meisten Fragen offen sind.$L \subseteq \Sigma^*$$NC$

Hier ist eine äquivalente Definition in Bezug auf Schaltungen. Sei eine Schaltung (oder ein Tag), deren Bögen durch Elemente von [ n ] × Σ gekennzeichnet sind und die einen einzelnen Wurzelknoten r hat . Wir sagen , dass K ein Wort akzeptiert w & egr ; & Sgr; n genau dann , wenn es eine Wurzel-Blatt Pfad P in K , dessen Sequenz von Etiketten Streichhölzer w , dh für jedes Etikett ( i , a ) in P haben wir w [ i ] = a . Nun eine Sprache gegeben$K$$[n] \times \Sigma$$r$$K$$w \in \Sigma^n$$P$$K$$w$$(i,a)$$P$$w[i] = a$ , für jede ganze Zahl n definieren wir ihre n- Scheibenkomplexität C L ( n ) als die minimale Größe einer Schaltung, die genau die Wörter in L ∩ Σ n akzeptiert. Wir können diesem Begriff einige Einschränkungen auferlegen, indem wir beispielsweise verlangen, dass die Schaltungen einmal gelesen werden, was bedeutet, dass jeder akzeptierende Pfad einen einzelnen Zugriff auf eine bestimmte Position gewährt. Dies führt zu einem zweiten Komplexitätsmaß C ' L ( n ), das einfacher zu analysieren scheint, wie nachstehend dargestellt.$L$$n$$n$$C_L(n)$$L \cap \Sigma^n$$C'_L(n)$

Ein Beispiel ist das Perfect Matching-Problem ( ), von dem gezeigt werden kann, dass es eine monotone Komplexität C ' P M ( n ) = 2 Ω ( n ) wie folgt aufweist. Es sei P M n die Schicht der Sprache, die zweigeteilten Graphen G mit n Eckpunkten auf jeder Seite der Zweiteilung entspricht (bezeichnet mit A , B ). Betrachten Sie eine Schaltung K, die dies akzeptiert. Wenn eine ganze Zahl k gegeben ist, bezeichne P k die Menge der Pfade der Länge $PM$$C'_{PM}(n) = 2^{\Omega(n)}$$PM_n$$G$$n$$A,B$$K$$k$$\mathcal{P}_k$$k$in ausgehend von der Wurzel, und T k bezeichne das Mengenpaar ( S , T ) mit S ⊆ A , T ⊆ B und | S | = | T | = k . Durch Monotonie können wir folgende Annahme treffen:$K$$\mathcal{T}_k$$(S,T)$$S \subseteq A, T \subseteq B$$|S| = |T| = k$

(*) Für jeden Knoten der Tiefe k gibt es ein Tupel t = ( S , T ) ∈ T k, so dass jeder Pfad P ∈ P k, der zu u führt, durch eine Permutation σ P : S → T gekennzeichnet ist .$u$$k$$t = (S,T) \in \mathcal{T}_k$$P \in \mathcal{P}_k$$u$$\sigma_P : S \rightarrow T$

Wenn zwei verschiedene Pfade zu , die verschiedenen Tupeln entsprechen, könnte einer von ihnen auf eine Funktion erweitert werden, die keine Permutation ist (und somit einen n- Kanten-Graphen erkennen würde, der nicht übereinstimmt).$u$$n$

Nun beachten Sie, dass wir die folgenden „Abdeckung“ Eigenschaft haben muss: für jede Permutation , es sollte eine gewisse Pfad existieren P ∈ P k , so dass σ erstreckt σ P . Beachten Sie, dass eine gegebene Permutation σ P auf höchstens ( n - k ) erweitert werden kann ! verschiedene Permutationen, und dass ein gegebenes Tupel in T k höchstens k induzieren kann ! verschiedene Permutationen. Dies impliziert, dass die Anzahl der Knoten in der Tiefe k mindestens n beträgt$\sigma : A \rightarrow B$$P \in \mathcal{P}_k$$\sigma$$\sigma_P$$\sigma_P$$(n-k)!$$\mathcal{T}_k$$k!$$k$. Insbesondere die Anzahl der Knoten auf Ebene$\frac{n!}{k! (n-k)!}$ ist mindestensn$\frac{n}{2}$.$\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$

Es gibt zwei Dinge , Ich mag würde verstehen: (i) warum bricht diese Argumentation für Read-Many / nonmonotone Raum Komplexität nach unten, (ii) wie funktioniert es bezieht sich auf bekannte untere Schranken für die monotonen Raum Komplexität von .$PM$

Dies ist keine Antwort, sondern ein "erweiterter Kommentar".

Zu Frage (i): Eigenschaft (*) gilt aufgrund des einmaligen Lesens, nicht aufgrund der Monotonie, und aus diesem Grund schlägt das Argument im Fall des vielen (sogar monotonen) Lesens fehl: Dann müssen die kombinierten Pfade keine PMs sein. Dies können beliebige Graphen sein, die eine PM enthalten.

$O(n^3)$

$n^{\Omega(\log n)}$