Es gibt eine Reihe von Problemen in der kombinatorischen Darstellungstheorie und der algebraischen Geometrie, für die keine positive Formel bekannt ist. Es gibt mehrere Beispiele, an die ich denke, aber lassen Sie mich die Berechnung der Kronecker-Koeffizienten als mein Beispiel nehmen. Normalerweise ist der Begriff "positive Formel" in der Kombinatorik nicht genau definiert, aber er bedeutet grob "eine Beschreibung als die Kardinalität einer scheinbar ziemlich expliziten Menge". Vor kurzem habe ich mit Jonah Blasiak gesprochen und er hat mich überzeugt, dass die richtige Definition von "positiver Formel" #P ist . Ich gehe davon aus, dass ich auf dieser Site kein #P definieren muss.
Bürgisser und Ikenmeyer zeigen, dass die Kronecker-Koeffizienten #P hart sind. (Sie sind auch immer positiv, weil sie Tensorproduktmultiplizitäten sind.) Aber ich bin mir ziemlich sicher, dass niemand einen Weg kennt, sie zu berechnen, der sie sogar in #P bringt.
Nehmen wir also an, ich würde tatsächlich versuchen, zu beweisen, dass die Kronecker-Koeffizienten nicht in #P enthalten sind. Ich gehe davon aus, dass ich eine komplexitätstheoretische Vermutung anstellen und dann das Kronecker-Produkt auf ein anderes Problem reduzieren würde, das für eine Klasse größer als #P als vollständig bekannt ist.
Welche Vermutung könnte ich annehmen und auf welches Problem könnte ich versuchen, es zu reduzieren?
ADDED: Wie in den Kommentaren ausgeführt, zeigen Buergisser und Ikenmeyer, dass die Kronecker-Koeffizienten in Gap-P liegen, was ziemlich nahe an #P liegt. Die Fragen, die ich stellen sollte, lauten also: (1) Was sind einige Gap-P-vollständige Probleme, auf die ich plausibel reduzieren könnte, und (2) welche Aussichten bestehen darauf, zu zeigen, dass Gap-P kein #P ist? Ich denke (2) sollte sich in zwei Teile aufteilen (2a) glauben Experten, dass diese Klassen unterschiedlich sind? und (2b) gibt es wahrscheinliche Strategien, um dies zu beweisen?
Ich hoffe, dass diese Bearbeitung der Frage nicht verpönt ist.
quelle
Antworten:
Ich würde vorschlagen, Eigenschaften von #P-Funktionen zu betrachten, die sich von Gap-P-Funktionen unterscheiden. Zum Beispiel ist das Bestimmen, ob eine #P-Funktion Null ist, in co-NP. Wenn Sie zeigen könnten, dass die Bestimmung, ob der Kronecker-Koeffizient Null ist, UP-schwer ist, dann hätten Sie "Kronecker-Koeffizienten in #P implizieren UP in co-NP", eine unwahrscheinliche Schlussfolgerung.
quelle
GapP ist genau das Schließen von #P unter Subtraktion. Andererseits wird #P nicht unter Subtraktion geschlossen, es sei denn, UP = PP. Ich glaube, das beantwortet deine Fragen.
quelle
Die Frage der Berechnung von Zeichen irreduzibler Darstellungen der symmetrischen Gruppe könnte ein natürlicher Kandidat sein.
Ich denke, Charles Hepler zeigt, dass Gap-P vollständig ist, aber ich bin mir nicht sicher: Einen Link zu seiner Masterarbeit finden Sie unter https://dspace.ucalgary.ca/handle/1880/45530?mode=full
quelle