Kohomologischer Ansatz zur booleschen Komplexität

33

Vor einigen Jahren gab es eine Arbeit von Joel Friedman, die sich mit den unteren Schaltkreisgrenzen der Grothendieck-Kohomologie befasste (siehe Artikel: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024) ). Hat diese Denkrichtung neue Einsichten in die boolesche Komplexität gebracht oder bleibt sie eher eine mathematische Neugierde?

Marcin Kotowski
quelle
4
Ich bin sehr gespannt auf die Antwort darauf.
Suresh Venkat

Antworten:

28

Ich habe vor ungefähr 3 Jahren mit Joel Friedman über dieses Thema korrespondiert. Zu der Zeit sagte er, dass sein Ansatz zu keinen signifikanten neuen Einsichten in die Komplexitätstheorie geführt habe, obwohl er es immer noch für vielversprechend hielt.

Grundsätzlich versucht Friedman, die Probleme der Schaltungskomplexität in der Sprache der Garben auf einer Grothendieck-Topologie umzuformulieren. Die Hoffnung ist, dass dieser Prozess es ermöglicht, geometrische Intuition auf das Problem des Auffindens von Schaltkreisuntergrenzen anzuwenden. Es lohnt sich zwar zu prüfen, ob dieser Weg irgendwohin führt, aber es gibt heuristische Gründe, skeptisch zu sein. Geometrische Intuition funktioniert am besten im Kontext von glatten Sorten oder Dingen, die glatten Sorten so ähnlich sind, dass die Intuition nicht vollständig zusammenbricht. Mit anderen Worten, Sie benötigen eine gewisse Struktur , damit die geometrische Intuition Fuß fasst. Aber Schaltkreisuntergrenzen müssen von Natur aus mit willkürlichen Berechnungen konfrontiert werden, die schwer genau zu analysieren sind, weil sie so strukturlos zu sein scheinen. Friedman räumt von vornherein ein, dass die von ihm betrachteten Grothendieck-Topologien hochgradig kombinatorisch und weit entfernt von den üblichen Untersuchungsobjekten der algebraischen Geometrie sind.

Als Randbemerkung würde ich sagen, dass es wichtig ist, sich nicht zu sehr auf eine Idee zu freuen, nur weil sie ungewohnte, leistungsstarke Maschinen verwendet. Die Maschinerie kann die Probleme, für die sie entwickelt wurde, sehr effektiv lösen, aber um ein bekanntes schweres Problem in einem anderen Bereich angreifen zu können, muss es überzeugende Argumente geben, warum die fremde Maschinerie gut dafür geeignet ist, das Grundlegende zu lösen Hindernis in dem interessierenden Problem.

Timothy Chow
quelle
4
Natürlich sind Mulmuleys Bemühungen "ähnlich" im Sinne von "glatten Strukturen", aber er sucht nach Problemen, die zunächst nette geometrische Invarianten zulassen.
Suresh Venkat
2
@Suresh: Sie haben Recht, dass der Mulmuley-Sohoni-Ansatz anders ist, aber das grundlegende Problem der Bewältigung einer willkürlichen Berechnung lauert immer noch im Hintergrund. Man kann sich also fragen, wie man damit zurechtkommt. Im Moment glaube ich nicht, dass es jemand wirklich weiß, weshalb die GCT-Leute keine spektakulären Durchbrüche in naher Zukunft versprechen.
Timothy Chow
tatsächlich. Es ist interessant zu sehen, dass ein STOC 2011-Artikel GCT für Matrixmultiplikationsgrenzen verwendet (und Ketan hatte dieses Ergebnis in seinem Tutorial bei FOCS erwähnt)
Suresh Venkat
1
@Suresh: Wenn Sie über das Buergisser / Ikenmeyer-Papier sprechen, sagt es meiner Meinung nach viel mehr über die Grenzen des GCT-Ansatzes aus als darüber, wie man untere Schranken beweist.
5501
1
@Neel, ich habe keine Antwort, aber ich frage mich, ob dies eine eigene Frage verdient.
Suresh Venkat
16

Ich denke Timothy Chow hat es genau richtig. Ich habe meine eigene persönliche Wäscheliste mit Ideen für "glatte" Sorten oder Konzepten wie das Zählen verbundener Komponenten oder Monome, die zu den untersten Sprossen der "Kohomologieleiter" gehören. Variationen der Mayr-Meyer-Konstruktion, die die EXPSPACE-Vollständigkeit verschiedener Probleme im Zusammenhang mit GCT zeigen. Mein einziges Riff in seinem letzten Absatz ist, dass ich denke, dass eine Art leistungsstarker Maschinen benötigt wird ...!

Kenneth W. Regan
quelle