Verbesserte Untergrenze für die Komplexität monotoner Schaltkreise bei perfekter Anpassung?

Razborov hat bewiesen, dass jede monotone Schaltung, die die perfekte Anpassungsfunktion für zweigeteilte Graphen berechnet, mindestens Gatter haben muss (er nannte es "logisch permanent"). Wurde seitdem eine bessere Untergrenze für dasselbe Problem nachgewiesen? (sprich ?) Soweit ich mich erinnere, war dieses Problem Mitte der 90er Jahre offen. $n^{\Omega(\log n)}$ $2^{n^\epsilon}$

Ich bin mir bewusst, dass die Clique-Funktion monotone Schaltkreise mit exponentieller Größe usw. erfordert, aber ich bin speziell an einer perfekten Anpassung interessiert.

cc.complexity-theory circuit-complexity matching Slimton
quelle

Antworten:

Eva Tardos bewies, dass die Lücke wirklich exponentiell ist, indem sie zeigte, dass es eine monotone Boolesche Funktion gibt, die Schaltkreise mit Polygröße enthält, jedoch monotone Schaltkreise mit Exponentialgröße erfordert. Nichts ist besser als Superpolynom für Matching bekannt.

Raz hat zur Folge, dass monotone Schaltkreise zur Anpassung eine lineare Tiefe haben. (Danke Klauck, dass du auf den Tippfehler hingewiesen hast.)

AFAIK, wir wissen nichts besseres.

Ref: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf

(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps

V Vinay
quelle

Komm schon, es ist lineare Tiefe (und seine Raz und Wigderson).

Hartmut Klauck

Komm schon, Hartmut, die Tiefenuntergrenze ist nur

N^{1 / 2}

$N^{1/2}$ wo

N

$N$ ist die Anzahl der Variablen (= Kanten). Bisher haben wir keine

Ω (N)

$\Omega(N)$ Tiefenuntergrenze, auch für monotone Schaltkreise. The Perfect Matching ist eine andere Geschichte. Keines der "verfeinerten" Argumente der unteren Schranke kann Rasborows untere Schranke schlagen

N^{Ω (\log N)}

$N^{\Omega(\log N)}$ auf die Größe.

Stasys