Eine Frage zu GCT

In der Arbeit 'Über das Verschwinden der Kronecker-Koeffizienten' hier in http://arxiv.org/pdf/1507.02955v1.pdf wird gezeigt, dass es im Allgemeinen schwierig ist, die Positivität der Kronecker-Koeffizienten zu bestimmen. Es gibt jedoch eine Einschränkung, die besagt, dass in der GCT nur die Positivität der 'rechteckigen Kronecker-Koeffizienten' benötigt wird . Was bedeutet GCT, wenn dies auch NP-schwer wird?

Eine verwandte Frage ist, welche Konsequenzen dies für die GCT hat, wenn es keine allgemeine positive Formel gibt, die einer für den Sonderfall der LR-Koeffizienten ähnelt.

Selbst wenn die Entscheidung über die Positivität der Kronecker-Koeffizienten NP-schwer ist oder wenn es keine allgemeine positive Formel für sie gibt, ist es für GCT durchaus möglich, "zu arbeiten". Selbst unter der vorhergehenden Annahme ist es immer noch möglich, dass es für einige der rechteckigen Kronecker-Koeffizienten eine positive Formel (und sogar ein Entscheidungsverfahren für die Polynomzeit) gibt . Wenn man eine solche Formel finden und dann zeigen könnte, dass die entsprechenden irreduziblen Darstellungen mit einer Multiplizität ungleich Null im Koordinatenring des Orbitverschlusses einer Permanentgröße geeigneter Größe erscheinen, würde dies immer noch die (starke) permanente versus determinante Vermutung beweisen.

Update 30.08.15 : Ich sollte hinzufügen, dass der geometrische Ansatz zur Komplexität, wie in der GCT, unabhängig von positiven kombinatorischen Formeln ein sehr nützlicher Weg ist, um die Struktur von Komplexitätsklassen zu verstehen und die Darstellungstheorie dort zu verwenden, wo dies natürlich der Fall ist entsteht (wie hier) ist immer eine gute idee. Landsbergs Arbeit auf diesem Gebiet ist in dieser Richtung bemerkenswert (dh unter Verwendung geometrischer Techniken in Kombination mit Darstellungstheorie, auch ohne positive kombinatorische Formeln). [Update beenden]

[Nun zurück zu positiven kombinatorischen Formeln ...] Auch wenn immer mehr Kronecker-Koeffizienten NP-schwer zu entscheiden sind, ob sie verschwinden, oder wenn es für sie keine positive kombinatorische Formel gibt, (a) ist es einfach ein Testament wie schwer diese Probleme sind (während GCT die bekannten Barrieren umgeht, zielt es immer noch darauf ab, einige sehr harte offene Probleme zu beweisen) und / oder (b) schlägt vor, wo man seinen Fokus einschränken muss, um GCT zu erreichen Arbeit (zB wie oben).

Auch wenn die NP-Härte im Allgemeinen eine "schlechte Nachricht" ist, ist sie nicht unbedingt das Ende der Straße. Obwohl der Hamilton-Zyklus NP-hart ist, gibt es zum Beispiel immer noch viele Theoreme und theoretisches Verständnis für Hamilton-Zyklen. Die NP-Härte lässt nur einen (oder zumindest mich) erwarten, dass es niemals eine "vollständige Theorie der Hamilton-Zyklen" geben wird. Eine solche "vollständige Theorie der Kronecker-Koeffizienten" braucht man jedoch nicht, um eine Untergrenze über GCT zu beweisen - man braucht nur eine Familie von Darstellungen, die beim Umlaufbahnschluss der Determinante verschwindet, aber nicht beim Umlaufbahnschluss der Permanente.

(Diese Antwort gilt auch für das kürzlich erschienene Papier von Kahle und Michalek, das zeigt, dass es Familien von Plethysmenmultiplizitäten gibt, die nicht durch die Anzahl der ganzzahligen Punkte in einer natürlichen Familie von Polytopen gegeben sind.)