Limite inférieure améliorée sur la complexité du circuit monotone de l'adéquation parfaite?

Razborov a prouvé que chaque circuit monotone qui calcule la fonction de correspondance parfaite pour les graphes bipartis doit avoir au moins portes (il l'a appelé "permanent logique"). Une meilleure borne inférieure pour le même problème a-t-elle été prouvée depuis lors? (disons ?) Pour autant que je me souvienne, ce problème était ouvert au milieu des années 90. $n^{\Omega(\log n)}$ $2^{n^\epsilon}$

Je suis conscient que la fonction de clique nécessite des circuits monotones de taille exponentielle, etc., mais je suis particulièrement intéressé par une correspondance parfaite.

cc.complexity-theory circuit-complexity matching slimton
la source

Réponses:

Eva Tardos a prouvé que l'écart est vraiment exponentiel en montrant qu'il existe une fonction booléenne monotone qui a des circuits de taille poly mais nécessite des circuits monotones de taille exponentielle. Rien de mieux qu'un super-polynôme est connu pour l'appariement.

Raz a pour résultat que les circuits monotones pour l'adaptation ont une profondeur linéaire. (Merci Klauck, d'avoir pointé la faute de frappe.)

AFAIK, nous ne savons rien de mieux.

Réf: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf

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

V Vinay
la source

Allez, c'est la profondeur linéaire (et ses Raz et Wigderson).

Hartmut Klauck

Allez, Hartmut, la limite inférieure de profondeur n'est que où est le nombre de variables (= bords). Jusqu'à présent, nous n'avons pas de limite inférieure de profondeur , même pour les circuits monotones. The Perfect Matching est une autre histoire. Aucun des arguments de limite inférieure "raffinés" ne peut battre la limite inférieure de Razborov sur la taille.

N^{1 / 2}

$N^{1/2}$

N

$N$

Ω (N)

$\Omega(N)$

N^{Ω (\log N)}

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

Stasys