Obstacles et complexité du circuit monotone

15

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?monotone

Shiva Kintali
la source
2
Dick Lipton n'a-t-il pas écrit un article à ce sujet il y a quelques mois en discutant des preuves naturelles? (mise à jour): voici le lien: rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs
Suresh Venkat
4
Il existe des limites inférieures exponentielles connues sur les circuits monotones (Razborov 85, Alon+Boppana 87).
Iddo Tzameret
2
Raz et McKenzie n'ont-ils pas séparé toute la hiérarchie NC monotone? (R. Raz, P. McKenzie, "Séparation de la hiérarchie NC monotone")
Michaël Cadilhac
1
Une question connexe: cstheory.stackexchange.com/questions/2291/…
Gil Kalai
7
((N'utilisez pas pour mettre en italique; utilisez l' italique !))muneth
Jeffε

Réponses:

15

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.

András Salamon
la source
1
J'ai également trouvé que «Sur la démonstration des limites inférieures de la taille des circuits» de Karchmer était utile pour comprendre pourquoi les circuits monotones sont différents des circuits avec négation.
Kaveh
11

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.

Dick Lipton
la source
18
Bienvenue sur TCS SE !! Un grand merci à vos articles de blog, c'est vraiment un plaisir à lire!
Hsien-Chih Chang 張顯 之