Loading…
Geometric complexity theory and orbit closures of homogeneous forms
Hüttenhain, Jesko
Valiant's Conjecture is the algebraic version of P vs. NP and serves as our central motivation. The first part of the thesis starts out by giving an introduction to the underlying theory. In the second chapter, we define a complexity measure for integer polynomials which can be seen as a discretization of the original theory and can be studied combinatorically. A different approach to Valiant's conjecture is the Geometric Complexity Theory programme (GCT for short) which was introduced in 2001 by Mulmuley and Sohoni. Chapter 3 serves as an introduction to GCT: Here, the separation of complexity classes is reduced to the existence of certain integer vectors, which we also call obstructions. The final chapter of the first part shows that certain obstructions are in some sense rare and only recently, it was confirmed that these obstructions are insufficient to prove Valiant's conjecture via GCT.
In the second part of the thesis, we study the central geometric object of GCT in more detail and generality: Given the action of a general linear group on a space of homogeneous polynomials by variable substitution, we are interested in the closure of certain orbits, in particular the orbit of the determinant polynomial. Before we study the determinant, we first analyze the case where the orbit closure contains only polynomials that arise by variable substitution, possibly by a non-invertible transformation. A complete classification of this case remains open, but we can answer and pose serveral questions to advance it. In Chapter 7, we introduce techniques to classify the boundary of orbit closures in the general case. We can successfully give a description for the 3×3 determinant polynomial and under one remaining assumption, also for the general binomial. We also determine the stabilizer group of the determinant of a generic traceless matrix and can conclude that the orbit closure of this polynomial is always an irreducible component of the boundary of the orbit closure of the determinant.
Die Vermutung von Valiant ist eine algebraische Version des P vs. NP Problems aus der theoretischen Informatik und unsere zentrale Motivation. Im ersten Teil der Arbeit wird daher zunächst die zugrundeliegende Theorie von Valiant zusammengefasst. Im zweiten Kapitel wird ein Komplexitätsmaß für ganzzahlige Polynome definiert, welches die ursprüngliche Theorie noch stärker diskretisiert und sich rein kombinatorisch untersuchen lässt. Ein anderer Ansatz zur Lösung der Vermutung von Valiant ist die Geometrische Komplexitätstheorie, welche 2001 von Mulmuley und Sohoni ins Leben gerufen wurde: Kapitel 3 der Arbeit liefert eine Einführung. Die Trennung von Komplexitätsklassen wird hier auf die Existenz gewisser ganzzahliger Vektoren mit kombinatorischen Eigenschaften reduziert: Diese Vektoren nennen wir auch Obstruktionen. Im letzten Kapitel des ersten Teils wird gezeigt, dass diese Obstruktionen in einem gewissen Sinne selten sind: Erst kürzlich wurde auch bewiesen, dass diese Obstruktionen tatsächlich nicht ausreichen, um Valiant's Vermutung zu beweisen.
Valiant's Conjecture is the algebraic version of P vs. NP and serves as our central motivation. The first part of the thesis begins with an introduction to the underlying theory.
Der zweite Teil der Arbeit beschäftigt sich näher und in größerer Allgemeinheit mit dem zentralen Konzept der Geometrischen Komplexitätstheorie: Wir betrachten die Wirkung der allgemeinen linearen Gruppe auf einem Raum homogener Polynome durch Variablensubstitution und studieren den topologischen Abschluss bestimmter Bahnen dieser Wirkung. Zunächst wird der Fall studiert, dass jedes Element in diesem Abschluss durch Variablensubstitution entsteht, möglicherweise mittels einer nicht invertierbaren Transformation. Eine vollständige Klassifikation aller Polynome mit dieser Eigenschaft bleibt offen, obwohl wir einige Fragen im Hinblick darauf beantworten können. Es werden weiterhin Techniken vorgestellt, um den Rand eines Bahnabschlusses auch im Allgemeinen zu klassifizieren. Dies gelingt uns für den Fall der 3×3 Determinante und unter einer verbleibenden Annahme auch für das allgemeine Binom. Wir bestimmen hier auch den Stabilisator der Determinante einer allgemeinen, spurlosen Matrix und können schlussfolgern, dass der Bahnabschluss dieses Polynoms stets eine irreduzible Komponente im Rand des Bahnabschlusses der allgemeinen Determinante ist. Der Determinante gilt hier besondere Aufmerksamkeit aufgrund ihrer wichtigen Rolle in der algebraischen Komplexitätstheorie.
