Was ist der effizienteste Algorithmus, um zu entscheiden, ob sich ein Element am wenigsten in seiner Umlaufbahn befindet?

Wenn eine Gruppe auf eine Menge mit einer Gesamtordnung und einem einwirkt , was ist der effizienteste Algorithmus, um zu entscheiden, ob x das kleinste Element in seiner Umlaufbahn ist oder nicht, mit anderen Worten, um zu entscheiden, ob ? $G$ $X$ $\leq$ $x\in X$ $min(Gx) = x$

Meine Motivation liegt in der SMT-Lösung, bei der ein gewisses Interesse daran bestand, Symmetrien automatisch zu brechen. Das Hinzufügen von Prädikaten, die die Symmetrie brechen, führt häufig zu einer großen Klauselmenge, daher bin ich an der Möglichkeit interessiert, dies als träge Theoriepropagation zu behandeln.

Die obige Beschreibung ist vielleicht zu allgemein und, wie von Sid bemerkt , NP-hart. Eine mögliche einfachere Aufgabe besteht darin, eine Gruppe von Permutationen von Strings der Länge , die als eine Menge von Generatoren und einem String der Länge codiert sind . Was ist der effizienteste Algorithmus, um zu entscheiden, ob diese Zeichenfolge die lexikografisch kleinste in ihrer Umlaufbahn ist? $n$ $x$ $n$

ds.algorithms gr.group-theory HaskellElephant
quelle

Ich nehme an, Sie sprechen von endlichen Mengen X? Ich denke, dies zu entscheiden ist NP-schwer. Sei

eine Tour durch eine Reihe von Städten im Travelling Salesman-Problem mit

. Die Gruppe

sei die symmetrische Gruppe

. Dann ist die Umlaufbahn alle möglichen Touren und der Nachweis, dass eine von ihnen minimal ist, ist NP-schwer.

X = {c_{1}, \dots, c_{n}}

$X=\{c_1,\dots,c_n\}$

c_{1} \to c_{2} \dots

$c_1 \rightarrow c_2 \dots$

G

$G$

S_{n}

$S_n$

Opt

@Sid, ja, ich interessiere mich nur für den Fall, dass X endlich ist, und ich hatte nicht daran gedacht, aber es ist sicherlich NP-schwer. Ich denke, es könnte immer noch die Möglichkeit eines effizienten Monte-Carlo-Algorithmus geben.

HaskellElephant

Wenn Sie jedoch ein anderes Kriterium für das Minimum verwenden, ist es hier polynomisch: Es ist einfach, die lexikografisch kleinste Tour zu finden (zumindest wenn Sie davon ausgehen, dass alle Kanten unterschiedliche Bezeichnungen haben; ansonsten ist es immer noch NP-hart).

Peter Shor

@PeterShor, ja, tatsächlich reicht für meinen Zweck jede kanonische Form aus.

HaskellElephant

Wenn

und

als Wertorakel dargestellt werden, muss

aufgezählt werden .

G

$G$

X

$X$

G

$G$

David Harris

Antworten:

Für allgemeine Äquivalenzbeziehungen, nicht für solche, die sich aus Permutationsgruppenaktionen ergeben, ist es immer noch "zu" allgemein, selbst lexikographisch am wenigsten zu finden. Das Finden des lexikographisch kleinsten Elements in einer Äquivalenzklasse kann -hard sein (tatsächlich -hard) - selbst wenn die Beziehung eine kanonische Form für die Polynomzeit hat [1]. $NP$ $P^{NP}$

Bei Problemen mit der Umlaufbahn der Permutationsgruppe, wie Sie sie beschreiben, ist es jedoch unwahrscheinlich, dass die Entscheidung, ob zwei Punkte in derselben Umlaufbahn liegen, -hart ist: Sie ist in und daher nicht -hard, es sei denn, die Die Polynomhierarchie wird auf die zweite Ebene reduziert. $NP$ $NP \cap coAM$ $NP$

$2^{\tilde{O}(\sqrt{n})}$

$P$ $P$ $NP = UP = RP$ $BPP$ $P$ Dieses Ergebnis deutet jedoch darauf hin, dass selbst wenn es in einer höheren Komplexitätsklasse liegt, andere schwierige Probleme Ihnen möglicherweise im Weg stehen.

Ich denke, wenn Sie bessere Obergrenzen wollen, brauchen Sie das Problem wirklich, um genauer zu sein.

[1] Andreas Blass und Yuri Gurevich. Äquivalenzbeziehungen, Invarianten und Normalformen . SIAM J. Comput. 13: 4 (1984), 24-42.

[2] László Babai und Eugene M. Luks. Kanonische Beschriftungen von Graphen . STOC 1983, 171-183.

[3] Lance Fortnow und Joshua A. Grochow. Komplexitätsklassen von Äquivalenzproblemen überarbeitet . Informieren. und Comput. 209: 4 (2011), 748 & ndash; 763. Auch als arXiv erhältlich: 0907.4775v2 .

Joshua Grochow
quelle

P E q = C F

$PEq=CF$

Soweit ich weiß, nicht. Bestenfalls würde dies bedeuten, dass jedes Problem des kombinatorischen Isomorphismus in Ker (FP) liegt; Ein Problem ist, dass eine kanonische Form für einen Graphen keine kanonische Form für die Struktur ergeben muss, mit der Sie begonnen haben. Das andere Problem ist, dass der kombinatorische Isomorphismus nicht unbedingt PEq-vollständig ist. Wir fragten, ob es PEq-vollständige Probleme gab; Finkelstein und Hescott zeigten CEq-vollständige Probleme für C höher in der PH, ließen jedoch die Frage nach der Existenz eines PEq-vollständigen Problems offen.

Joshua Grochow

Wäre es möglich, dass das Vorhandensein eines vollständigen Problems in PEq impliziert, dass PH bis zu einem gewissen Grad zusammenbricht?

T ....

@ Turbo: Sicher, obwohl es mir ein wenig unwahrscheinlich erscheint. Kennen Sie ein Beispiel, bei dem das Vorhandensein eines vollständigen Problems für eine Klasse impliziert, dass PH zusammenbricht? (Abgesehen von PH-vollständigen Problemen.) Ich denke, es ist wahrscheinlich, dass entweder (a) PEq-vollständige Probleme existieren (und nicht den Hauptvermutungen widersprechen), wir haben einfach nicht herausgefunden, wie man sie konstruiert, oder (b) dort Gehen Orakel in beide Richtungen, wenn es um PEq-vollständige Probleme geht? (b) scheint mir - analog zu BPP - wahrscheinlicher zu sein, da PEq im Wesentlichen eine semantische Klasse ist.

Joshua Grochow