Razborov udowodnił, że każdy obwód monotoniczny, który oblicza idealną funkcję dopasowania dla grafów dwustronnych, musi mieć co najmniej bramek (nazwał to „logicznym stałym”). Czy od tego czasu udowodniono lepszą dolną granicę dla tego samego problemu? (powiedzmy 2 n ϵ ?) O ile pamiętam ten problem był otwarty w połowie lat 90.
Zdaję sobie sprawę, że funkcja kliki wymaga obwodów monotonicznych wielkości wykładniczej i tak dalej, ale interesuje mnie właśnie idealne dopasowanie.
Eva Tardos udowodniła, że przerwa jest naprawdę wykładnicza, pokazując, że istnieje monotoniczna funkcja boolowska, która ma obwody wielowymiarowe, ale wymaga obwodów monotonicznych o wielkości wykładniczej. Nic lepszego niż super-wielomian nie jest znane z dopasowywania.
Raz powoduje, że obwody monotoniczne do dopasowania mają głębokość liniową. (Dzięki Klauck, za wskazanie literówki.)
AFAIK, nie wiemy nic lepszego.
Ref: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf
(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps