Wie kann ich zeigen, dass ein Gap-P-Problem außerhalb von #P liegt?

14

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.

David E Speyer
quelle
5
Willkommen bei cstheory! (Ich habe der Frage Zählkomplexität und Untergrenzen hinzugefügt ).
Kaveh
3
@Kaveh Bürgisser und Ikenmeyer zeigen, dass die Berechnung der Kronecker-Koeffizienten in GapP erfolgt. David, sind Kronecker-Koeffizienten immer nicht negative ganze Zahlen?
Tyson Williams
2
Ja. Sie sind Multiplikiten von Tensorprodukten, daher sind sie immer nicht negativ.
David E Speyer
1
Sie haben ein Problem mit GapP und möchten beweisen, dass es außerhalb von #P liegt. Ein offensichtlicher Ansatz besteht darin, zu zeigen, dass das Problem unter funktioneller (Levin) Reduzierbarkeit GapP-vollständig ist, was impliziert, dass das Problem außerhalb von #P liegt, wenn # P # GapP angenommen wird.
Tsuyoshi Ito
1
Was ich in meinem vorherigen Kommentar geschrieben habe, ist falsch, weil jedes Problem in GapP funktionell auf #P reduziert werden kann (wenn ich mich diesmal nicht irre). Mit anderen Worten, der Unterschied zwischen #P und GapP ist zu heikel, um mit funktionaler Reduzierbarkeit umgegangen zu werden.
Tsuyoshi Ito

Antworten:

12

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.

Lance Fortnow
quelle
3

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.

Tayfun Pay
quelle
4
Wenn Sie es
Tayfun Pay
3
Genau. Soweit ich sagen kann, gibt die Antwort zwei richtige Aussagen und beantwortet die ursprüngliche Frage (obwohl meine Suche ergab, dass UP = PH die gewünschte Bedingung ist?)
Suresh Venkat
2
@ Suresh: Wie beantwortet dieser Beitrag die ursprüngliche Frage? Die Frage bezieht sich nicht auf ein GapP-vollständiges Problem.
Tsuyoshi Ito
3
Teil (2) des Updates fragt: "Was sind die Aussichten, dass GapP nicht gleich #P ist". In dieser Antwort wird darauf hingewiesen, dass #P nicht durch Subtraktion geschlossen wird, es sei denn, es kommt zu einem Kollaps.
Suresh Venkat
1
@ Suresh: Dies ist das Papier. M. Ogiwara & L. Hemachandra. "Eine Komplexitätstheorie für mögliche Verschlusseigenschaften." Journal of Computer and System Sciences, Band 46, Seiten 295-325. 1993.
Tayfun Pay
0

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

Hari
quelle