Algebraische Komplexitätstheorie III

Zur Berechnungskomplexität von Permanenten

Michael Clausen, Universität Bonn

Im dritten und letzten Teil unserer kleinen Vortragsreihe über algebraische Komplexitätstheorie ging es um ein algebraisches Analogon zur Theorie der NP-Vollständigkeit. Dieses Analogon geht auf Valiant [15, 17] zurück und entsprang seinen Studien von Zählproblemen [14]. Neben den offensichtlichen Querverbindungen zur Kombinatorik werden durch dieses Thema aber auch innerhalb der Komplexitätstheorie Brücken geschlagen: einerseits eine Brücke zur strukturellen Komplexitätstheorie, bei der es (etwa auf der Grundlage des Turingmaschinenmodells) um die Formulierung von Komplexitätsklassen und deren Beziehungen untereinander geht, andererseits eine Brücke zur parallelen Komplexitätstheorie.

Diese Vortragsausarbeitung beginnt mit einer Erinnerung an die Booleschen Komplexitätsklassen P und NP sowie an den Begriff der NP-Vollständigkeit. Danach werden die algebraischen Analoga VP und VNP einführt sowie der Begriff der VNP-Vollständigkeit vorgestellt. Während die Objekte im Booleschen Fall Sprachen sind, also Mengen von Wörtern endlicher Länge über einem endlichen Alphabet, sind die Objekte im algebraischen Fall gewisse unendliche Folgen multivariater Polynome über einem Körper k. Wichtige Rollen im algebraischen Analogon werden die Folgen DET = (DET_{n}) bzw. PER = (PER_{n}) der generischen Determinanten bzw. Permanenten spielen:

DET_{n} := ∑_{σ∈S_{n}} sgn(σ) ∏_{i=1}^{n} X_{iσ(i)} , PER_{n} := ∑_{σ∈S_{n}} ∏_{i=1}^{n} X_{iσ(i)}.

Wir werden die (erweiterte) Hypothese von Valiant diskutieren, aus deren Gültigkeit sich ergeben würde, daß es zwischen der Berechnungskomplexität von Determinanten und Permanenten trotz der Ähnlichkeit in der Definition krasse Unterschiede gibt. Obwohl viele Indizien für diese Hypothese sprechen, ist man von einem Beweis noch sehr weit entfernt.

1 Die Hypothesen von Cook und Valiant

In der ersten Hälfte dieses Jahrhunderts hat man die Frage nach dem prinzipiell Berechenbaren auf verschiedene, aber äquivalente Weise befriedigend formalisieren können durch Konzepte wie Turingmaschinen, Registermaschinen, While-Programme, rekursive Funktionen, Thue-Systeme und Markov-Algorithmen. Zu Beginn des Computer-Zeitalters trat dann naturgemäß die Frage in den Vordergrund: Welche Probleme sind in einem praktischen Sinne berechenbar?

Als erste Approximation der in einem praktischen Sinn berechenbaren Probleme sieht man die Komplexitätsklasse P an, die aus allen Sprachen A über einem Alphabet Σ besteht, die von einer deterministischen Turingmaschine in polynomialer Zeit akzeptiert werden. Das heißt, zu A gibt es eine deterministische Turingmaschine M und eine pbeschränkte Funktion^{1} f: ℕ → ℕ, so daß M angesetzt auf x ∈ Σ^{n} nach höchstens f(n) Schritten entschieden hat, ob x zu A gehört oder nicht; im ersten Fall gibt M eine 1, ansonsten eine 0 aus. M berechnet also die charakteristische Funktion χ_{A}: Σ^{∗} → {0, 1}, wobei Σ^{∗} := ∪_{n≥0}Σ^{n}.

Neben einer Vielzahl von effizient lösbaren Problemen traten in der Praxis vermehrt Probleme in den Vordergrund, die sich allen Anstregungen, sie effizient zu lösen, widersetzten. Viele derartige Probleme hatten aber eins gemeinsam: bekam man eine im Vergleich zur Eingabelänge kurze Lösung “verraten”, so hatte man es nicht schwer, diese Lösung als solche zu verifizieren. Beispiele derartiger Probleme sind das Erfüllbarkeitsproblem der Aussagenlogik, oder die Frage nach einem Hamiltonkreis in einem Graphen. Dies führte zur Definition der Komplexitätsklasse NP.

Definition 1 Eine Sprache A ⊆ Σ^{∗} gehört zu NP gdw. es eine p-beschränkte Funktion t: ℕ → ℕ sowie eine Sprache B ⊆ (Σ ⊔ {#})^{∗} aus P gibt, so daß

∀n ∈ ℕ ∀x ∈ Σ^{n} (x ∈ A ⇔ ∃e ∈ Σ^{t(n)} : x#e ∈ B).

Hat x ∈ A die Länge n und ist e ∈ Σ^{t(n)} mit x#e ∈ B, so ist e ein kurzer Zeuge für die Zugehörigkeit von x zu A und die Möglichkeit, x#e ∈ B in polynomialer Zeit zu entscheiden, kann man als effiziente Verifikation von x ∈ A ansehen. Die obige Äquivalenz kann man auch so umformulieren:

χ_{A}(x) = ⋁_{e∈Σ^{t(n)}} χ_{B}(x#e).

Nun kommen wir zu den algebraischen Komplexitätsklassen und leiten zunächst von den bisherigen Objekten, nämlich den Sprachen, über zu den algebraischen Objekten.

1Eine Funktion f: ℕ → ℕ heißt p-beschränkt, wenn sie von einer Polynomfunktion majorisiert wird.

Es sei A eine Sprache über dem Alphabet Σ = {0, 1}. Dieses A kann man ansehen als Folge von Indikatorfunktionen f_{n}, wobei f_{n}: {0, 1}^{n} → {0, 1} der Indikator von A ∩ Σ^{n} in Σ^{n} ist. Zu dieser Funktionenfolge gehört die Partition A = ⊔_{n≥0}(A ∩ Σ^{n}). Es wird für unsere Zwecke bequem sein, mit dem Parameter n etwas großzügiger umzugehen. Denken wir etwa an die Sprache A aller invertierbaren Matrizen über dem Körper 𝔽_{2} aus zwei Elementen, so ist diese in natürlicher Weise partitioniert als A = ⊔A_{n}, wobei A_{n} = GL(n, 2) ist. Demnach ist hier f_{n}: {0, 1}^{n^{2}} → {0, 1}. Da aber die Klasse der p-beschränkten Funktionen unter Komposition abgeschlossen ist, können wir uns diese Freiheit erlauben. Schließlich beachte man, daß jede n-stellige Boolesche Funktion sich repräsentieren läßt durch ein Polynom F_{n} ∈ 𝔽_{2}[X_{1}, …, X_{n}] von höchstens linearem Grad in jeder Variablen, insbesondere ist der Grad von F_{n} polynomial beschränkt in n, sogar deg F_{n} ≤ n.

Bevor wir zur Definition der Komplexitätsklasse VP kommen, legen wir noch zwei Bezeichnungsweisen fest. Für ein multivariates Polynom f über dem Körper k sei v(f) die Minimalzahl von Unbestimmten, von denen f abhängt, o.B.d.A. sei f ∈ k[X_{1}, …, X_{v(f)}]. (Manchmal werden wir auch andere Mengen zum Indizieren der Unbestimmten nehmen.) Im folgenden arbeiten wir der Einfachheit halber mit straight-line Programmen, bei denen nur addiert, multipliziert und skalarmultipliziert werden darf; die zum Kostenmaß c mit c(ω) = 1 für ω ∈ k∪{+, ∗} gehörige Komplexität eines multivariaten Polynoms f (modulo I = k ∪ {X_{1}, X_{2}, …}) bezeichnen wir mit L(f).

Definition 2 Es sei k ein Körper, X_{1}, X_{2}, … Unbestimmte über k.

• Eine Folge f = (f_{n})_{n≥1} multivariater Polynome über k heißt eine p-Familie gdw. die Funktionen n ↦ v(f_{n}) und n ↦ deg f_{n} beide p-beschränkt sind.

• Eine p-Familie f = (f_{n}) heißt p-berechenbar, gdw. n ↦ L(f_{n}) p-beschränkt ist.

• VP = VP(nonuniform; k) bezeichnet Valiants Klasse aller p-berechenbaren Familien über k.

Wir machen einige Anmerkungen zur Definition. Die Einschränkung auf p-Familien ist ein Gebot der Fairness. Dadurch wird der unerwünschte Effekt ausgeschaltet, daß durch zu schnell wachsenden Grad oder durch zu schnell wachsende Unbestimmtenanzahl gewisse Polynomfamilien “komplexer” erscheinen als sie in Wirklichkeit sind. Nichtuniform bedeutet hier etwa: die Mitglieder der Familie (f_{n}) müssen nicht notwendigerweise einheitlich durch eine Turingmaschine beschreibbar sein. Wir bemerken noch, daß wir dieselbe Komplexitätsklasse VP erhalten, wenn auch Divisionen zugelassen sind und alle Operationen gezählt werden. (Dies folgt aufgrund eines Satzes von Strassen [13].)

Beispiele. Folgende p-Familien liegen in VP:

• SUM := (SUM_{n})_{n≥1}, wobei SUM_{n} := X_{1} + … + X_{n}.

• PROD := (PROD_{n})_{n≥1}, wobei PROD_{n} := X_{1} ⋯ X_{n}.

• POWERSUM := (POWERSUM_{n}), wobei POWERSUM_{n} := ∑_{i=1}^{n} X_{i}^{n}.

• DET := (DET_{n}); dies folgt mittels Gaußelimination sowie der oben erwähnten Tatsache, daß Divisonen zugelassen werden können.

Wenn wir in χ_{A}(x) = ∨_{e∈{0,1}^{t(n)}}χ_{B}(x#e) die Disjunktion über e durch eine Summe über e ersetzen, kommen wir zu folgendem Analogon von NP.

Definition 3 • Eine p-Familie f = (f_{n}) von Polynomen über k heißt p-definierbar, gdw. es eine p-berechenbare Familie g = (g_{n}) ∈ VP gibt, so daß stets t(n) := v(g_{n})− v(f_{n}) ≥ 0 ist und f_{n}(X) = ∑_{e∈{0,1}^{t(n)}} g_{n}(X, e) gilt. (Wir treffen die Konvention X := (X_{1}, …, X_{v(f_{n})}) und setzen f_{n}(X) = g_{n}(X), falls t(n) = 0.)

• VNP = VNP(nonuniform; k) bezeichnet Valiants Klasse aller p-definierbaren Familien über k.

Offenbar ist P ⊆ NP und VP ⊆ VNP. Wir geben im folgenden eine p-Familie in VNP an, von der vermutet wird, daß sie nicht in VP liegt, wenn char k ≠ 2. (Im Fall der Charakteristik 2 ist DET = PER, also PER ∈ VP.)

Proposition 4 PER ∈ VNP.

Beweis. PER ist eine p-Familie, denn die Variablenanzahlfunktion n ↦ n^{2} und die Gradfunktion n ↦ n sind p-beschränkt. Als nächstes geben wir eine Familie g = (g_{n}) in VP an, wobei g_{n} = g_{n}(X, Y) ein Polynom in 2n^{2} Unbestimmten X_{ij} und Y_{ij} über k ist mit PER_{n} = ∑_{e∈{0,1}^{n×n}} g_{n}(X, e). Die Polynome g_{n} sind definiert durch

g_{n}(X, Y) := \underbrace{\underbrace{( ∏_{i=ℓ ⇔ j≠m}(1 − Y_{ij}Y_{ℓm}))}_{=:α_{n}(Y)} · \underbrace{(∏_{i=1}^{n} ∑_{j=1}^{n} Y_{ij})}_{=:β_{n}(Y)}}_{=:γ_{n}(Y)} · \underbrace{(∏_{i=1}^{n} ∑_{j=1}^{n} X_{ij}Y_{ij})}_{=:μ_{n}(X,Y)} .

Dann ist g = (g_{n}) ∈ VP, denn v(g_{n}) = 2n^{2}, deg g_{n} = O(n^{3}) und die Komplexität von g_{n} ist O(n^{3}). Weiter zeigt man leicht für alle e ∈ {0, 1}^{n×n}:

• α_{n}(e) ≠ 0 gdw. jede Zeile und jede Spalte von e höchstens eine Eins enthält.

• Sei α_{n}(e) ≠ 0. Dann ist β_{n}(e) ≠ 0 gdw. jede Zeile von e mindestens eine Eins enthält.

• γ_{n}(e) ≠ 0 gdw. e eine Permutationsmatrix ist.

• γ_{n}(e) ∈ {0, 1}.

• γ_{n}(e) ≠ 0 impliziert μ_{n}(X, e) = ∏_{i=1}^{n} X_{iσ(i)}, wobei σ die zu e gehörige Permutation bezeichnet.

• PER_{n} = ∑_{e∈{0,1}^{n×n}} g_{n}(X, e).

Dies beweist PER ∈ VNP.

In der strukturellen Komplexitätstheorie sieht das weitere Vorgehen typischerweise so aus: Mit geeigneten Reduktionsbegriffen partitioniert man die Komplexitätsklassen in Teilklassen von ungefähr gleich schwierigen Problemen. Nachdem das geschehen ist, ist man insbesondere interessiert an härtesten Problemen innerhalb der großen Komplexitätsklassen. Dies sind die sogenannten vollständigen Probleme. Die nachfolgende Definition präzisiert dies auf eine mögliche Art. (Es gibt auch andere Reduktionsbegriffe.)

Definition 5 Es seien A_{1} ⊆ Σ_{1}^{∗} und A_{2} ⊆ Σ_{2}^{∗} Sprachen.

• A_{1} heißt p-reduzierbar auf A_{2} (kurz: A_{1} ≤_{p} A_{2}) gdw. eine p-berechenbare Funktion f: Σ_{1}^{∗} → Σ_{2}^{∗} existiert, so daß für alle x ∈ Σ_{1}^{∗} gilt: x ∈ A_{1} ⇔ f(x) ∈ A_{2}.

• A_{1} und A_{2} heißen p-äquivalent gdw. A_{1} ≤_{p} A_{2} und A_{2} ≤_{p} A_{1}.

• A ⊆ Σ^{∗} heißt NP-vollständig gdw. A ∈ NP und B ≤_{p} A gilt, für alle B ∈ NP.

Die NP-vollständigen Probleme sind untereinander p-äquivalent und bilden gerade die härtesten “Brocken” in NP. Weiterhin gilt für ein beliebiges NP-vollständiges Problem A:

P = NP ⇔ A ∈ NP.

Cook [5] war der erste, der von einem natürlichen Problem nachweisen konnte, daß es NP-vollständig ist:

Satz 6 (Cook) Das Erfüllbarkeitsproblem der Aussagenlogik ist NP-vollständig.

Mittlerweile kennt man hunderte von NP-vollständigen Problemen, darunter viele sehr praxisrelevante wie etwa das Problem des Handlungsreisenden, oder das Problem der ganzzahligen linearen Optimierung, siehe z.B. [7, 12].

Jetzt kommen wir zu den entsprechenden Begriffen im algebraischen Kontext. (Beim Reduktionsbegriff sind wir in gewisser Weise restriktiver, was letztendlich aber zu stärkeren Aussagen führt.)

Definition 7 • f ∈ k[X_{1}, …, X_{n}] ist eine Projektion von g ∈ k[X_{1}, …, X_{m}] gdw. f = g(a_{1}, …, a_{m}) für geeignete a_{1}, …, a_{m} aus k ∪ {X_{1}, …, X_{n}}.

• f = (f_{n}) heißt eine p-Projektion von g = (g_{n}) (kurz: f ⪯_{p} g) gdw. eine pbeschränkte Funktion t existiert, so daß f_{n} eine Projektion von g_{t(n)} ist für alle n.

• Eine p-Familie g über k ist VNP-vollständig gdw. g in VNP liegt und jedes f aus VNP eine p-Projektion von g ist.

Offenbar sind VP und VNP abgeschlossen unter p-Projektionen. Der folgende Satz zeigt, daß die Permanentenfamilie zu den schwierigsten Familien in VNP gehört.

Satz 8 (Valiant) PER ist VNP-vollständig über jedem Körper der Charakteristik ungleich 2.

Valiant [15] hat weiterhin gezeigt, daß die Familie HC = (HC_{n}) der Hamiltonzykluspolynome vollständig über jedem Körper ist (siehe auch [8]). Um das Besondere an der Vollständigkeit der Permanentenfamilie herauszustellen, geben wir zunächst eine etwas andere Charakterisierung der Komplexitätsklasse NP. Es sei t: ℕ → ℕ eine p-beschränkte Funktion und R ⊂ Σ^{∗} × Σ^{∗} eine Relation mit der Eigenschaft, daß für (x, y) ∈ Σ^{n} × Σ^{m} aus R(x, y) stets m ≤ t(n) folgt. Weiterhin sei {x#y | R(x, y)} ∈ P. Dann nennt man {x | ∃y : R(x, y)} ein (p-beschränktes) Suchproblem und die Funktion, die jedem x die Binärkodierung der Anzahl aller y mit R(x, y) zuordnet, das zugehörige Zählproblem. Die Klasse NP besteht nun gerade aus allen Suchproblemen. Jedes L ∈ NP liefert ein Zählproblem #L und #P (lies: number P) bezeichnet die Klasse aller Zählprobleme, die von zählenden Turingmaschinen in Polynomialzeit berechnet werden können. Auch #P enthält vollständige Probleme bezüglich eines geeigneten Reduktionsbegriffs. Es konnte gezeigt werden, daß für viele NP-vollständige Probleme L das zugehörige Zählproblem #L seinerseits vollständig in #P ist, siehe z.B. Valiant [14] und Johnson [12]. Valiant [16] machte darüber hinaus die erstaunliche Entdeckung, daß es sogar Probleme in P gibt, deren zugehörige Zählprobleme #P-vollständig sind. Das eindrucksvollste Beispiel ist das Problem des perfekten Matchings in bipartiten Graphen, das nach M. Hall [10] in P liegt. Das zugehörige Zählproblem, das äquivalent zur Permanentenberechnung von 0-1 Matrizen ist, stellte sich als #P-vollständig heraus. Vor diesem Hintergrund sollte der obige Satz von Valiant gesehen werden.

Die Sätze von Cook und Valiant gaben Anlaß zur

Hypothese von Cook: P ≠ NP.
Hypothese von Valiant: VP ≠ VNP.

Wir werden im letzten Abschnitt eine verschärfte Version der Valiantschen Hypothese auf algebraisch-kombinatorische Weise formulieren, wodurch schnell klar werden wird, wie weit man noch von einem Beweis dieser Hypothese entfernt ist.

In den restlichen Abschnitten wird eine grobe Beweisskizze des Satzes von Valiant gegeben. Für Einzelheiten verweisen wir auf Kapitel 21 in [3].

2 p-Definierbarkeit und Formelgröße

Im ersten Beweisschritt wird eine alternative Charakterisierung der Valiantschen Komplexitätsklasse VNP mit Hilfe der Formelgröße gegeben.

Die Menge der arithmetischen Formeln (Ausdrücke) über I := k ∪ {X_{1}, …, X_{n}} ist induktiv wie folgt definiert: jedes Element in I ist eine Formel; sind φ_{1} und φ_{2} Formeln, so auch (φ_{1} ∘ φ_{2}), für ∘ ∈ {+, ∗}. Die Größe E(φ) einer Formel φ ist die Anzahl der + und ∗, die zu ihrem Aufbau benutzt wurden. Jede Formel φ stellt in naheliegenderweise ein eindeutig bestimmtes Polynom val(φ) ∈ k[X_{1}, …, X_{n}] dar. Die Formelgröße E(f) von f ∈ k[X_{1}, …, X_{n}] ist die kleinste Größe einer Formel φ mit val(φ) = f.

Jede Formel φ kann man durch einen Baum T_{φ} veranschaulichen. So stellt

[figure: ∗; +; +; ∗; 2; X_{1}; 3; X_{2}; X_{2}]

z.B. die Formel φ = (((2 + X_{1}) + (3 ∗ X_{2})) ∗ X_{2}) dar. Man beachte, daß eine Formel für das Polynom f als spezielles straight-line Programm angesehen werden kann, bei dem Zwischenresultate nur einmal wiederverwendet werden dürfen; insbesondere gilt

L(f) ≤ E(f).

Jedoch können L(f) und E(f) stark voneinander abweichen, was sich schon aus folgender Bemerkung ergibt:

∀ f ∈ k[X_{1}, …, X_{n}] \ {0} : E(f) ≥ deg(f) − 1.

Ist z.B. f = (f_{n}) mit f_{n} := X_{1}^{2^{n}}, so folgt L(f_{n}) = n, aber E(f_{n}) = 2^{n} − 1. Hier ist n ↦ L(f_{n}) p-beschränkt, wohingegen n ↦ E(f_{n}) exponentiell in n ist. Allerdings ist f keine p-Familie, da n ↦ deg f_{n} nicht p-beschränkt ist. Offen ist die Frage, ob ein solcher Unterschied innerhalb von VP möglich ist.

Definition 9 • Eine p-Familie g = (g_{n}) heißt p-ausdrückbar gdw. n ↦ E(g_{n}) pbeschränkt ist.

• VP_{e} = VP_{e}(nonuniform; k) bezeichnet Valiants Klasse aller p-ausdrückbaren Familien über k.

• VNP_{e} = VNP_{e}(nonuniform; k) bezeichnet Valiants Klasse aller Familien f = (f_{n}) über k so daß eine p-ausdrückbare Familie g existiert mit t(n) := v(g_{n}) − v(f_{n}) ≥ 0 und f_{n}(X) = ∑_{e∈{0,1}^{t(n)}} g_{n}(X, e).

Offenbar ist VP_{e} ⊆ VP ⊆ VNP und VNP_{e} ⊆ VNP. Eine weitere fundamentale Vermutung lautet:

VP_{e} ≠ VP.

Überraschenderweise stimmen die zugehörigen “nichtdeterministischen” Klassen überein:

Satz 10 (Valiant) VNP_{e} = VNP.

Einen Beweis findet man in Abschnitt 21.2 in [3].

3 Universalität von Determinante und Permanente

Im zweiten Beweisschritt wird gezeigt, daß jede p-ausdrückbare Polynomfamilie eine p-Projektion von DET und PER ist. Genauer gilt folgender Satz.

Satz 11 (Valiant) Hat f ∈ k[X_{1}, …, X_{n}] Formelgröße u, so ist f sowohl eine Projektion von DET_{2u+2} als auch eine Projektion von PER_{2u+2}.

Beweisskizze. (von zur Gathen) Wir beschränken uns hier auf DET ; ähnlich geht man bei PER vor. Es bezeichne E die Menge aller Formeln über I := k ∪ {X_{1}, …, X_{n}}. Man definiert entlang des Formelaufbaus eine Abbildung μ: E → ∪_{s≥1}I^{s×s} mit folgenden Eigenschaften für alle φ ∈ E:

(A) val(φ) = det(μ(φ)).

(B) Hat φ Formelgröße u, so ist die Matrix μ(φ) s-reihig, s = 2u + 2.

(C) Mit s = 2u + 2 aus (B) gibt es A ∈ I^{(s−1)×(s−1)}, α ∈ I^{1×(s−1)}, β ∈ I^{(s−1)×1}, so daß A obere Dreiecksmatrix ist mit Einsen auf der Hauptdiagonalen und

μ(φ) = ( \begin{matrix}α & 0 \\ A & β \end{matrix} ) .

(D) μ(φ) hat in jeder Spalte höchstens einen Eintrag, der nicht in k liegt. Die letzte Spalte enthält keine Unbestimmte.

Konstruktion von μ:

Fall 1. (u = 0) Sei φ ∈ I. Dann erfüllt μ(φ) := \binom{φ 0}{1 1} ∈ I^{2×2} die Bedingungen (A)–(D).

Fall 2. φ = (φ_{1} ∗ φ_{2}). Für i ∈ {1, 2} bezeichne u_{i} die Formelgröße von φ_{i}. Definiere μ(φ) wie folgt:

= 0^{1} ^{μ(φ_{2})}^{μ(φ_{1})} 0  0^{1}^{^{1}  ^{1} ^{0} ∗ ^{β_{1}}^{α_{1}}} 0^{^{1}  ^{1} ^{0} ∗ ^{β_{2}}^{α_{2}}}^{μ(φ) :=}

Dann gelten (C) und (D). Weiterhin ist u = u_{1} + u_{2} + 1 die Größe von φ und nach Induktion ist die Größe s von μ(φ) gleich (2u_{1} + 2) + (2u_{2} + 2) = 2u + 2, womit (B) bewiesen ist. Aus der Blockdreiecksgestalt von μ(φ) folgt auch leicht (A).

Fall 3. φ = (φ_{1} + φ_{2}). Wir wenden auf M_{1} := μ(φ_{1}) und M_{2} := μ(φ_{2}) das folgende Lemma an und erhalten det(M) = −det(M_{1}) − det(M_{2}) = −val(φ) für die dort konstruierte Matrix M. Wir bekommen μ(φ), indem wir zu M eine letzte Zeile und eine vorletzte Spalte hinzufügen, deren Einträge sämtlich Null sind mit Ausnahme der Kreuzungsstelle, an der eine Eins steht.

Lemma 12 Es sei R ein kommutativer Ring. Für i = 1, 2 sei A_{i} ∈ R^{d_{i}×d_{i}} eine obere Dreiecksmatrix mit Einsen auf der Diagonalen, α_{i} ∈ R^{1×d_{i}} und β_{i} ∈ R^{d_{i}×1}. Dann stehen die Determinanten und Permanenten der Matrizen

M_{1} := ( \begin{matrix}α_{1} & 0 \\ A_{1} & β_{1} \end{matrix} ) , M_{2} := ( \begin{matrix}α_{2} & 0 \\ A_{2} & β_{2} \end{matrix} ) , M := ( \begin{matrix}α_{1} & α_{2} & 0 \\ A_{1} & 0 & β_{1} \\ 0 & A_{2} & β_{2} \end{matrix} )

wie folgt in Beziehung:

det(M) = (−1)^{d_{2}}det(M_{1}) + (−1)^{d_{1}}det(M_{2})

und

per(M) = per(M_{1}) + per(M_{2}).

Der Beweis des Lemmas ergibt sich durch Laplace-Entwicklung nach der d_{1} +1-ten Spalte von M. Damit ist die Beweisskizze des Universalitätssatzes abgeschlossen. Valiant [15] zeigt mit einer kompakteren Konstruktion, daß im letzten Satz 2u + 2 sogar durch u + 3 ersetzt werden kann.

4 Die Vollständigkeit der Permanentenfamilie

Nach den bisherigen Vorbereitungen kommen wir jetzt zur Skizze des eigentlichen Vollständigkeitsbeweises. Wir wissen bereits, daß PER in VNP liegt. Es bleibt zu zeigen, daß jedes f ∈ VNP eine p-Projektion von PER ist. Wegen VNP = VNP_{e} gibt es zu jedem f ∈ VNP ein g ∈ VP_{e} mit f_{n}(X) = ∑_{e} g_{n}(X, e), für alle n. Sei m = v(f_{n}) und t = v(g_{n}) − v(f_{n}). Setze X = (X_{1}, …, X_{m}) und Y = (Y_{1}, …, Y_{t}) := (X_{m+1}, …, X_{m+t}). Aufgrund der Universalität der Permanente gibt es eine Matrix A über k∪{X_{1}, …, X_{m}}∪ {Y_{1}, …, Y_{t}} mit N = 2E(g_{n})+2 Reihen, für die g_{n}(X, Y) = per(A) ist. Weiter können wir nach Eigenschaft (D) im Universalitätsbeweis annehmen, daß A in jeder Spalte höchstens einen Eintrag hat, der eine Unbestimmte ist. Damit ergibt sich die VNP-Vollständigkeit von PER aus folgendem Resultat.

Satz 13 Es sei k ein Körper der Charakteristik ≠ 2 und A = A(X, Y) eine N × N Matrix über k∪{X_{1}, …, X_{m}, Y_{1}, …, Y_{t}}, in der pro Spalte höchstens ein Eintrag außerhalb k vorkommt. Dann läßt sich eine quadratische Matrix A′ über k ∪ {X_{1}, …, X_{m}} mit N′ ≤ 10N Zeilen angeben, so daß per(A′) = ∑_{e∈{0,1}^{t}} perA(X, e).

Beweisskizze. Die zu konstruierende Matrix A′ hat eine Block- und eine Feinstruktur. Blockeinträge ungleich einer Nullmatrix gibt es in A′ höchstens in der ersten Blockzeile, in der ersten Blockspalte, sowie auf der Blockdiagonalen. Das folgende Schaubild verdeutlicht die Blockstruktur für den Fall t = 2:

A′ = ( \begin{matrix}A_{0} & Y_{01} & Y_{02} \\ Y_{10} & Y_{1} & 0 \\ Y_{20} & 0 & Y_{2} \end{matrix} ) .

Dabei geht A_{0} aus A hervor, indem man alle Y_{i} durch 0 ersetzt. Bei der Feinstruktur spielt die Valiant-Matrix

V = ( \begin{matrix}0 & 1 & −1 & −1 \\ 1 & −1 & 1 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 1 & 3 & 0 \end{matrix} )

eine zentrale Rolle. Dies liegt an folgenden Eigenschaften (dabei bezeichne V [R|C] die Matrix V ohne die Zeilen r ∈ R und Spalten c ∈ C):

per(V) = per(V [1|1]) = per(V [4|4]) = per(V [1, 4|1, 4]) = 0

und

per(V [1|4]) = per(V [4|1]) = 4.

Wir erläutern die Feinstruktur von A′ anhand des Beispiels:

A = A(X_{1}, Y_{1}, Y_{2}) = ( \begin{matrix}Y_{1} & 2 & 3 & 4 & 5 \\ 6 & Y_{2} & X_{1} & 7 & 8 \\ 9 & 10 & 11 & Y_{1} & 12 \\ 13 & 14 & 15 & 16 & 17 \\ 18 & 19 & 20 & 21 & 22 \end{matrix} ) .

(Hier ist also m = 1 und t = 2.) Die zugehörige Matrix A′ sieht so aus (dabei ist ε_{1} = 4^{−4} und ε_{2} = 4^{−2}, was wegen der Voraussetzung char k ≠ 2 Sinn macht!):

ε^{2}  ε^{2} 1 1  1  1 ε_{1}  ε_{1} 1 1 1 1  1  1 1 1  18  21  19 13  16  14 9  1  10 6  7  1 1  4  2 1819202122 1314151617 9 1011 0 12 6 0X_{1}7 8 0 2 3 4 5 ^{0010 11 -1 1 311 -1 021 -1}^{0010 11 -1 1 311 -1 021 -1}^{0010 11 -1 1 311 -1 021 -1}^{0010 11 -1 1 311 -1 021 -1} ^{0010 11 -1 1 311 -1 021 -1}^{0010 11 -1 1 311 -1 021 -1}

Das Ergebnis per(A′) = ∑_{e∈{0,1}^{2}} perA(X_{1}, e_{1}, e_{2}) ergibt sich nun mittels einer verallgemeinerten Laplace-Entwicklung unter Verwendung der Blockstruktur der Matrix A′. Dabei steuert die Zeile mit den beiden ε_{1}’s die Summation e_{1} ∈ {0, 1}: das linke ε_{1} liefert den Beitrag zu “e_{1} = 1” das andere den zu “e_{1} = 0”. Entsprechendes gilt für die beiden ε_{2}’s.

Das mag an groben Hinweisen genügen. Einzelheiten findet man im Abschnitt 21.4 von [3].

5 Die erweiterte Valiantsche Hypothese

Wir wollen in diesem letzten Abschnitt die Valiantsche Hypothese verschärfen. Dazu arbeiten wir mit p-Familien, deren Formelgrößen bzw. Komplexitäten quasi-polynomial wachsen dürfen; das ist schneller als polynomial, aber weniger schnell als exponentiell.

Definition 14 • Eine Funktion t: ℕ → ℕ heißt quasi-polynomial beschränkt (qpbeschränkt), wenn es eine positive Konstante c gibt mit t(n) ≤ n^{O(log^{c} n)}.

• Eine p-Familie f = (f_{n}) über k heißt qp-berechenbar (bzw. qp-ausdrückbar) gdw. n ↦ L(f_{n}) (bzw. n ↦ E(f_{n})) qp-beschränkt ist.

• VQP = VQP(k; nonuniform) (bzw. VQP_{e} = VQP_{e}(k; nonuniform)) bezeichnet Valiants Klasse aller qp-berechenbaren (bzw. qp-ausdrückbaren) Familien über k.

Offenbar ist VP ⊆ VQP und VP_{e} ⊆ VQP_{e}. Die folgende Vermutung verallgemeinert die Hypothese VNP \ VP ≠ ∅.

Erweiterte Hypothese von Valiant: VNP \ VQP ≠ ∅ über jedem Körper.

Mit den folgenden Ausführungen soll skizziert werden, daß diese Vermutung äquivalent ist zur Aussage: VNP_{e} \VQP_{e} ≠ ∅ über einem beliebigen Körper. Da wir bereits wissen, daß VNP_{e} = VNP ist, genügt es, folgenden Satz zu zeigen.

Satz 15 VQP_{e} = VQP über einem beliebigen Körper.

Dieser Satz ergibt sich aus Zusammenhängen zwischen den verschiedenen Komplexitätsmaßen Formelgröße E(f), Komplexität L(f) und der Tiefe D(f) eines Polynoms f. Die Tiefe kann interpretiert werden als die die minimale parallele Berechnungszeit, und im folgenden präzisieren wir kurz diesen Begriff. Jedem straight-line Programm Γ = (Γ_{1}, …, Γ_{r}), das Eingaben der Länge n erwartet, kann man einen Digraphen zuordnen, dessen Knotenmenge {−n+1, …, r} ist. Eine Anweisung Γ_{i} = (ω_{i}; α, β) steuert zwei Kanten, nämlich (α, i) und (β, i) bei, während die Skalarmultiplikationsanweisung Γ_{i} = (ω_{i}; α) nur die Kante (α, i) beiträgt. Die Tiefe D(Γ) von Γ ist die maximale Länge eines Weges im gerade definierten Digraphen zu Γ. Die Tiefe (depth) des Polynoms f ist definiert durch

D(f) := min{D(Γ) | Γ berechnet f}.

Entsprechend definiert man die Tiefe T (φ) einer Formel φ und gelangt so zum Begriff der Formeltiefe T (f) von f:

T (f) := min{T (φ) | val(φ) = f}.

Es ist eine empfehlenswerte Übung zu zeigen, daß D(f) = T (f) ist. Während die untere Schranke des folgenden Satzes fast trivial ist (ebenfalls eine sinnvolle Übung!), ergibt sich die obere Schranke durch geschickte Anwendung des goldenen Schnitts; daher tritt dort auch die Zahl ϵ := (1 + \sqrt{5})/2 auf.

Satz 16 (Brent [2]) Für ein n-variates Polynom f vom Grad d ≥ 2 gilt:

log(E(f) + 1) ≤ D(f) ≤ \frac{2}{log ϵ} log(E(f)) + 1.

Die Tatsache, daß D = Θ(log E) ist, untermauert die Vermutung, daß VP_{e} ≠ VP gilt, denn VP_{e} = VP würde implizieren, daß für jedes f ∈ VP (insbesondere auch für f = DET ) eine Konstante c existiert mit D(f_{n}) ≤ c log n, für alle n. Das liegt aber jenseits unserer Vorstellungskraft.

In den Beweis von VQP_{e} = VQP geht schließlich noch das folgende fundamentale Resultat der parallelen Komplexitätstheorie ein, das auf Hyafil [11] sowie Valiant, Skyum, Berkowitz und Rackoff [18] zurückgeht.

Satz 17 Es gibt es eine universelle Konstante c, so daß für jedes n-variate Polynom f vom Grad d ≥ 1 über k gilt:

D(f) ≤ c(log(dL(f)) log d + log n).

Darüber hinaus kann f von einem straight-line Programm der Länge O(d^{6}L(f)^{3}) und Tiefe O(log(dL(f)) log d + log n) berechnet werden.

Aus den letzten beiden Sätzen ergibt sich nach leichter Rechnung die Gleichheit VQP = VQP_{e}.

Zum Vergleich von DET und PER diskutieren wir jetzt Vollständigkeitsresultate für VQP auf der Basis eines etwas großzügigeren Reduktionsbegriffs.

Definition 18 • Seien f = (f_{n}) und g = (g_{n}) p-Familien über k. Dann heißt f eine qp-Projektion von g gdw. es eine qp-beschränkte Funktion t gibt, so daß für jedes n das Polynom f_{n} eine Projektion von g_{t(n)} ist.

• Eine Familie g heißt VQP-vollständig gdw. g ∈ VQP und jedes f ∈ VQP eine qp-Projektion von g ist.

Offenbar ist VQP abgeschlossen unter qp-Projektionen.

Satz 19 DET ist VQP-vollständig.

Beweis. Wir wissen bereits, daß DET ∈ VP ⊆ VQP. Nun sei f ∈ VQP = VQP_{e}. Dann ist n ↦ E(f_{n}) qp-beschränkt und aufgrund der Universalität der Determinante ist f_{n} eine Projektion von DET_{2E(f_{n})+2}. Also ist f eine qp-Projektion von DET .

Nun kommen wir zu einem abschließenden Vergleich von DET und PER. Aufgrund von Satz 17 wissen wir, daß DET_{n} durch ein straight-line Programm polynomialer Länge und Tiefe O(log^{2} n) berechnet werden kann. (Für direkte Konstruktionen verweisen wir auf Csanky [6], Berkowitz [1] und Chistov [4].) Zusammen mit D = Θ(log E) (Satz von Brent) ergibt das

E(DET_{n}) = 2^{O(log^{2} n)}.

Im Vergleich dazu ergibt sich für die Permanente aus der Formel von Ryser nur die folgende obere Schranke:

E(PER_{n}) = O(n^{2}2^{n}).

Wegen Satz 8 und Satz 19 ist die erweiterte Valiantsche Hypothese (in Charakteristik ≠ 2) äquivalent zur folgenden rein algebraisch-kombinatorischen Aussage.

Erweiterte Hypothese von Valiant: PER ist keine qp-Projektion von DET .

Das bisher beste Resultat, was in diese Richtung geht, besagt folgendes:

Satz 20 (von zur Gathen [9]) PER_{n} ist keine Projektion von DET_{m}, falls m < \sqrt{2}n.

Zum Beweis der erweiterten Valiantschen Hypothese müßte dieses Resultat um astronomische Größenordungen verbessert werden! Vielleicht kann die Kombinatorik hier der Komplexitätstheorie weiterhelfen.

Literatur

[1] S. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Proc. Letters, 18:147–150, 1984.

[2] R.P. Brent. The complexity of multiprecision arithmetic. In Proc. Seminar on Compl. of Comp. Problem Solving. Brisbaine, 126–165, 1975.

[3] P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften, Bd. 315. Springer Verlag, 1996.

[4] A.L. Chistov. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. In Fundamentals of Computation Theory, number 199 in Lecture Notes in Computer Science, Springer-Verlag, 63–69, 1985.

[5] S.A. Cook. The complexity of theorem proving procedures. In Proc. 3rd ACM STOC, 151–158, 1971.

[6] L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comp., 5:618–623, [7] M.R. Garey und D.S. Johnson. Computers and intracrability: a guide to the theory

of NP-completeness. W.H. Freeman and Company, New York, 1979.

[8] J. von zur Gathen. Feasible arithmetic computations: Valiant’s hypothesis. J. Symb. Comput., 4:137–172, 1987.

[9] J. von zur Gathen. Permanent and determinant. Lin. Alg. Appl., 96:87–100, 1987.

[10] M. Hall. An algorithm for distinct representatives. Amer. Math. Monthly, 63:716– 717, 1956.

[11] L. Hyafil. On the parallel evaluation of multivariate polynomials. SIAM J. Comp., 8:120–123, 1979.

[12] D.S. Johnson. A catalog of complexity classes. In J. van Leeuwen (ed.): Handbook of Theoretical Computer Science, volume A, chapter 2, 61–161. Elsevier Science Publishers B. V., 1990.

[13] V. Strassen. Vermeidung von Divisionen. Crelles J. Reine Angew. Math., 264:184– 202, 1973.

[14] L.G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comp., 8:410–421, 1979.

[15] L.G. Valiant. Completeness classes in algebra. In Proc. 11th ACM STOC, 249–261, 1979.

[16] L.G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sc., 8:189–201, 1979.

[17] L.G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic: an International Symposium held in Honor of Ernst Specker, volume 30, pp. 365–380, 1982.

[18] L.G. Valiant, S. Skyum, S. Berkowitz und C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comp., 12(4):641–644, 1983.