Les preuves naturelles sont une barrière pour prouver les limites inférieures de la complexité des circuits des fonctions booléennes. Ils ne signifient pas directement une telle barrière à prouver minorations sur le complexité du circuit. Y a-t-il des progrès vers l'identification de tels obstacles? Y a-t-il d'autres obstacles dans le cadre monotone?
cc.complexity-theory
circuit-complexity
barriers
natural-proofs
Shiva Kintali
la source
la source
85, Alon+Boppana87).Réponses:
Le récent article de Benjamin Rossman résume l'état de l'art de la complexité des circuits monotones de k-CLIQUE. En bref, Razborov s'est avéré une borne inférieure en 1985, améliorée par la suite par Alon et Boppana en 1987: , par rapport à la borne supérieure de force brute O ( n k ) .ω ( nk/ (journaln )k) O ( nk)
Rossman montre une borne inférieure de pour la complexité du cas moyen dans le modèle Erdős-Rényi des graphiques aléatoires; Amano a précédemment montré qu'il s'agissait essentiellement de la limite supérieure. Le lemme quasi-tournesol qui constitue un élément clé du papier est plutôt net.ω ( nk / 4)
La barrière des preuves naturelles ne semble donc pas s'appliquer à la complexité des circuits monotones.
Norbert Blum a expliqué pourquoi les limites inférieures des circuits monotones sont essentiellement différentes des circuits avec négations. L'observation clé d'Éva Tardos est qu'une petite modification de la fonction thêta de Lovász a une complexité de circuit monotone exponentielle.
la source
On donne au point une fonction booléenne générale f il y a une fonction booléenne monotone g de sorte que toute limite inférieure super linéaire sur g en implique une sur f. Ou plus la complexité générale de f est égale à la complexité monotone de g jusqu'à O (n).
Je ne sais toujours pas comment cela se rapporte aux obstacles.
la source