Résumé - Complexité en circuit monotone de la correspondance

Complexité en circuit monotone de la correspondance

2025-07-21 23:13:29

{"Bruno Cavalar","Mika Göös","Artur Riazanov","Anastasia Sofronova","Dmitry Sokolov"}

{cs.CC,math.CO}

L'article de Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova et Dmitry Sokolov établit que la fonction de correspondance bipartite sur les graphes à n sommets nécessite des circuits monotones de taille au moins 2^n. Cela améliore la borne inférieure précédente de n^Ω(log n) de Razborov (1985). La preuve utilise la méthode d'approximation standard combinée avec un nouveau lemme du chrysanthème pour les correspondances. Points clés : * L'article montre que la correspondance bipartite nécessite des circuits monotones de taille au moins 2^n, améliorant ainsi la borne inférieure précédente de n^Ω(log n) de Razborov (1985). * La preuve utilise la méthode d'approximation standard, qui implique de définir une distribution sur le domaine d'entrée et de montrer que si une fonction est calculée par un petit circuit monotone, alors elle peut être approximée par un petit DNF monotone. * Le cœur technique de la preuve consiste à identifier les situations où un DNF monotone peut être remplacé par un seul terme sans incurrir d'une erreur importante. * L'article prouve également des bornes inférieures pour la fonction "facteur impair", définie comme la fonction qui renvoie 1 si un graphe contient une sous-graphe couvrante dont les degrés sont tous impairs. * La preuve s'étend à d'autres distributions et fonctions, telles que le problème de satisfaisabilité Zq. * Les résultats ont des implications pour la complexité des propriétés des graphes et le pouvoir des circuits monotones.