Durchschnittliche Komplexität gruppentheoretischer Probleme

Thorsten Camps

27. Mai 2003

1 Einleitung

Die generische Komplexität eines Problems (hier: Wort- oder Zugehörigkeitsproblem) betrachtet die Laufzeit eines Algorithmus nur für die Menge der am häufigsten auftretenden Eingaben. Die restlichen, meist schwierigen, da kompliziert zu berechnenden Eingaben, werden außen vor gelassen. Für die ”allermeisten“ Fälle ist sie also eine ausreichende Beschreibung. Möchte man bei der Komplexitätsbetrachtung nun alle Fälle in Betracht ziehen, kann dies zu einer deutlichen Erhöhung der Komplexität führen, im Extremfall sogar zur (durchschnittlichen) Unentscheidbarkeit, wenn für eine gewisse Menge von Wörtern das Problem zum Beispiel unlösbar ist. Im folgenden wird untersucht, wie sich durchschnittl. und generische Komplexität zueinander verhalten. Als Ergebnis erhält man die Gleichheit, wenn man für die ”kleine“ Menge der bei der generischen Komplexität nicht betrachteten Wörter eine Obergrenze für die Komplexität hat. Der technische Ansatz sieht folgendermaßen aus: Es sei M′ ein partieller Algorithmus, der das Problem mit generischer Komplexität in C löst. Anschaulich bedeutet dies, dass das Problem für die ”meisten“ Wörter mit dieser Komplexität entscheidbar ist und für die restlichen Wörter, eine sehr kleine und daher in der Praxis (hoffentlich) unbedeutende Teilmenge, in einer anderen Komplexität oder sogar gar nicht entscheidbar ist. Weiter sei M′′ ein Algorithmus, der für alle Wörter das Problem löst. Um das betrachtete Problem für die ganze Wortmenge zu lösen, setzt man M′ und M′′ zu einem Algorithmus M := M′ ∥ M′′ zusammen, in dem man sie parallel laufen lässt. Die Frage ist nun, welche Auswirkungen die Komplexität von M′ auf die durchschnittl. Komplexität des Problems hat. Bis einschl. der Proposition in Kapitel 4 ist von den gruppentheoretischen Entscheidungsproblemen noch nicht viel zu sehen. Alle Ergebnisse sind verallgemeinert für Algorithmen, die mit einer Sprache D arbeiten, der wiederum ein Alphabet X zugrunde liegt. Nach der allgemeinen Betrachtung wird das gewonnene Ergebnis auf das Wort- und das Zugehörigkeitsproblem in Gruppen übertragen. Doch zunächst noch einmal das Wichtigste in Kürze.

2 Wiederholung (Generische Komplexität)

Zum Nachschauen hier noch einmal die wichtigsten Definitionen betreffend die generische Komplexität eines Algorithmus. Die Definition von der generischen Performance unterscheidet sich ein wenig von der Definition im Vortrag von Guntram Hainke, ist aber nur eine andere Formulierung.

2.1 Definition (Asymptotische Dichte)

Sei X ein endliches Alphabet mit mindestens zwei Elementen. X^{∗} bezeichne die Menge aller Wörter in X. Sei weiter S ⊂ X^{∗} eine Teilmenge von X^{∗}. Für jedes n > 0 bezeichne B_{n} die Menge aller Wörter in X^{∗} mit einer Länge von höchstens n. Die asymptotische Dichte ρ(S) von S in X^{∗} ist definiert als

ρ(S) := lim sup_{n→∞} ρ_{n}(S), wobei ρ_{n}(S) := \frac{|S ∩ B_{n}|}{|B_{n}|} ist.

Wenn der eigentliche Grenzwert existiert, setzen wir ρ̂(S) := ρ(S).

2.2 Definition (Exponentielle Konvergenz)

Eine positive Nullfolge (a_{n}) heißt exponentiell konvergent, wenn es ein 0 ≤ σ < 1 und ein C > 0 gibt, so dass für jedes n ≥ 1 gilt: a_{n} ≤ Cσ^{n}.

Entsprechend heißt eine Folge (b_{n}) mit lim_{n→∞} b_{n} = b und 0 ≤ b_{n} ≤ b exponentiell konvergent, wenn die Folge (b − b_{n}) exponentiell gegen 0 konvergiert.

2.3 Definition (Generische Performance eines partiellen Algorithmus)

Sei X ein endliches Alphabet mit mindestens zwei Elementen und D ⊂ X^{∗} eine Sprache in X. Ω sei ein korrekter partieller Algorithmus, der entscheidet, ob ein Wort w ∈ X^{∗} zu D gehört. Sei weiter C eine Komplexitätsklasse.

Wir sagen, Ω löst D mit generischer Komplexität in C, wenn es eine Teilmenge S ⊂ X^{∗} mit ρ̂(S) = 1 gibt, so dass der Algorithmus Ω für jedes w ∈ S mit einer Komplexität in C entscheidet, ob w ∈ D ist.

Gilt zusätzlich lim_{n→∞} ρ_{n}(S) = 1 exponentiell, dann löst Ω D mit generischer Komplexität stark in C.

2.4 Folgerung

Mit den Bezeichnungen aus der vorangehenden Definition und K := X^{∗} \ S gilt:

lim_{n→∞} ρ_{n}(S) = 1 exponentiell ⇒ lim_{n→∞} ρ_{n}(K) = 0 exponentiell
⇒ \frac{|K ∩ B_{n}|}{|B_{n}|} ≤ C · q^{n} für ein C > 0 und ein q ∈ [0, k[ .

Beweis: Sei |X| = k, dann gilt:

|B_{n}| = ∑_{i=1}^{n} k^{i} = \frac{k^{n+1} − 1}{k − 1}.

Damit folgt:

\frac{|K ∩ B_{n}|}{|B_{n}|} + \frac{|S ∩ B_{n}|}{|B_{n}|} = 1
⇒ \frac{|K ∩ B_{n}|}{|B_{n}|} = 1 − \frac{|S ∩ B_{n}|}{|B_{n}|}
⇒ \frac{|K ∩ B_{n}|}{|B_{n}|} ≤ C · σ^{n} für ein σ ∈ [0, 1[  (∗)
⇒ |K ∩ B_{n}| ≤ C · σ^{n} · \frac{k^{n+1} − 1}{k − 1}
≤ C · σ^{n} · k^{n+1}
≤ C′ · q^{n} für ein q ∈ [0, k[  (∗∗).

Dabei ist C′ := C · k und q := σ · k. Die Behauptungen folgen dann aus (∗) bzw. (∗∗).

□

Diese Folgerung wird in der Proposition 4.1 benutzt.

3 Vorbereitung

3.1 Definition (Diskretes Wahrscheinlichkeitsmaß)

Sei X ein endliches Alphabet mit |X| ≥ 2 Elementen. Eine Abbildung

μ : X^{∗} → [0, 1]

mit der Eigenschaft, dass ∑_{w∈X^{∗}} μ(w) = 1, heißt diskretes Wahrscheinlichkeitsmaß. Gilt μ(w) = μ (w′) für alle w, w′ ∈ X^{∗} mit |w| = |w′|, so heißt μ längeninvariant.

Längeninvarianz des W.-Maßes ist im Zusammenhang mit dem Wortproblem eine übliche Annahme. Sie besagt, dass alle Wörter mit einer festen Länge n gleich wahrscheinlich auftreten.

3.2 Konventionen

• Ein Algorithmus sei immer eine deterministische Mehrband-Turingmaschine

• C sei eine Komplexitätsklasse. Die Laufzeit für Entscheidungsprobleme aus C sei beschränkt durch eine Menge von Funktionen f(n) mit der Eigenschaft, dass für jedes C ∈ ℕ auch Cf (Cn + C) + C in dieser Menge liegt.

3.3 Definition (Subexponentielle Funktionen) und Bemerkung

Eine nicht-negative Funktion f(n) heißt subexponentiell, wenn für jedes r > 1 gilt:

lim_{n→∞} \frac{f(n)}{r^{n}} = 0.

Damit gilt für alle r > 1 und 1 < r′ < r:

∑_{n=1}^{∞} \frac{f(n)}{r^{n}} = ∑_{n=1}^{∞} \underbrace{\frac{f(n)}{(r′)^{n}}}_{≤c} · (\frac{r′}{r} )^{n} ≤ c · \frac{1}{1 − \frac{r′}{r}} < ∞

3.4 Definition (Durchschn. Komplexität)

Sei X ein Alphabet mit |X| ≥ 2 Elementen. Sei D ⊂ X^{∗} eine Sprache und M ein (totaler) Algorithmus, der für jedes Wort w ∈ X^{∗} in endlicher Zeit T (w) entscheidet, ob w ∈ D. Seien weiter f(n) eine monoton wachsende positive Funktion und μ ein diskretes Wahrscheinlichkeitsmaß auf X^{∗}.

1. Wir sagen, M löst D mit durch f(n) begrenzter durchschnittlicher Zeitkomplexität relativ zu μ, wenn gilt:

∫_{X^{∗}} \frac{T (w)}{f(|w|)} μ(w) = ∑_{w∈X^{∗}} \frac{T (w)}{f (|w|)} μ(w) < ∞.

Gehört f(n) zu einer bestimmten Komplexitätsklasse C, so löst M D in durchschnittlicher Zeitkomplexität in C relativ zu μ.

2. Sei ℜ eine Familie aus den diskreten W.-Maßen auf X^{∗}. Wir sagen, M löst D mit durch f(n) begrenzter Zeitkomplexität einheitlich relativ zu ℜ, wenn es ein 0 < C < ∞ gibt, so dass für jedes μ ∈ ℜ gilt:

∫_{X^{∗}} \frac{T (w)}{f(|w|)} μ(w) = ∑_{w∈X^{∗}} \frac{T (w)}{f(|w|)} μ(w) ≤ C.

Gehört f(n) zu einer bestimmten Komplexitätsklasse C, so löst M D in durchschnittlicher Zeitkomplexität in C einheitlich relativ zu ℜ.

Während im ersten Teil der Definition die Zeitkomplexität vom Algorithmus M und vom W.-Maß μ abhängt, entkoppelt die einheitliche Relativität die Zeitkomplexität (in gewissem Grad) von der Wahl des Wahrscheinlichkeitsmaßes. Die obere Schranke C gilt für alle W.- Maße μ ∈ ℜ. Die zweite Definition ist somit die weitergehende, der stärkere Annahmen zugrunde liegen. Im folgenden wird die Familie ℜ meist die Familie der längeninvarianten W.-Maße sein.

Interpretation

Interpretiere

∑_{w∈X^{∗}} T (w) μ(w)

als Erwartungswert für die benötigte Zeit bzw. als durchschnittliche Zeitkomplexität. Wenn die Gewichtung mit einer geeigneten Funktion \frac{1}{f(n)} den Erwartungswert endlich macht, dann nennt man das Problem D lösbar mit Komplexität von f(n). Diesen Zusammenhang macht folgende Überlegung deutlich:

3.5 Bemerkung

Angenommen, M löst D mit Komplexität begrenzt durch f(n) relativ zu μ. Dann gilt:

∑_{w∈X^{∗}} \frac{T (w)}{f(|w|)} μ(w) = ∑_{n=0}^{∞} ∑_{{w∈X^{∗} \atop |w|=n}} \frac{T (w)μ(w)}{f(|w|)} < ∞.

Daher gilt:

sup_{n≥0} \frac{∑_{w∈X^{∗}, |w|=n} T (w)μ(w)}{f(|w|)} < ∞,

und es ist

∑_{{w∈X^{∗} \atop |w|=n}} T (w)μ(w) = O(f(n)).

3.6 Konvention

Im folgenden bezeichne SUBEX P die Klasse der in subexponentieller Zeit entscheidbaren Sprachen, d.h. es gibt ein subexponentielles f, so dass die Definition 3.4 erfüllt ist.

4 Die durchschnittl. Komplexität des Wortproblems

Notwendig für die Beweise der zentralen Sätze ist die folgende

4.1 Proposition

Es seien X ein endliches Alphabet mit mindestens zwei Elementen und D ⊂ X^{∗}. Angenommen, D ist entscheidbar in einer Zeit f(n) und stark generisch entscheidbar in Zeit f_{1}(n) ≤ f(n), wobei die Funktion \frac{f(n)}{f_{1}(n)} subexponential sei. Dann ist die Sprache D entscheidbar mit einer durch f_{1}(n) beschränkten durchschnittl. Komplexität einheitlich relativ zur Familie aller längeninvarianten W.-Maße auf X^{∗}.

\underline{Beweis}: Seien M′ ein Algorithmus, der D in einer Zeit von f(n) löst, und M′′ ein partieller Algorithmus, der D stark generisch in Zeit f_{1}(n) löst. M sei definiert als der Algorithmus, der M′ und M′′ parallel laufen lässt. Sei weiter μ ein längeninvariantes W.-Maß auf X^{∗}. Definiere k := |X| ≥ 2. Sei nun B_{n} die Menge aller Wörter in X^{∗} mit Länge von höchstens n. Also gilt:

|B_{n}| = ∑_{i=0}^{n} k^{i} = \frac{k^{n+1} − 1}{k − 1}.

Sei S ⊂ X^{∗}, so dass der Algorithmus M′′ für jedes w ∈ S in Zeit von f_{1}(|w|) terminiert und lim_{n→∞} \frac{|S∩B_{n}|}{|B_{n}|} = 1 exponentiell.

Sei K := X^{∗} − S. Dann gibt es nach Folgerung 2.4 ein C > 0 und 1 ≤ q < k, so dass für jedes n ≥ 1 gilt: |K ∩ B_{n}| ≤ Cq^{n}. Für jedes w ∈ X^{∗} bezeichne T (w) die Zeit, die der Algorithmus M benötigt, um das Wort w zu entscheiden. Es gilt also:

T (w) ≤ \{ \begin{matrix}f_{1}(|w|) & für w ∈ S, \\ f(|w|) & für w ∈ X^{∗}. \end{matrix}

Da μ längeninvariant ist, gibt es eine Funktion d(n) ≥ 0, so dass

∑_{n=0}^{∞} d(n) = 1,

und für w ∈ X^{∗} mit |w| = n gilt: μ(w) = \frac{d(n)}{k^{n}}. Insbesondere gilt d(n) ≤ 1 für alle n. Insgesamt erhalten wir:

∫_{X^{∗}} \frac{T (w)}{f_{1}(|w|)} μ(w) = ∫_{S} \frac{T (w)}{f_{1}(|w|)} μ(w) + ∫_{K} \frac{T (w)}{f_{1}(|w|)} μ(w).

Weiter ist

∫_{S} \frac{T (w)}{f_{1}(|w|)} μ(w) ≤ ∫_{S} \frac{f_{1}(w)}{f_{1}(|w|)} μ(w) = μ(S) ≤ 1.

Für die Abschätzung des Integrals über K betrachtet man Wörter der Länge n. Dann ist

T (w) ≤ f(n) und μ(w) = d(n)\frac{1}{k^{n}} .

Damit ist die Funktion \frac{f(|w|)}{f_{1}(|w|)} d(|w|) ≤ \frac{f(n)}{f_{1}(n)}, wobei \frac{f(n)}{f_{1}(n)} subexponential ist.

Bezeichne nun noch K_{n} die Menge aller Wörter aus K der Länge n. Dann gilt:

|K_{n}| ≤ |K ∩ B_{n}| ≤ Cq^{n}.

Also:

∫_{K} \frac{T (w)}{f_{1}(|w|)} μ(w) = ∑_{n=0}^{∞} ∑_{w∈K_{n}} \frac{T (w)}{f_{1}(|w|)} μ(w)

≤ ∑_{n=0}^{∞} ∑_{w∈K_{n}} \frac{f(n)}{f_{1}(n)} d(n)\frac{1}{k^{n}}

≤ C ∑_{n=0}^{∞} \frac{f(n)}{f_{1}(n)}d(n)\frac{q^{n}}{k^{n}}

≤ C ∑_{n=0}^{∞} \frac{f(n)}{f_{1}(n)} \frac{q^{n}}{k^{n}}
=^{(∗)} C_{0},

Die Abschätzung (∗) folgt mit der Bemerkung in 3.3, da \frac{f(n)}{f_{1}(n)} subexponential und \frac{k^{n}}{q^{n}} > 1 ist. Dies ergibt insgesamt:

∫_{X^{∗}} \frac{T (w)}{f_{1}(|w|)} μ(w) = ∫_{S} \frac{T (w)}{f_{1}(|w|)} μ(w) + ∫_{K} \frac{T (w)}{f_{1}(|w|)} μ(w) ≤ 1 + C_{0} < ∞.

Da C_{0} nicht von μ abhängt, ist die Behauptung vollständig bewiesen.

□

Um es einmal explizit festzuhalten: Ist ein Problem stark generisch lösbar mit Komplexität von f_{1}(n) und existiert ein totaler Algorithmus mit Komplexität f(n), die nicht ”zu groß“ ist, dann ist die Menge K der nicht mit dem partiellen Algorithmus entscheidbaren Wörter klein genug und beeinflusst die Komplexität des zusammengesetzten Algorithmus nicht. Insgesamt wird eine durchschnittl. Komplexität von f_{1}(n) erreicht, die der generischen Komplexität entspricht. Nun ist das wichtigste Hilfsmittel vorhanden, um die Hauptsätze des Artikels zu beweisen. Zunächst das Wortproblem für endlich präsentierte Gruppen.

Satz A

Sei G eine endlich präsentierte Gruppe, in der das Wortproblem aus SUBEX P ist. Weiter besitze G eine nicht-amenable Quotientengruppe \overline{G}, in der das Wortproblem lösbar ist mit Komplexität C ⊂ SUBEX P. Dann ist das Wortproblem W P (G, A) für G lösbar mit durchschnittlicher Zeitkomplexität in C einheitlich relativ zur Familie aller längeninvarianten W.-Maße μ auf (A ∪ A^{−1})^{∗}

\underline{Beweis}: Da \overline{G} nicht amenabel ist, ist das Wortproblem W P (G, A) für G nach [2] (vgl. Vortrag Guntram Hainke und [3]) stark generisch lösbar mit Komplexität C, und zwar für jeden Erzeuger A. Aus Proposition 4.1 folgt dann die Aussage.

□

Mit anderen Worten: Die Komplexität des Wortproblems der gesamten Gruppe G ist die gleiche wie die Komplexität auf der Quotientengruppe.

Korollar B

Sei G eine endlich präsentierte Gruppe, in der das Wortproblem in subexponentieller Zeit lösbar ist. Sei weiter A Erzeuger von G und X := A ∪ A^{−1}. ℜ sei die Familie aller längeninvarianten diskreten W.-Maße auf X^{∗}. Dann gilt:

1. Angenommen, G besitzt eine nichtelementare, worthyperbolische Quotientengruppe. Dann ist das Wortproblem W P (G, A) ⊂ X^{∗} lösbar mit durchschnittl. linearer Zeitkomplexität einheitlich relativ zu ℜ.

2. Angenommen, G besitzt eine nicht-amenable automatische Quotientengruppe. Dann ist das Wortproblem W P (G, A) ⊂ X^{∗} lösbar mit durchschnittl. quadratischer Zeitkomplexität einheitlich relativ zu ℜ.

\underline{Beweis}: Jede nicht-elementare hyperbolische Gruppe enthält eine freie Untergruppe vom Rang zwei und ist daher nicht-amenabel. Aus der Literatur ist bekannt, dass das Wortproblem in hyperbolischen Gruppen in linearer Zeit lösbar ist und in automatischen Gruppen in quadratischer Zeit. Die Behauptung von Korollar B folgt nun aus Satz A.

□

4.2 Beispiel

Sei B_{n} die Zopfgruppe mit n Strängen. In [2] zeigen die Autoren, dass das Wortproblem in B_{n} für n ≥ 3 streng generisch (also für die ”meisten“ Elemente von B_{n}) in linearer Zeit lösbar ist. Für die gesamte Gruppe ist das Wortproblem in quadratischer Zeit lösbar, da B_{n} automatisch ist. Damit ergibt sich nach Satz und Korollar im Durchschnitt eine lineare Komplexität.

Und nun das Zugehörigkeitsproblem:

Satz C

Sei G eine endlich präsentierte Gruppe und H < G eine Untergruppe mit unendlichem Index, so dass das Zugehörigkeitsproblem für H in G in SUBEX P lösbar ist. Sei weiter ϕ : G → \overline{G} ein Epimorphismus. Angenommen, es gibt eine Untergruppe ϕ(H) < K < \overline{G}, so dass der Schreier-Nebenklassen-Graph für \overline{G} über K nicht-amenabel und das Zugehörigkeitsproblem für K in \overline{G} lösbar ist mit Komplexität C ⊂ SUBEX P . Dann ist das Zugehörigkeitsproblem MP (G, H, A) für jeden endlichen Erzeuger A von G lösbar mit durchschnittl. Komplexität C einheitlich relativ zur Familie aller längeninvarianten diskreten W.-Maße μ : (A ∪ A^{−1})^{∗} → [0, 1].

\underline{Beweis:} Da der Schreier-Nebenklassen-Graph von \overline{G} über \overline{H} nicht-amenabel ist, folgt aus [2] (s.a. Vortrag Frank Reidegeld und [4]), dass für jeden endlichen Erzeuger das Zugehörigkeitsproblem MP (G, H, A) streng generisch mit Komplexität C lösbar ist. Die Behauptung folgt nun aus Proposition 4.1. □

Korollar D

Sei G eine endlich präsentierte Gruppe und H < G eine Untergruppe, in der das Zugehörigkeitsproblem für H in G in subexponentieller Zeit lösbar ist. Sei G_{1} < G eine Untergruppe mit endlichem Index in G mit H < G_{1}. Seien weiter ϕ : G_{1} → \overline{G} ein Epimorphismus und weiter ϕ(H) < K < \overline{G}.

1. Angenommen, \overline{G} ist nicht-elementar und worthyperbolisch, sowie K < \overline{G} eine rationale Untergruppe von unendlichem Index. Dann ist für jeden endlichen Erzeuger A von G das Zugehörigkeitsproblem MP (G, H, A) für H in G durchschnittl. in linearer Zeit lösbar einheitlich relativ zur Familie aller längeninvarianten diskreten W.-Maße μ : (A ∪ A^{−1})^{∗} → [0, 1].

2. Sei \overline{G} automatisch und K < \overline{G} eine rationale Untergruppe, so dass der Schreier-Nebenklassen-Graph für \overline{G} über K nicht-amenabel ist. Dann ist für jeden endlichen Erzeuger A von G das Zugehörigkeitsproblem MP (G, H, A) für H in G lösbar in quadratischer Zeit einheitlich relativ zur Familie aller längeninvarianten diskreten W.-Maße μ : (A ∪ A^{−1})^{∗} → [0, 1].

\underline{Beweis}: Das Zugehörigkeitsproblem für eine rationale Untergruppe einer hyperbolischen Gruppe ist lösbar in linearer Zeit. Für eine rationale Untergruppe einer automatischen Gruppe ist es lösbar in quadratischer Zeit. Da nicht-elementare, hyperbolische Gruppen nicht-amenabel sind, folgen die Behauptungen aus Satz C. □

Literatur

[1] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain: Average-Case Complexity and Decision Problems in Group Theory, Preprint, 2002

[2] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain: Generic-Case Complexity and Decision Problems in Group Theory, Preprint, 2002

[3] Guntram Hainke: Generische Komplexität gruppentheoretischer Entscheidungsprobleme I: Das Wortproblem, Seminararbeit und Vortrag zu [2], 2003

[4] Frank Reidegeld: Generische Komplexität gruppentheoretischer Entscheidungsprobleme II: Das Zugehörigkeitsproblem, Seminararbeit und Vortrag zu [2], 2003