Razborov demostró que cada circuito monótono que calcula la función de coincidencia perfecta para gráficos bipartitos debe tener al menos compuertas (lo llamó "lógico permanente"). ¿Se ha demostrado un límite inferior mejor para el mismo problema desde entonces? (diga 2 n ϵ ?) Hasta donde recuerdo, este problema estaba abierto a mediados de la década de 1990.
Soy consciente de que la función de camarilla requiere circuitos monótonos de tamaño exponencial, etc., pero estoy interesado específicamente en la coincidencia perfecta.