Разборов доказал, что каждая монотонная схема, которая вычисляет функцию идеального соответствия для двудольных графов, должна иметь как минимум вентилей (он назвал это «логическим перманентом»). Была ли лучшая оценка снизу для той же проблемы доказана с тех пор? (скажем 2 n ϵ ?) Насколько я помню, эта проблема была открыта в середине 1990-х годов.
Я знаю, что функция клика требует монотонных схем экспоненциального размера и т. Д., Но я особенно заинтересован в идеальном подборе.
Ева Тардос доказала, что разрыв действительно экспоненциальный, показав, что существует монотонная булева функция, которая имеет схемы с разным размером, но требует монотонных схем с экспоненциальным размером. Ничто лучше, чем супер-полином не известен для сопоставления.
В результате Raz монотонные схемы для согласования имеют линейную глубину. (Спасибо, Клаук, за указание на опечатку.)
AFAIK, мы не знаем ничего лучше.
Ссылка: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf
(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps