Komplexität des Coset-Schnittpunktproblems

17

Wenn die Symmetriegruppe und zwei Untergruppen G , H S n und π S n gegeben sind , gilt G π H = ?SnG,HSnπSnGπH=

Soweit ich weiß, ist das Problem als Coset-Schnittpunkt-Problem bekannt. Ich frage mich, was ist die Komplexität? Ist dieses Problem insbesondere bei coAM bekannt?

Wenn auf abelsch beschränkt ist, wie groß wird dann die Komplexität?H

maomao
quelle
2
Wie werden die beiden Gruppen als Eingabe dargestellt?
Emil Jeřábek unterstützt Monica
1
Konventionell sind sie durch Generatorsätze gegeben.
Maomao
1
Das Problem der Coset-Schnittmenge ist in der Regel umgekehrt formuliert: Die Antwort lautet Ja, wenn sie sich überschneiden. Es ist diese Version des Problems, die in . NPcoAM
Joshua Grochow
Eine interessante Randnotiz, die nichts von alledem zunichte macht: Graphisomorphismus, Coset-Schnittmenge und String-Isomorphismus waren Gegenstand eines neuen Ergebnisses, das Babai vor einigen Tagen erstmals in einem Seminar beschrieben hat. Noch keine Veröffentlichung, aber es scheint, als gäbe es jetzt für alle einen quasi-polynomialen Algorithmus.
Perry,

Antworten:

11

Mäßig exponentielle Zeit und (für das Gegenteil des angegebenen Problems gilt: Die Coset-Schnittmenge wird normalerweise als mit "Ja" beantwortet, wenn sich die Cosets überschneiden, im Gegensatz zur Angabe in der OQ.)coAM

Luks 1999 ( freie Autorenkopie ) gab einen -Zeit-Algorithmus an, während Babai (siehe seine Dissertation von 1983, auch Babai-Kantor-Luks FOCS 1983 , und eine erscheinende Zeitschriftenversion) eine 2 gab ˜ O ( 2O(n)-Zeitalgorithmus, der bis heute der bekannteste bleibt. Da Graphisomorphie zu quadratischem großen coset Schnitt reduziert, verbessertdies zu2 ~ O (n 1 / 4 - ε )würde den Stand der Technik für Graphisomorphie verbessern.2O~(n)2O~(n1/4ϵ)

Joshua Grochow
quelle
9

Betrachten wir die Ergänzung, also dort , wo Sie zu Test gefragt werden , ob . Wie ich in darauf hingewiesen , diese Antwort , Testen , ob g & egr ; g 1 , ... , g k heißt in NC P [1]. Sie können also g , h S n erraten und in polynomialer Zeit testen, ob g G , h H und g π = h sind . Dies ergibt einen NPGπHgg1,,gkNCPg,hSngGhHgπ=hNPObere Schranke und daher liegt Ihr Problem in .coNP

Edit : Es wird in [2, Thm. 15] , dass das coset Kreuzungsproblem ist in . Wie hier angemerkt , p. In 7 ist das Coset-Schnittproblem daher nicht NP-vollständig, es sei denn, die Polynomzeithierarchie bricht zusammen. Im Übrigen wird hier vermerkt , p. 6, dass es von Luks gezeigt wurde, dass das Problem in P liegt, wenn H lösbar ist, was den Fall von H abelian einschließt .NPcoAMPHH

[1]  L. Babai, EM Luks & amp; A. Seress. Permutationsgruppen in NC . Proc. 19. jährliches ACM-Symposium über Computertheorie, S. 409-420, 1987.

[2] L. Babai, S. Moran. Arthur-Merlin-Spiele: Ein randomisiertes Beweissystem und eine Hierarchie von Komplexitätsklassen . Journal of Computer and System Sciences, vol. 36, Heft 2, S. 254-276, 1988.

Michael Blondin
quelle
vielen dank für die antwort. Für den Fall, dass H eine normale Untergruppe ist, ist dies klar. Wenn H jedoch nur abelisch ist, ist es für mich nicht wirklich klar. Gilt noch? (Entschuldigung für meine Dummheit ...)GH=<st:sS,tT>
Maomao
Mein schlechtes Gehirn mischte für einen Moment "normal" und "lösbar". Es tut mir Leid. Ich habe die Antwort bearbeitet und hoffe, sie beantwortet Ihre Frage.
Michael Blondin
1
Wenn H eine normale Untergruppe von G ist, ist das Coset-Schnittpunktproblem viel einfacher: Es reduziert sich nur auf das Zugehörigkeitsproblem (ist in G). π
Joshua Grochow
Richtig, danke. Dieser Teil meiner Antwort ist dann ziemlich wertlos.
Michael Blondin
Ich habe den Absatz entfernt, es war nur verwirrend.
Michael Blondin