Polynomial Methoden , sagen Combinatorial Nullstellensatz und Chevalley-Warnung Satz leistungsfähige Werkzeuge in Additiv Kombinatorik sind. Indem sie ein Problem mit geeigneten Polynomen darstellen, können sie die Existenz einer Lösung oder die Anzahl der Lösungen für die Polynome garantieren. Sie wurden verwendet, um Probleme wie eingeschränkte Summenmengen oder Nullsummenprobleme zu lösen , und einige der Sätze in diesem Bereich können nur mit solchen Methoden bewiesen werden.
Für mich ist die nicht-konstruktive Art dieser Methoden wirklich erstaunlich, und ich bin gespannt, wie wir diese Methoden anwenden können, um interessante Einschlüsse und Trennungen von Komplexitätsklassen zu beweisen (auch wenn das Ergebnis mit anderen Methoden gelöst werden kann).
Gibt es Komplexitätsergebnisse, die man mit polynomiellen Methoden nachweisen kann?
quelle
Es gibt das Ergebnis von Zeev Dvir über das endliche Kakeya-Problem , das zuvor auf dieser Website erwähnt wurde. Zeev verwendete die Polynommethode, um die Anzahl der Punkte in einer beliebigen Menge von Punkten in F ^ n (F endliches Feld, n natürliche Zahl), die eine Linie in jede Richtung enthält, nach unten zu begrenzen. Dieses Ergebnis hat die Aufmerksamkeit der analysierenden Personen auf die Polynommethode gelenkt.
Zeevs Ergebnis war durch die Aufgabe motiviert, Zufallsextraktoren zu konstruieren . Dies ist Teil einer großen Anstrengung in der theoretischen Informatik, Algorithmen zu derandomisieren und letztendlich zu zeigen, dass P = BPP und ähnliche Komplexitätsergebnisse gelten.
Weitere Informationen finden Sie in Zeevs Umfrage: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf
quelle