Est-il supposé que les limites inférieures de la taille des circuits monotones s'appliquent également aux circuits booléens généraux?

Question

A "Général" Circuit Boolean (Combinatoiral) est un étiqueté (avec les étiquettes: et, ou, non in), dirigé, graphique acyclique, qui satisfait:

1. fan-in= 2 pour les et ou les nœuds
2. fan-n= 1 pour les nœuds non
3. fan-in= 0 pour les nœuds dans les nœuds
4. fan-out= 0 à exactement un nœud (le nœud OUT)
5. fan - sortie sans bornes au reste des nœuds (mais le nœud OUT)

Un circuit monotone est un circuit booléen avec 0 sommets étiquetés comme "non".

La taille d'un circuit est le nombre de "portes" (sommets avec des étiquettes "et", "ou" ou "non") contient.

Nous connaissons beaucoup de limites inférieures sur la taille des circuits monotones, que nous ne savons pas comment prouver sur un circuit booléen général (tel que Celui-ci sur le problème de la clique).

Ma question est la suivante: supposons-nous que les limites inférieures prouvées sur des circuits monotones s'appliquent également à des circuits Booleans (car ils calculent la fonction monotone), et nous ne savons tout simplement pas comment le prouver ; ou nous supposons que \ Sachons que ces limites inférieures ne s'appliquent pas aux circuits booléens généraux équivalents?

Dans ce dernier cas, pourriez-vous me fournir un exemple de fonction monotone calculée à la fois par un circuit monotone et un circuit booléen général, tandis que la taille du circuit monotone est gretate que le circuit booléen général? (J'ai été coincé dessus pendant des heures, cherchant un tel exemple, je crois donc qu'il n'y a pas d'exemple ..)

Answer 1

Éva Tardos a donné un fonction qui peut être calculée par un circuit général de taille polynomiale mais nécessiteUn circuit monotone de taille exponentielle.Le circuit calcule une approximation suffisante de la fonction de Lovász theta du graphique d'entrée.

RAZBOROV a donné un $ N ^ {\ OMEGA (\ journal n)} $ Circuits monotone liés inférieurs Circulation de la fonction de correspondance parfaite bipartite, pour laquelle des circuits généraux de taille polynomialeexiste.