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?
cc.complexity-theory
lower-bounds
circuit-complexity
boolean-functions
Marcin Kotowski
quelle
quelle
Antworten:
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.
quelle
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 ...!
quelle