Barrieren und monotone Schaltungskomplexität

15

Natürliche Beweise sind ein Hindernis für den Nachweis der unteren Schranken der Schaltungskomplexität von Booleschen Funktionen. Sie implizieren keine solche Barriere für den Nachweis der unteren Schranken der Komplexität der Schaltung. Gibt es Fortschritte bei der Identifizierung solcher Hindernisse? Gibt es andere Barrieren in der monotonen Einstellung?monotone

Shiva Kintali
quelle
2
Hat Dick Lipton nicht vor ein paar Monaten einen Beitrag dazu geschrieben, als er über natürliche Beweise sprach? (Update): Hier ist der Link: rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs
Suresh Venkat
4
Es sind exponentielle Untergrenzen für monotone Schaltkreise bekannt (Razborov 85, Alon+Boppana 87).
Iddo Tzameret
2
Haben Raz und McKenzie nicht die gesamte monotone NC-Hierarchie getrennt? (R. Raz, P. McKenzie, "Trennung der monotonen NC-Hierarchie")
Michaël Cadilhac
1
Eine verwandte Frage: cstheory.stackexchange.com/questions/2291/…
Gil Kalai
7
((Verwenden Sie um kursiv zu schreiben; verwenden Sie kursiv !))meinth
Jeffs

Antworten:

15

Benjamin Rossmans jüngster Aufsatz fasst den Stand der Technik für die monotone Schaltungskomplexität von k-CLIQUE zusammen. Kurz gesagt, Razborov bewies 1985 eine Untergrenze, die später von Alon und Boppana 1987 verbessert wurde: gegenüber der Obergrenze der rohen Kraft O ( n k ) .ω(nk/(Logn)k)Ö(nk)

Rossman zeigt eine untere von gebundenen für den durchschnittlichen Fall Komplexität im Erdős Rényi-Modell von zufälligen Graphen; Amano zeigte zuvor, dass dies im Wesentlichen auch die Obergrenze war. Die Quasi-Sonnenblumen-Deckspelze, die einen wichtigen Teil des Papiers bildet, ist ziemlich ordentlich.ω(nk/4)

Die Barriere für natürliche Beweise scheint also nicht für die Komplexität von monotonen Schaltkreisen zu gelten.

Norbert Blum hat diskutiert, warum sich untere Schranken für monotone Schaltkreise wesentlich von Schaltkreisen mit Negationen unterscheiden. Die Schlüsselbeobachtung von Éva Tardos ist, dass eine kleine Modifikation der Lovász-Theta-Funktion eine exponentielle monotone Schaltungskomplexität aufweist.

András Salamon
quelle
1
Ich fand auch Karchmers "Über das Nachweisen der unteren Schranken für die Schaltkreisgröße" hilfreich, um zu verstehen, warum monotone Schaltkreise sich von Schaltkreisen mit Negation unterscheiden.
Kaveh
11

Dem Punkt wird eine allgemeine Boolesche Funktion gegeben, f es gibt eine monotone Boolesche Funktion g, so dass jede superlineare untere Schranke für g eine für f impliziert. Oder stärker ist die allgemeine Komplexität von f gleich der monotonen Komplexität von g bis zu O (n).

Ich bin mir immer noch nicht sicher, wie das mit den Barrieren zusammenhängt.

Dick Lipton
quelle
18
Willkommen bei der TCS SE !! Vielen Dank an Ihre Blog-Beiträge, es ist wirklich eine Freude zu lesen!
Hsien-Chih Chang 張顯 張顯