\documentclass[12pt,twoside]{article}

\usepackage{amssymb}
\usepackage[german]{babel}
\usepackage{epic}
\usepackage{latexsym}
\usepackage{bezier}

\pagestyle{myheadings}
\markboth{}{{\sc S\'eminaire Lotharingien de Combinatoire} {\rm S36c (16pp.)}}
\newtheorem{theorem}{Satz}
\newtheorem{corollary}[theorem]{Korollar}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}

%\input macros21.tex
 
\parindent=0pt
\parskip=1em
\setlength{\textwidth}{14cm}

%\pagestyle{empty}
\addtolength{\oddsidemargin}{-1cm}
\addtolength{\evensidemargin}{-1cm}
\addtolength{\textwidth}{2cm}
%\addtolength{\topmargin}{-2cm}
\addtolength{\textheight}{2cm}
\def\EuScript{\mathcal}
\def\C{{\Bbb C}}
\def\R{{\Bbb R}}
\def\F{{\Bbb F}}
\def\N{{\Bbb N}}
\def\P{{\mathbf{P}}}
\def\VP{{\mathbf{VP}}}
\def\NP{{\mathbf{NP}}}
\def\VNP{{\mathbf{VNP}}}
\def\VQP{{\mathbf{VQP}}}
\def\NC{{\mathbf{NC}}}
\def\VNC{{\mathbf{VNC}}}
\def\PER{{\mathit{PER}}}
\def\per{{\mathrm{per}}}
\def\DET{{\mathit{DET}}}
\def\HC{{\mathit{HC}}}
\def\det{{\mathrm{det}}}
\def\iff{{\Leftrightarrow}}
\def\val{{\mathrm{val}}}
\def\EX{{\mathcal{E}}}



\begin{document}
\phantom{...}
\vspace{.2cm}
\begin{center}
{\Large\bf Algebraische Komplexit\"atstheorie III}
\end{center}

\begin{center}
{\Large\bf Zur Berechnungskomplexit\"at\\ von Permanenten}
\end{center}
\begin{center}
{\sc Michael Clausen, Universit\"at Bonn}
\end{center}

\vspace{1cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Im dritten und letzten Teil unserer kleinen Vortragsreihe \"uber 
algebraische Komple\-xit\"atstheorie ging es um ein algebraisches 
Analogon zur Theorie der $\NP$-Vollst\"andigkeit. Dieses Analogon geht auf 
Valiant~\cite{vali:79-1,vali:82} zur\"uck und entsprang 
seinen Studien von Z\"ahlproblemen~\cite{vali:79-0}. 
Neben den offensichtlichen Querverbindungen zur Kombinatorik 
werden durch dieses Thema aber auch innerhalb der Komplexit\"atstheorie 
Br\"ucken geschlagen: einerseits eine Br\"ucke zur strukturellen 
Komplexit\"atstheorie, bei der es (etwa auf der Grundlage des 
Turingmaschinenmodells) um die Formulierung von Komplexit\"atsklassen 
und deren Beziehungen untereinander geht, andererseits eine Br\"ucke 
zur parallelen Komplexit\"atstheorie.

Diese Vortragsausarbeitung beginnt mit einer Erinnerung an die Booleschen 
Komplexi\-t\"ats\-klas\-sen $\P$ und $\NP$ sowie an den Begriff 
der $\NP$-Vollst\"andigkeit. Danach werden die 
algebrai\-schen Analoga $\VP$ und $\VNP$ einf\"uhrt sowie der
Begriff der $\VNP$-Vollst\"andigkeit vorgestellt. W\"ahrend die
Objekte im Booleschen Fall Sprachen sind, also Mengen von 
W\"ortern endlicher L\"ange \"uber einem endlichen Alphabet,
sind die Objekte im algebraischen Fall 
gewisse unendliche Folgen multivariater Polynome \"uber einem 
K\"orper $k$. Wichtige Rollen im algebraischen Analogon 
werden die Folgen $\DET=(\DET_n)$ bzw.\ $\PER=(\PER_n)$ der generischen 
Determinanten bzw.\ Permanenten spielen:
$$\DET_n:=\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^n 
X_{i\sigma(i)}\ , \quad
\PER_n:=\sum_{\sigma\in S_n}\prod_{i=1}^n X_{i\sigma(i)}.$$
Wir werden die (erweiterte) Hypothese von Valiant diskutieren, aus deren 
G\"ultigkeit sich ergeben w\"urde, da\ss\ es zwischen der 
Berechnungskomplexit\"at von Determinanten und Permanenten 
trotz der \"Ahnlichkeit in der Definition krasse Unterschiede gibt. 
Obwohl viele Indizien f\"ur diese Hypothese sprechen, ist man von
einem Beweis noch sehr weit entfernt.

\markboth{\hfill M.~Clausen\hfill}{\hfill Algebraische Komplexit\"atstheorie %
III \hfill}
\section{Die Hypothesen von Cook und Valiant}

In der ersten H\"alfte dieses Jahrhunderts hat man die 
Frage nach dem prinzi\-piell Berechenbaren auf verschiedene,
aber \"aquivalente Weise befriedigend formalisieren k\"onnen 
durch Konzepte wie Turingmaschinen, Registermaschinen, 
{\sc While}-Programme, rekursive Funktionen, Thue-Systeme und Markov-Algorithmen.
Zu Beginn des Computer-Zeit\-alters trat dann  natur\-gem\"a\ss\ 
die Frage in den Vordergrund: {\em Welche Probleme sind in einem 
prakti\-schen Sinne berechenbar?}

Als erste Approximation der in einem praktischen Sinn berechenbaren 
Probleme sieht man die Komplexit\"atsklasse $\P$
an, die aus allen Spra\-chen $A$ \"uber einem Alphabet $\Sigma$ besteht, 
die von einer deterministischen Turingmaschine in polynomialer Zeit 
akzeptiert werden. Das hei\ss t, zu $A$ 
gibt es eine deterministische Turingmaschine $M$ und eine 
$p$-beschr\"ankte Funktion\footnote{Eine Funktion $f\colon \N\to\N$
hei\ss t {\em $p$-beschr\"ankt}, wenn sie von einer Polynomfunktion
majorisiert wird.}
$f\colon \N\to\N$, so da\ss\ $M$ angesetzt auf $x\in\Sigma^n$ nach 
h\"ochstens $f(n)$ Schritten entschieden hat, ob $x$ zu $A$ geh\"ort 
oder nicht; im ersten Fall gibt $M$ eine $1$, ansonsten eine $0$ aus. 
$M$ berechnet also die charakteri\-stische Funktion 
$\chi_A\colon \Sigma^*\to\{0,1\}$, wobei $\Sigma^*:=\cup_{n\ge 0}\Sigma^n$.

Neben einer Vielzahl von effizient l\"osbaren Problemen traten in der 
Praxis vermehrt Pro\-bleme in den Vordergrund, die sich allen Anstregungen, 
sie effizient zu l\"osen, widersetzten. Viele derartige Probleme hatten 
aber eins gemeinsam: bekam man eine im Vergleich zur Eingabel\"ange kurze 
L\"osung ``verraten'', so hatte man es nicht schwer, diese 
L\"osung als solche zu verifizieren. 
Beispiele  derartiger Probleme sind das Erf\"ullbarkeitsproblem der 
Aussagenlogik, oder die Frage nach einem
Hamiltonkreis in einem Graphen.
Dies f\"uhrte zur Definition der Komplexit\"atsklasse $\NP$. 
%%%%%%%%%%%%%%%%%%%%
\begin{definition} Eine Sprache $A\subseteq \Sigma^*$ geh\"ort zu 
$\NP$ gdw.\ es eine $p$-beschr\"ankte Funktion $t\colon \N\to\N$ 
sowie eine Sprache $B\subseteq (\Sigma\sqcup\{\#\})^*$ aus $\P$ 
gibt, so da\ss\ 
$$\forall n\in\N\ \forall x\in\Sigma^n\ (x\in A\ \iff\ \exists e\in 
  \Sigma^{t(n)}:\ x\# e\in B).$$ 
\end{definition}
%%%%%%%%%%%%%%%%%%%
Hat $x\in A$ die L\"ange $n$ und ist $e\in \Sigma^{t(n)}$ mit 
$x\# e \in B$, so ist $e$ ein kurzer Zeuge f\"ur die 
Zugeh\"origkeit von $x$ zu $A$ und die M\"oglichkeit, $x\# e\in B$ 
in polynomialer Zeit zu entscheiden, kann man als effiziente 
Verifikation von $x\in A$ ansehen. Die obige \"Aqui\-valenz kann man auch 
so umformulieren: 
$$\chi_A(x)=\bigvee_{e\in\Sigma^{t(n)}}\chi_B(x\# e).$$

Nun kommen wir zu den algebraischen Komplexit\"atsklassen und leiten 
zun\"achst von den bisherigen Objekten, n\"amlich den Sprachen, \"uber
zu den algebraischen Objekten. 

Es sei $A$ eine Sprache \"uber dem Alphabet $\Sigma=\{0,1\}$.
Dieses $A$ kann man ansehen als 
Folge von Indikatorfunktionen $f_n$, wobei 
$f_n\colon \{0,1\}^n\to\{0,1\}$ der Indikator von $A\cap \Sigma^n$ 
in $\Sigma^n$ ist. Zu dieser Funktionenfolge geh\"ort die 
Partition $A=\sqcup_{n\ge 0} (A\cap \Sigma^n)$. Es wird f\"ur 
unsere Zwecke bequem sein, mit dem Parameter $n$ etwas gro\ss z\"ugiger 
umzugehen. Denken wir etwa an die Sprache $A$ aller invertierbaren 
Matrizen \"uber dem K\"orper $\F_2$ aus zwei Elementen, so ist
diese in nat\"urlicher Weise partitioniert als 
$A=\sqcup A_n$, wobei $A_n=\mathrm{GL}(n,2)$ ist. Demnach ist hier
$f_n\colon\{0,1\}^{n^2}\to\{0,1\}$. Da aber  die Klasse der 
$p$-beschr\"ankten Funktionen unter Komposition abgeschlossen ist,
k\"onnen wir uns diese Freiheit erlauben. Schlie\ss lich beachte 
man, da\ss\  jede $n$-stellige Boolesche Funktion sich
repr\"asentieren l\"a\ss t
durch ein Polynom $F_n\in \F_2[X_1,\ldots,X_n]$ von h\"ochstens linearem Grad 
in jeder Variablen, insbesondere ist der Grad von $F_n$ polynomial 
beschr\"ankt in $n$, sogar $\deg F_n\le n$. 

Bevor wir zur 
Definition der Komplexit\"atsklasse $\VP$ kommen, legen wir noch zwei 
Be\-zeichnungsweisen fest. F\"ur ein multivariates 
Polynom $f$ \"uber dem K\"orper $k$ sei $v(f)$ die Minimalzahl von 
Unbestimmten, von denen $f$ abh\"angt, o.B.d.A.\ sei 
$f\in k[X_1,\ldots,X_{v(f)}]$. (Manchmal werden wir auch andere 
Mengen zum Indizieren der Un\-be\-stimmten nehmen.) Im folgenden arbeiten
wir der Einfachheit halber mit straight-line Programmen, bei denen nur
addiert, multipliziert und skalarmultipliziert werden darf; die zum
Kostenma\ss\ $c$ mit $c(\omega)=1$ f\"ur $\omega\in k\cup\{+,*\}$
geh\"orige Komplexit\"at 
eines multivariaten Polynoms $f$ (modulo $I=k\cup\{X_1,X_2,\ldots\}$) 
bezeichnen wir mit $L(f)$.
%%%%%%%%%%%%%%%%%%%%%%
\begin{definition} Es sei $k$ ein K\"orper, $X_1,X_2,\ldots$ 
Unbestimmte \"uber $k$. 
\begin{itemize}
\item Eine Folge $f=(f_n)_{n\ge 1}$ multivariater Polynome \"uber $k$ 
      hei\ss t eine {\em $p$-Familie} gdw.\ die Funktionen $n\mapsto v(f_n)$ 
      und $n\mapsto \deg f_n$ beide $p$-beschr\"ankt sind. 
\item Eine $p$-Familie $f=(f_n)$ hei\ss t {\em $p$-berechenbar}, gdw.\ 
      $n\mapsto L(f_n)$ $p$-beschr\"ankt ist.
\item $\VP=\VP(\mathrm{nonuniform};k)$ bezeichnet Valiants Klasse aller 
      $p$-berechen\-baren Fa\-milien \"uber $k$.
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%%
Wir machen einige Anmerkungen zur Definition. Die 
Einschr\"ankung auf {\em $p$-Familien} ist ein Gebot der Fairness.
Dadurch wird der unerw\"unschte Effekt ausgeschaltet, da\ss\ durch zu 
schnell wachsenden Grad oder durch 
zu schnell wachsende Unbestimmtenanzahl gewisse Polynomfamilien
``komplexer'' erscheinen als sie in Wirklichkeit sind.
{\em Nichtuniform} bedeutet hier etwa: die Mitglieder der Familie $(f_n)$
m\"ussen nicht notwendigerweise einheitlich durch eine Turingmaschine 
beschreibbar sein. Wir bemerken noch, da\ss\ wir dieselbe
Komplexit\"atsklasse $\VP$ erhalten, wenn auch Divisionen zugelassen
sind und alle Operationen gez\"ahlt werden. (Dies folgt aufgrund eines
Satzes von Strassen~\cite{stra:73-1}.)

{\bf Beispiele.}
Folgende $p$-Familien liegen in $\VP$:
\begin{itemize}
\item $\mathit{SUM}:=(\mathit{SUM}_n)_{n\ge 1}$, wobei 
      $\mathit{SUM}_n:=X_1+\ldots+X_n$.
\item $\mathit{PROD}:=(\mathit{PROD}_n)_{n\ge 1}$, wobei 
      $\mathit{PROD}_n:=X_1\cdots X_n$. 
\item $\mathit{POWERSUM}:=(\mathit{POWERSUM}_n)$, wobei
      $\mathit{POWERSUM}_n:=\sum_{i=1}^n X_i^n$.
\item $\DET:=(\DET_n)$; dies folgt mittels Gau\ss elimination sowie
      der oben erw\"ahnten Tatsache, da\ss\ Divisonen zugelassen
      werden k\"onnen.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Wenn wir in $\chi_A(x)=\vee_{e\in\{0,1\}^{t(n)}}\chi_B(x\# e)$
die Disjunktion \"uber $e$ durch eine Summe \"uber $e$ ersetzen,
kommen wir zu folgendem Analogon von $\NP$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
\begin{itemize}
\item Eine $p$-Familie $f=(f_n)$ von Polynomen \"uber $k$ hei\ss t 
      $p$-definierbar, gdw.\ es eine $p$-berechenbare Familie 
      $g=(g_n)\in\VP$ gibt, so da\ss\ stets $t(n):=v(g_n)-v(f_n)\ge 0$ 
      ist und $f_n(X)=\sum_{e\in\{0,1\}^{t(n)}}g_n(X,e)$
      gilt. (Wir treffen die Konvention $X:=(X_1,\ldots,X_{v(f_n)})$ 
      und setzen $f_n(X)=g_n(X)$, falls $t(n)=0$.)
\item $\VNP=\VNP(\mathrm{nonuniform};k)$ bezeichnet Valiants Klasse 
      aller $p$-defi\-nier\-baren Fa\-milien \"uber $k$.
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Offenbar ist $\P\subseteq \NP$ und $\VP\subseteq \VNP$. Wir geben im 
folgenden eine $p$-Familie in $\VNP$ an, von der vermutet wird, da\ss\ 
sie nicht in $\VP$ liegt, wenn char$\, k\ne 2$. (Im Fall der 
Charakteristik $2$ ist $\DET=\PER$, also $\PER\in\VP$.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proposition} $\PER\in\VNP$.
\end{proposition}
%%%%%%%%%%%%%%%%
{\sc Beweis.} 
$\PER$ ist eine $p$-Familie, denn die Variablenanzahlfunktion
$n\mapsto n^2$ und die Gradfunktion $n\mapsto n$ sind
$p$-beschr\"ankt. Als n\"achstes 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}$ \"uber $k$ ist mit
$\PER_n=\sum_{e\in\{0,1\}^{n\times n}}g_n(X,e)$. 
Die Polynome $g_n$ sind definiert durch
$$g_n(X,Y):=\underbrace{\underbrace{\left(\prod_{i=\ell\ \iff\ j\ne m}
              (1-Y_{ij}Y_{\ell m})\right)}_{=:\alpha_n(Y)}\cdot
            \underbrace{\left(\prod_{i=1}^n
              \sum_{j=1}^nY_{ij}\right)}_{=:\beta_n(Y)}}_{=:\gamma_n(Y)}
            \cdot
            \underbrace{\left(\prod_{i=1}^n\sum_{j=1}^n 
                X_{ij}Y_{ij}\right)}_{=:\mu_n(X,Y)}.$$
Dann ist $g=(g_n)\in \VP$, denn $v(g_n)=2n^2$, $\deg g_n=O(n^3)$
und die Komplexit\"at von $g_n$ ist $O(n^3)$. 
Weiter zeigt man leicht f\"ur alle $e\in\{0,1\}^{n\times n}$:
\begin{itemize}
\item $\alpha_n(e)\ne 0$ gdw.\ jede Zeile und jede Spalte von $e$ 
      h\"ochstens eine Eins enth\"alt.
\item Sei $\alpha_n(e)\ne 0$. Dann ist $\beta_n(e)\ne 0$ gdw.\ jede
      Zeile von $e$ mindestens eine Eins enth\"alt.
\item $\gamma_n(e)\ne 0$ gdw.\ $e$ eine Permutationsmatrix ist. 
\item $\gamma_n(e)\in\{0,1\}$.
\item $\gamma_n(e)\ne 0$ impliziert 
      $\mu_n(X,e)=\prod_{i=1}^n X_{i\sigma(i)}$, wobei $\sigma$ die zu $e$ 
      geh\"orige Permutation bezeichnet.
\item $\PER_n=\sum_{e\in\{0,1\}^{n\times n}}g_n(X,e)$.
\end{itemize}
Dies beweist $\PER\in\VNP$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In der strukturellen Komplexit\"atstheorie sieht das weitere Vorgehen
typischerweise so aus: 
Mit geeigneten Reduktionsbegriffen partitioniert man die Komplexit\"atsklassen 
in Teil\-klassen von ungef\"ahr gleich schwierigen Problemen.
Nachdem das geschehen ist, ist man insbesondere interessiert an 
h\"arte\-sten Problemen innerhalb der gro\ss en 
Komple\-xi\-t\"atsklassen. Dies sind die sogenannten vollst\"andigen 
Probleme. Die nachfolgende Definition pr\"azisiert dies auf eine
m\"ogliche Art. (Es gibt auch andere Reduktionsbegriffe.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{definition} Es seien $A_1\subseteq \Sigma_1^*$ und 
$A_2\subseteq \Sigma_2^*$ Sprachen.
\begin{itemize}
\item $A_1$ hei\ss t {\em $p$-reduzierbar} auf $A_2$ (kurz: $A_1\le_p A_2$)
      gdw.\ eine $p$-berechenbare Funktion $f\colon \Sigma_1^*\to
      \Sigma_2^*$ existiert, so da\ss\ f\"ur alle $x\in \Sigma_1^*$ 
      gilt: $x\in A_1 \ \iff\ f(x)\in A_2$.
\item $A_1$ und $A_2$ hei\ss en {\em $p$-\"aquivalent} gdw.\ $A_1\le_p A_2$
      und $A_2\le_p A_1$. 
\item $A\subseteq\Sigma^*$ hei\ss t {\em $\NP$-vollst\"andig} gdw.\ 
      $A\in\NP$ und $B\le_p A$ gilt, f\"ur alle $B\in\NP$.
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%
Die $\NP$-vollst\"andigen Probleme sind untereinander $p$-\"aquivalent 
und bilden gerade die h\"artesten ``Brocken'' in $\NP$. Weiterhin gilt 
f\"ur ein beliebiges $\NP$-vollst\"andiges Problem $A$:
$$\P=\NP\ \iff\ A\in\NP.$$
Cook~\cite{cook:71} war der erste, der von einem nat\"urlichen Problem 
nachweisen konnte, da\ss\ es $\NP$-vollst\"andig ist:

\begin{theorem}[Cook]  Das Erf\"ullbarkeitsproblem der Aussagenlogik 
ist $\NP$-vollst\"andig. 
\end{theorem}

Mittlerweile kennt man hunderte von $\NP$-vollst\"andigen Problemen, 
darunter viele sehr praxisrelevante wie etwa das Problem des
Handlungsreisenden, oder das Problem der ganzzahligen linearen 
Optimierung, siehe z.B.~\cite{gajo:79,john:90}.

Jetzt kommen wir zu den entsprechenden Begriffen im algebraischen 
Kontext. (Beim Reduktionsbegriff sind wir in gewisser Weise
restriktiver, was letztendlich aber zu st\"arkeren Aussagen f\"uhrt.)
%%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
\begin{itemize}
\item $f\in k[X_1,\ldots,X_n]$ ist eine {\em Projektion} von 
      $g\in k[X_1,\ldots,X_m]$ gdw.\ $f=g(a_1,\ldots,a_m)$ 
      f\"ur geeignete $a_1,\ldots,a_m$ aus $k\cup\{X_1,\ldots,X_n\}$.
\item $f=(f_n)$ hei\ss t eine {\em $p$-Projektion} von $g=(g_n)$ (kurz: 
      $f \preceq_p g$) gdw.\ eine $p$-beschr\"ankte Funktion $t$ 
      existiert, so da\ss\ $f_n$ eine Projektion von $g_{t(n)}$ ist 
      f\"ur alle $n$.
\item Eine $p$-Familie $g$ \"uber $k$ ist {\em $\VNP$-vollst\"andig} gdw.\ 
      $g$ in $\VNP$ liegt und jedes $f$ aus $\VNP$ eine $p$-Projektion
      von $g$ ist.
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%%%%%%%
Offenbar sind $\VP$ und $\VNP$ abgeschlossen unter $p$-Projektionen.
Der folgende Satz zeigt, da\ss\ die Permanentenfamilie zu den
schwierigsten Familien in $\VNP$ geh\"ort.
%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Valiant]
 $\PER$ ist $\VNP$-vollst\"andig \"uber 
jedem K\"orper der Charakteristik ungleich $2$.
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%
Valiant~\cite{vali:79-1} hat weiterhin gezeigt, da\ss\ die Familie $\HC=(\HC_n)$ der
Hamiltonzykluspolynome vollst\"andig \"uber {\em jedem} K\"orper ist
(siehe auch~\cite{vzg:87}).
Um das Besondere an der Vollst\"andigkeit der Permanentenfamilie 
herauszustellen, geben wir zun\"achst eine etwas andere Charakterisierung
der Komplexit\"atsklasse $\NP$. Es sei $t\colon \N\to\N$ eine
$p$-beschr\"ankte Funktion und $R\subset \Sigma^*\times \Sigma^*$
eine Relation mit der Eigenschaft, da\ss\ f\"ur 
$(x,y)\in\Sigma^n\times\Sigma^m$ aus $R(x,y)$ stets $m\le t(n)$ folgt.
Weiterhin sei $\{x\# y\mid R(x,y)\}\in \P$. Dann nennt man
$\{x\mid\exists y: R(x,y)\}$ ein ($p$-beschr\"anktes) {\em Suchproblem} und
die Funktion, die jedem $x$ die Bin\"arkodierung der Anzahl aller $y$
mit $R(x,y)$ zuordnet, das zugeh\"orige {\em Z\"ahlproblem}. Die Klasse
$\NP$ besteht nun gerade aus allen Suchproblemen. Jedes $L\in\NP$
liefert ein Z\"ahlproblem $\#L$ und $\#\P$ (lies: number $\P$)
bezeichnet die Klasse aller Z\"ahlprobleme, die von z\"ahlenden
Turingmaschinen in Polynomialzeit berechnet werden
k\"onnen. Auch $\#\P$ enth\"alt vollst\"andige Probleme bez\"uglich eines
geeigneten Reduktionsbegriffs. Es konnte gezeigt werden, da\ss\ f\"ur viele 
$\NP$-vollst\"andige Probleme $L$ das zugeh\"orige Z\"ahlproblem $\#L$
seinerseits vollst\"andig in $\#\P$ ist, siehe
z.B.~Valiant~\cite{vali:79-0} und Johnson~\cite{john:90}.
Valiant~\cite{vali:79-2} machte dar\"uber hinaus die erstaunliche Entdeckung, da\ss\ es
sogar Probleme {\em in} $\P$ gibt, deren zugeh\"orige Z\"ahlprobleme
$\#\P$-vollst\"andig sind. Das eindrucksvollste Beispiel ist das 
Problem des perfekten Matchings in bipartiten Graphen, das nach
M.~Hall~\cite{hall:56} in $\P$ liegt. Das zugeh\"orige Z\"ahlproblem, das \"aquivalent
zur Permanentenberechnung von 0-1 Matrizen ist, stellte sich als 
$\#\P$-vollst\"andig heraus. Vor diesem Hintergrund sollte der obige
Satz von Valiant gesehen werden. 

Die S\"atze von Cook und Valiant gaben Anla\ss\ zur

\begin{center}
\begin{tabular}{ll}
{\bf Hypothese von Cook:}& $\P\ne\NP$.\\
{\bf Hypothese von Valiant:}& $\VP\ne\VNP$.
\end{tabular}
\end{center}

Wir werden im letzten Abschnitt eine versch\"arfte 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\"ur Einzelheiten verweisen wir auf Kapitel 21
in~\cite{bucs:96}.

\section{p-Definierbarkeit und Formelgr\"o\ss e}

Im ersten Beweisschritt wird eine alternative Charakterisierung der 
Valiantschen Komplexit\"atsklasse $\VNP$ mit Hilfe der 
Formelgr\"o\ss e gegeben. 


Die Menge der arithmetischen Formeln (Ausdr\"ucke) \"uber 
$I:=k\cup\{X_1,\ldots,X_n\}$ ist induktiv wie folgt definiert:
jedes Element in $I$ ist eine Formel; sind  $\varphi_1$ und 
$\varphi_2$ Formeln, so auch $(\varphi_1\circ\varphi_2)$, f\"ur
$\circ\in\{+,*\}$. Die  Gr\"o\ss e $E(\varphi)$ einer Formel
$\varphi$ ist die Anzahl der $+$ und $*$, die zu ihrem Aufbau 
benutzt wurden. Jede Formel $\varphi$ stellt in naheliegenderweise 
ein eindeutig bestimmtes Polynom $\val(\varphi)\in k[X_1,\ldots,X_n]$ 
dar. Die Formelgr\"o\ss e $E(f)$ von $f\in k[X_1,\ldots,X_n]$ ist die 
kleinste Gr\"o\ss e einer Formel $\varphi$ mit $\val(\varphi)=f$.

Jede Formel $\varphi$ kann man durch einen Baum $T_{\varphi}$
veranschaulichen. So stellt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(3455,2242)(0,-10)
\put(1725,2052){\circle{336}}
\put(1125,1452){\circle{336}}
\put(525,852){\circle{336}}
\put(1725,852){\circle{336}}
\drawline(1575,1902)(1275,1602)
\drawline(1275,1302)(1575,1002)
\drawline(975,1302)(675,1002)
\drawline(450,702)(75,252)
\drawline(675,702)(975,252)
\drawline(1650,702)(1275,252)
\drawline(1875,702)(2175,252)
\drawline(1875,1902)(3225,252)
\put(1620,2000){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} $*$}}}}}
\put(990,1400){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} $+$}}}}}
\put(460,852){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} }}}}}
\put(380,800){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} $+$}}}}}
\put(1610,800){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} $*$}}}}}
\put(-90,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} $2$}}}}}
\put(900,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$X_1$}}}}}
\put(1160,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault} $3$}}}}}
\put(2175,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$X_2$}}}}}
\put(3225,27){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}$X_2$}}}}}
\end{picture}
}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
z.B.~ die Formel $\varphi=(((2+X_1)+(3*X_2))*X_2)$ dar.
Man beachte, da\ss\ eine Formel f\"ur das Polynom $f$ als spezielles 
straight-line Programm angesehen werden kann, bei dem Zwischenresultate
nur einmal wiederverwendet werden d\"urfen; insbesondere gilt 
$$L(f)\le E(f).$$ 
Jedoch k\"onnen $L(f)$ und $E(f)$ stark voneinander abweichen, was
sich schon aus folgender Bemerkung ergibt:
$$\forall\ f\in k[X_1,\ldots,X_n]\setminus\{0\}:\  E(f)\ge \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\mapsto L(f_n)$ 
$p$-beschr\"ankt, wohingegen $n\mapsto E(f_n)$ exponentiell in $n$
ist. Allerdings ist $f$ keine $p$-Familie, da 
$n\mapsto\deg f_n$ nicht  $p$-beschr\"ankt ist. Offen ist die Frage, 
ob  ein solcher Unterschied innerhalb von $\VP$ m\"oglich ist.
%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
\begin{itemize}
\item Eine $p$-Familie $g=(g_n)$ hei\ss t {\em $p$-ausdr\"uckbar} gdw.\ 
      $n\mapsto E(g_n)$ $p$-beschr\"ankt ist.
\item $\VP_{\!e}=\VP_{\!e}(\mathrm{nonuniform};k)$ bezeichnet
	Valiants Klasse aller $p$-ausdr\"uckbaren Familien \"uber $k$.
\item $\VNP_{\!e}=\VNP_{\!e}(\mathrm{nonuniform};k)$
      bezeichnet Valiants Klasse aller  Familien $f=(f_n)$ \"uber $k$
      so da\ss\ eine $p$-ausdr\"uckbare Familie $g$ existiert mit
      $t(n):=v(g_n)-v(f_n)\ge 0$ und 
      $f_n(X)=\sum_{e\in\{0,1\}^{t(n)}}g_n(X,e)$. 
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%
Offenbar ist $\VP_{\!e}\subseteq \VP\subseteq \VNP$ und $\VNP_{\!e}\subseteq \VNP$.
Eine weitere fundamentale  Vermutung lautet:
$$\VP_{\!e}\ne \VP.$$
\"Uberraschenderweise stimmen die zugeh\"origen
``nichtdeterministischen'' Klassen \"uber\-ein:

\begin{theorem}[Valiant] $\VNP_{\!e}=\VNP$. 
\end{theorem}

Einen Beweis findet man in Abschnitt 21.2 in~\cite{bucs:96}.

\section{Universalit\"at von Determinante und Permanente}


Im zweiten Beweisschritt wird gezeigt, da\ss\ jede $p$-ausdr\"uckbare 
Polynomfamilie eine $p$-Projektion von $\DET$ und $\PER$ ist. Genauer
gilt folgender Satz. 

\begin{theorem}[Valiant]
Hat $f\in k[X_1,\ldots,X_n]$ Formelgr\"o\ss e  $u$, so ist $f$ sowohl
eine Projektion von $\mathit{DET}_{2u+2}$ als auch eine Projektion 
von $\mathit{PER}_{2u+2}$.
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\sc Beweisskizze.} (von zur Gathen) Wir beschr\"anken uns hier auf $\DET$;
\"ahnlich geht man bei $\PER$ vor.
Es bezeichne $\EX$ die Menge aller Formeln \"uber $I:=k\cup\{X_1,\ldots,X_n\}$. 
Man definiert entlang des Formelaufbaus eine Abbildung 
$\mu\colon\EX\to\cup_{s\ge 1} I^{s\times s}$ mit folgenden
Eigenschaften f\"ur alle $\varphi\in\EX$:
\begin{itemize}
\item[(A)] {$\val(\varphi)=\det(\mu(\varphi))$.}
\item[(B)] Hat $\varphi$ Formelgr\"o\ss e $u$, so ist die Matrix 
           $\mu(\varphi)$ $s$-reihig, $s=2u+2$.
\item[(C)] Mit $s=2u+2$ aus (B) gibt es $A\in I^{(s-1)\times(s-1)}$, 
           $\alpha\in I^{1\times(s-1)}$, $\beta\in I^{(s-1)\times 1}$,
           so da\ss\  $A$ obere Dreiecksmatrix ist mit Einsen auf der 
           Hauptdiagonalen und 
          $$\mu(\varphi)=\left(\begin{array}{ll} 
            \alpha&0\\ A&\beta\end{array}\right).$$
\item[(D)] $\mu(\varphi)$ hat in jeder Spalte h\"ochstens einen
           Eintrag, der nicht in $k$ liegt. Die letzte Spalte
           enth\"alt keine Unbestimmte. 
\end{itemize}
Konstruktion von $\mu$:

{\sc Fall 1.} ($u=0$) Sei $\varphi\in I$.  
Dann erf\"ullt $\mu(\varphi):={\varphi\ 0\choose 1\ 1}\in I^{2\times 2}$
die Bedingungen (A)--(D).
 
\noindent
{\sc Fall 2.}  $\varphi=(\varphi_1*\varphi_2)$. 
F\"ur $i\in\{1,2\}$ bezeichne $u_i$ die Formelgr\"o\ss e von $\varphi_i$.
Definiere $\mu(\varphi)$ wie folgt:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\setlength{\unitlength}{0.5cm}
\newsavebox{\m}
\newsavebox{\n}
\newsavebox{\oo}
\savebox{\m}{
\begin{picture}(3,3)(0,0)
\put(0,0){\framebox(3,3){}}
%
\put(0,1.5){\makebox(0.75,0.75){\scriptsize$1$}}
\put(1.5,0){\makebox(0.75,0.75){\scriptsize$1$}}
\dottedline{0.3}(0.75,1.5)(1.5,0.75)
\put(2.25,2.25){\makebox(0.75,0.75){\scriptsize$0$}}
\put(0.75,0.75){\makebox(1.5,1.5){\large $\ast$}}
\put(2.25,0){\makebox(0.75,2.25){\scriptsize$\beta_1$}}
\put(0,2.25){\makebox(2.25,0.75){\scriptsize$\alpha_1$}}
\put(2.25,0){\line(0,1){3}}
\put(0,2.25){\line(1,0){3}}
\end{picture}
}
%
\savebox{\n}{
\begin{picture}(3,3)(0,0)
\put(0,0){\framebox(3,3){}}
%
\put(0,1.5){\makebox(0.75,0.75){\scriptsize$1$}}
\put(1.5,0){\makebox(0.75,0.75){\scriptsize$1$}}
\dottedline{0.3}(0.75,1.5)(1.5,0.75)
\put(2.25,2.25){\makebox(0.75,0.75){\scriptsize$0$}}
\put(0.75,0.75){\makebox(1.5,1.5){\large $\ast$}}
\put(2.25,0){\makebox(0.75,2.25){\scriptsize$\beta_2$}}
\put(0,2.25){\makebox(2.25,0.75){\scriptsize$\alpha_2$}}
\put(2.25,0){\line(0,1){3}}
\put(0,2.25){\line(1,0){3}}
\end{picture}
}
%
\savebox{\oo}{
\begin{picture}(3,3)(0,0)
\put(2.1,2.25){\makebox(0.75,0.75){\scriptsize$1$}}
\put(0,0){\makebox(2.25,2.25){\Large$0$}}
\end{picture}}
%
\begin{picture}(19,6)(-3,0)
\put(0,0){\framebox(6,6){}}
\put(8,3){\makebox(0,0){$=$}}
\put(0,0){\usebox{\oo}}
%
\put(3,0){\line(0,1){6}}
\put(0,3){\line(1,0){6}}
\put(3,0){\makebox(3,3){$\mu(\varphi_2)$}}
\put(0,3){\makebox(3,3){$\mu(\varphi_1)$}}
\put(3,3){\makebox(3,3){\Large $0$}}
%
\put(10,0){\framebox(6,6){}}
%
\put(9.75,0){\usebox{\oo}}
%
\put(9.75,3){\usebox{\m}}
%
\put(13,3){\makebox(3,3){\Large $0$}}
%
\put(12.75,0){\usebox{\n}}
%
\put(-3,3){\makebox(0,0){$\mu(\varphi):=$}}
%
\end{picture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Dann gelten (C) und (D). Weiterhin ist $u=u_1+u_2+1$ die Gr\"o\ss e von $\varphi$ 
und nach Induktion ist die Gr\"o\ss e $s$ von
$\mu(\varphi)$ gleich $(2u_1+2)+(2u_2+2)=2u+2$, womit (B) bewiesen
ist. Aus der Blockdreiecksgestalt von $\mu(\varphi)$ folgt auch leicht (A).
 
\noindent
{\sc Fall 3.} $\varphi=(\varphi_1+\varphi_2)$. 
Wir wenden auf $M_1:=\mu(\varphi_1)$ und 
$M_2:=\mu(\varphi_2)$ das folgende Lemma an und erhalten 
$\det(M)=-\det(M_1)-\det(M_2)=-\val(\varphi)$ f\"ur die 
dort konstruierte Matrix $M$. Wir bekommen $\mu(\varphi)$, indem wir
zu $M$ eine letzte Zeile und eine vorletzte Spalte hinzuf\"ugen, deren
Eintr\"age s\"amtlich Null sind mit Ausnahme der Kreuzungsstelle, an
der eine Eins steht. 
%%%%%%%%%%%%%%%%%%%%%%
\begin{lemma} Es sei $R$ ein kommutativer Ring. F\"ur $i=1,2$ sei 
$A_i\in R^{d_i\times d_i}$ 
eine obere Dreiecksmatrix mit Einsen auf der Diagonalen, 
$\alpha_i\in R^{1\times d_i}$ und $\beta_i\in R^{d_i\times 1}$. 
Dann stehen die Determinanten und Permanenten der Matrizen
$$M_1:=\left(\begin{array}{ll} \alpha_1&0\\ A_1&\beta_1\end{array}\right), 
  M_2:=\left(\begin{array}{ll} \alpha_2&0\\ A_2&\beta_2\end{array}\right),
  M:=\left(\begin{array}{lll} \alpha_1&\alpha_2&0\\ A_1&0&\beta_1\\ 
  0&A_2&\beta_2\end{array}\right)$$
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).$$
\end{lemma}
%%%%%%%%%%%%%%%%
Der Beweis des Lemmas ergibt sich durch Laplace-Entwicklung 
nach der $d_1+1$-ten Spalte von $M$. 
Damit ist die Beweisskizze des Universalit\"atssatzes abgeschlossen.
Valiant~\cite{vali:79-1} zeigt mit einer kompakteren Konstruktion,
da\ss\ im letzten Satz $2u+2$ sogar durch $u+3$ ersetzt werden kann.

\section{Die Vollst\"andigkeit der Permanentenfamilie}


Nach den bisherigen Vorbereitungen kommen wir jetzt zur Skizze des
eigentlichen Voll\-st\"an\-digkeitsbeweises. Wir wissen bereits, da\ss\ 
$\PER$ in $\VNP$ liegt. Es bleibt zu zeigen, da\ss\ 
jedes $f\in\VNP$ eine $p$-Projektion von $\PER$ ist. 
Wegen $\VNP=\VNP_e$ gibt es zu jedem $f\in\VNP$ ein 
$g\in\VP_e$ mit $f_n(X)=\sum_e g_n(X,e)$, 
f\"ur alle $n$. Sei $m=v(f_n)$ und $t=v(g_n)-v(f_n)$. Setze
$X=(X_1,\ldots,X_m)$ und $Y=(Y_1,\ldots,Y_t):=(X_{m+1},\ldots,X_{m+t})$. 
Aufgrund der Universalit\"at der Permanente gibt es eine 
Matrix $A$ \"uber $k\cup\{X_1,\ldots,X_m\}\cup\{Y_1,\ldots,Y_t\}$ 
mit $N=2E(g_n)+2$ Reihen, f\"ur die $g_n(X,Y)=\per(A)$ ist. Weiter k\"onnen wir
nach Eigenschaft (D) im Universalit\"atsbeweis annehmen, da\ss\ $A$ 
in jeder Spalte h\"ochstens einen Eintrag hat, der eine Unbestimmte ist.
Damit ergibt sich die $\VNP$-Vollst\"andigkeit von $\PER$ aus
folgendem Resultat.
%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem} Es sei $k$ ein K\"orper der Charakteristik $\ne 2$ und 
$A=A(X,Y)$ eine $N\times N$ Matrix \"uber 
$k\cup\{X_1,\ldots,X_m,Y_1,\ldots,Y_t\}$, in der pro Spalte 
h\"ochstens ein Eintrag au\ss erhalb $k$ vorkommt. Dann l\"a\ss t 
sich eine quadratische Matrix $A'$ \"uber $k\cup\{X_1,\ldots,X_m\}$ 
mit  $N'\le 10 N$ Zeilen angeben, so da\ss\ 
$\per(A')=\sum_{e\in\{0,1\}^t} \per A(X,e)$. 
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%%
{\sc Beweisskizze.} Die zu konstruierende Matrix $A'$ hat eine 
Block- und eine Feinstruktur. 
Blockeintr\"age ungleich einer Nullmatrix gibt es in
$A'$ h\"ochstens in der ersten Blockzeile, in der
ersten Blockspalte, sowie auf der Blockdiagonalen. Das folgende Schaubild 
verdeutlicht die Blockstruktur f\"ur den Fall $t=2$:
$$A'=\left(\begin{array}{ccc}
A_0&\EuScript{Y}_{\,01}&\EuScript{Y}_{\,02}\\
\EuScript{Y}_{\,10}&\EuScript{Y}_{\,1}&0\\
\EuScript{Y}_{\,20}&0&\EuScript{Y}_{\,2}
\end{array}\right).$$
Dabei geht $A_0$ aus $A$ hervor, indem man alle $Y_i$ durch $0$
ersetzt. Bei der Feinstruktur spielt die Valiant-Matrix
$$V=\left(\begin{array}{rrrr}
0&1&-1&-1\\
1&-1&1&1\\
0&1&1&2\\
0&1&3&0
\end{array}\right)$$
eine zentrale Rolle. Dies liegt an folgenden Eigenschaften (dabei bezeichne
$V[R|C]$ die Matrix $V$ ohne die Zeilen $r\in R$ und Spalten $c\in 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\"autern die Feinstruktur von $A'$ anhand des Beispiels:
$$A=A(X_1,Y_1,Y_2)=\left(\begin{array}{rrrrr}
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{array}\right).$$
(Hier ist also $m=1$ und $t=2$.)
Die zugeh\"orige Matrix $A'$ sieht so aus (dabei ist
$\varepsilon_1=4^{-4}$ und $\varepsilon_2=4^{-2}$, was wegen der 
Voraussetzung $\mathrm{char}\, k\ne 2$ Sinn macht!):
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\vspace{1em}

\begin{center}
%\setlength{\unitlength}{0.394cm}
\setlength{\unitlength}{0.35cm}
\begin{picture}(31,31)(0,0)
%
%
%
%
%	Draw the horizontal lines%
%
\put(0,0){\line(1,0){31}}%
\put(0,1){\line(1,0){31}}%
\put(0,5){\line(1,0){5}}%
\put(22,5){\line(1,0){9}}%
\put(0,9){\line(1,0){31}}%
\put(0,10){\line(1,0){22}}%
\put(0,14){\line(1,0){22}}%
\put(0,18){\line(1,0){22}}%
\put(5,22){\line(1,0){17}}%
\put(0,26){\line(1,0){31}}%
\put(0,31){\line(1,0){31}}%
%
%	Draw the vertical lines%
%
\put(0,31){\line(0,-1){31}}%
\put(5,31){\line(0,-1){31}}%
\put(9,26){\line(0,-1){17}}%
\put(13,31){\line(0,-1){22}}%
\put(16,31){\line(0,-1){5}}%
\put(17,31){\line(0,-1){22}}%
\put(20,31){\line(0,-1){5}}%
\put(21,31){\line(0,-1){22}}%
\put(22,31){\line(0,-1){31}}%
\put(26,31){\line(0,-1){5}}%
\put(26,9){\line(0,-1){9}}%
\put(29,31){\line(0,-1){5}}%
\put(30,31){\line(0,-1){31}}%
\put(31,31){\line(0,-1){31}}%
%
%
%	The sporadic entries (row by row)%
%
\def\e#1#2#3{%
\put(#1,#2){\makebox(1,1){${#3}$}}%
}
\e{25}{0}{\varepsilon_2}%
\e{30}{0}{\varepsilon_2}%
\e{22}{1}{1}%
\e{1}{4}{1}%
\e{26}{5}{1}%
\e{30}{8}{1}%
\e{8}{9}{\varepsilon_1}%
\e{21}{9}{\varepsilon_1}%
\e{9}{10}{1}%
\e{3}{13}{1}%
\e{5}{14}{1}%
\e{0}{17}{1}%
\e{17}{18}{1}%
\e{21}{21}{1}%
\e{13}{22}{1}%
\e{12}{25}{1}%
%
% The three extra columns
% 
\e{16}{26}{1\!8}%
\e{20}{26}{2\!1}%
\e{29}{26}{1\!9}%
%
\e{16}{27}{1\!3}%
\e{20}{27}{1\!6}%
\e{29}{27}{1\!4}%
%
\e{16}{28}{9}%
\e{20}{28}{\mbox{\bf 1}}%
\e{29}{28}{1\!0}%
%
\e{16}{29}{6}%
\e{20}{29}{7}%
\e{29}{29}{\mbox{\bf 1}}%
%
\e{16}{30}{\mbox{\bf 1}}%
\e{20}{30}{4}%
\e{29}{30}{2}%
%
% The matrix A_0
%
\e{0}{26}{1\!8}%
\e{1}{26}{1\!9}%
\e{2}{26}{2\!0}%
\e{3}{26}{2\!1}%
\e{4}{26}{2\!2}%
%
\e{0}{27}{1\!3}%
\e{1}{27}{1\!4}%
\e{2}{27}{1\!5}%
\e{3}{27}{1\!6}%
\e{4}{27}{1\!7}%
%
\e{0}{28}{9}%
\e{1}{28}{1\!0}%
\e{2}{28}{1\!1}%
\e{3}{28}{\mbox{\bf 0}}%
\e{4}{28}{1\!2}%
%
\e{0}{29}{6}%
\e{1}{29}{\mbox{\bf 0}}%
\e{2}{29}{X_1}%
\e{3}{29}{7}%
\e{4}{29}{8}%
%
\e{0}{30}{\mbox{\bf 0}}%
\e{1}{30}{2}%
\e{2}{30}{3}%
\e{3}{30}{4}%
\e{4}{30}{5}%
%
%
%  The Valinat matrices 
%
%
%
\def\m{%
\makebox
}
\newsavebox{\valiant}
\savebox{\valiant}{%
\begin{picture}(4,4)(0,0)%
\put(0,0){\makebox(4,4){}}%
%
\put(0,0){\m(1,1){$0$}}%
\put(0,1){\m(1,1){$0$}}%
\put(0,2){\m(1,1){$1$}}%
\put(0,3){\m(1,1){$0$}}%
%
\put(1,0){\m(1,1){$1$}}%
\put(1,1){\m(1,1){$1$}}%
\put(1,2){\m(1,1){-1}}%
\put(1,3){\m(1,1){$1$}}%
%
\put(2,0){\m(1,1){$3$}}%
\put(2,1){\m(1,1){$1$}}%
\put(2,2){\m(1,1){$1$}}%
\put(2,3){\m(1,1){-1}}%
%
\put(3,0){\m(1,1){$0$}}%
\put(3,1){\m(1,1){$2$}}%
\put(3,2){\m(1,1){$1$}}%
\put(3,3){\m(1,1){-1}}%
%
\end{picture}
}
%
\multiput(5,22)(4,-4){4}{\usebox{\valiant}}%
\multiput(22,5)(4,-4){2}{\usebox{\valiant}}%
\linethickness{0.6mm}
%
%   The horizontal thick lines
%
%
\put(21.95,0){\line(1,0){9.15}}%
\put(5,9){\line(1,0){26.1}}%
\put(-0.065,26){\line(1,0){22.157}}%
\put(-0.065,31){\line(1,0){5.157}}%
%
%  The vertical thick lines
%
\put(0,31){\line(0,-1){5}}%
\put(5,31){\line(0,-1){22}}%
\put(22,26){\line(0,-1){26}}%
\put(31,9){\line(0,-1){9}}%
%
\linethickness{0.45mm}%
%
% The semi-thick horizontal lines
%
\put(5,18){\line(1,0){16}}%
\put(22,5){\line(1,0){8}}%
%
% The semi-thick vertical lines
%
\put(13,26){\line(0,-1){16}}%
\put(26,9){\line(0,-1){8}}%
\end{picture}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Das Ergebnis $\per(A')=\sum_{e\in\{0,1\}^2} \per A(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 $\varepsilon_1$'s die Summation $e_1\in\{0,1\}$: 
das linke $\varepsilon_1$ liefert den Beitrag
zu ``$e_1=1$'' das andere den zu ``$e_1=0$''. Entsprechendes gilt
f\"ur die beiden $\varepsilon_2$'s.

Das mag an groben Hinweisen gen\"ugen. Einzelheiten 
findet man im Abschnitt 21.4 von~\cite{bucs:96}.

\section{Die erweiterte Valiantsche Hypothese}


Wir wollen in diesem letzten Abschnitt die Valiantsche Hypothese 
versch\"arfen. Dazu arbeiten wir mit $p$-Familien, deren 
Formelgr\"o\ss en bzw.\ Komplexit\"aten quasi-polynomial wachsen 
d\"urfen; das ist schneller als polynomial, aber weniger schnell 
als exponentiell.
%%%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
\begin{itemize}
\item Eine Funktion $t\colon\N\to\N$ hei\ss t {\em quasi-polynomial beschr\"ankt}
      ({\em $qp$-beschr\"ankt}), wenn es eine positive Konstante $c$ gibt mit
      $t(n)\le n^{O(\log^c n)}$.
\item Eine $p$-Familie $f=(f_n)$ \"uber $k$ hei\ss t {\em $qp$-berechenbar}
      (bzw.\ $qp$-ausdr\"uckbar) gdw.\  $n\mapsto L(f_n)$ (bzw.\ 
      $n\mapsto E(f_n)$)  $qp$-beschr\"ankt ist.
\item $\VQP=\VQP(k;\mbox{nonuniform})$ (bzw.\ 
      $\VQP_{\!e}=\VQP_{\!e}(k;\mbox{nonuniform})$)
      bezeichnet Valiants Klasse aller $qp$-berechenbaren (bzw.\ 
      $qp$-ausdr\"uckbaren) Familien \"uber $k$.
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%%%%5
Offenbar ist $\VP\subseteq \VQP$ und $\VP_{\!e}\subseteq \VQP_{\!e}$. 
Die folgende Vermutung verallgemeinert die Hypothese $\VNP\setminus\VP\ne\emptyset$.


{\bf Erweiterte Hypothese von Valiant:}
$\VNP\setminus \VQP\ne\emptyset$ \"uber jedem K\"orper.

Mit den folgenden Ausf\"uhrungen soll skizziert werden, da\ss\ diese
Vermutung \"aquivalent ist zur Aussage: $\VNP_{\!e}\setminus
\VQP_{\!e}\ne\emptyset$ \"uber einem beliebigen K\"orper. Da wir bereits
wissen, da\ss\ $\VNP_{\!e}=\VNP$ ist, gen\"ugt es, folgenden Satz zu zeigen.
%%%%%%%%%%%
\begin{theorem} $\VQP_{\!e}=\VQP$ \"uber einem beliebigen K\"orper.
\end{theorem}
%%%%%%%%%%%%%%%%
Dieser Satz ergibt sich aus Zusammenh\"angen zwischen den verschiedenen 
Komplexit\"ats\-ma\-\ss en Formelgr\"o\ss e $E(f)$, Komplexit\"at 
$L(f)$ und der {\em Tiefe} $D(f)$ eines Polynoms $f$. Die Tiefe kann
interpretiert werden als die die minimale 
parallele Berechnungszeit, und im folgenden pr\"azisieren wir kurz
diesen Begriff. Jedem straight-line Programm
$\Gamma=(\Gamma_1,\ldots,\Gamma_r)$, das Eingaben der L\"ange $n$
erwartet, kann man einen Digraphen zuordnen, dessen Knotenmenge 
$\{-n+1,\ldots,r\}$ ist. Eine Anweisung
$\Gamma_i=(\omega_i;\alpha,\beta)$ steuert zwei Kanten, n\"amlich 
$(\alpha,i)$ und $(\beta,i)$ bei, w\"ahrend die Skalarmultiplikationsanweisung
$\Gamma_i=(\omega_i;\alpha)$ nur die Kante $(\alpha,i)$ beitr\"agt. Die
Tiefe $D(\Gamma)$ von $\Gamma$ ist die maximale L\"ange eines Weges im gerade
definierten Digraphen zu $\Gamma$. Die {\em Tiefe} (depth) des Polynoms $f$
ist definiert durch
$$D(f):=\min\{D(\Gamma)\mid \mbox{$\Gamma$ berechnet $f$}\}.$$
Entsprechend definiert man die Tiefe $T(\varphi)$ einer Formel
$\varphi$ und gelangt so zum Begriff der {\em Formeltiefe} $T(f)$ von
$f$:
$$T(f):=\min\{T(\varphi)\mid \mbox{$\val(\varphi)=f$}\}.$$
Es ist eine empfehlenswerte \"Ubung zu zeigen, da\ss\ $D(f)=T(f)$ ist.
W\"ahrend die untere Schranke des folgenden Satzes fast trivial ist
(ebenfalls eine sinnvolle \"Ubung!), ergibt sich die obere Schranke
durch geschickte Anwendung des goldenen Schnitts; daher tritt dort auch
die Zahl $\epsilon:=(1+\sqrt{5})/2$ auf.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Brent~\cite{bren:75}] F\"ur ein $n$-variates Polynom
$f$ vom Grad $d\ge 2$ gilt:
$$\log(E(f)+1)\le D(f)\le\frac{2}{\log \epsilon}\log(E(f))+1.$$
\end{theorem}
%%%%%%%%%%%%%%%%
Die Tatsache, da\ss\  $D=\Theta(\log E)$ ist,  untermauert die Vermutung,
da\ss\ $\VP_{\!e}\ne\VP$ gilt, denn $\VP_{\!e}=\VP$ w\"urde implizieren, 
da\ss\ f\"ur jedes $f\in\VP$ (insbesondere auch f\"ur $f=\DET$) 
eine Konstante $c$ existiert mit $D(f_n)\le c\log n$, 
f\"ur alle $n$. Das liegt aber jenseits unserer Vorstellungskraft.

In den Beweis von $\VQP_{\!e}=\VQP$ geht schlie\ss lich noch das folgende
fundamentale Resultat der parallelen Komplexit\"atstheorie ein, 
das auf Hyafil~\cite{hyaf:79} sowie 
Valiant, Skyum, Berkowitz und Rackoff~\cite{vsbr:83} zur\"uckgeht.
%%%%%%%%%%%%%%%%%%%%%%%%%%5
\begin{theorem}
Es gibt es eine universelle Konstante $c$, so da\ss\ f\"ur jedes 
$n$-variate Polynom $f$ vom Grad $d\ge 1$ \"uber $k$ gilt:
$$D(f)\le c(\log(d L(f))\log d+\log n).$$
Dar\"uber hinaus kann $f$ von einem straight-line Programm der L\"ange
$O(d^6 L(f)^3)$ und Tiefe $O(\log(d L(f))\log d +\log n)$ berechnet werden.
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Aus den letzten beiden S\"atzen ergibt sich nach leichter Rechnung die
Gleichheit $\VQP=\VQP_e$.

Zum Vergleich von $\DET$ und $\PER$ diskutieren wir jetzt 
Vollst\"andigkeitsresultate f\"ur $\VQP$ auf der Basis eines
etwas gro\ss z\"ugigeren Reduktionsbegriffs.
%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
\begin{itemize}
\item Seien $f=(f_n)$ und $g=(g_n)$  $p$-Familien \"uber $k$. Dann
      hei\ss t $f$ eine {\em $qp$-Projektion} von $g$ gdw.\ es eine 
      $qp$-beschr\"ankte Funktion $t$ gibt, so da\ss\ f\"ur jedes 
      $n$ das Polynom $f_n$ eine Projektion von $g_{t(n)}$ ist.
\item Eine Familie $g$ hei\ss t {\em $\VQP$-vollst\"andig} gdw.\ $g\in \VQP$
      und jedes $f\in\VQP$ eine $qp$-Projektion von $g$ ist.
\end{itemize}
\end{definition}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Offenbar ist $\VQP$ abgeschlossen unter $qp$-Projektionen.
%%%%%%%%%%%%%%%%%%%%
\begin{theorem} $\DET$ ist $\VQP$-vollst\"andig.
\end{theorem}
%%%%%%%%%%%%%%%%%%5
{\sc Beweis.} Wir wissen bereits, da\ss\ 
$\DET\in\VP\subseteq\VQP$. Nun sei 
$f\in\VQP=\VQP_{\!e}$. Dann ist $n\mapsto E(f_n)$ 
$qp$-beschr\"ankt und aufgrund der Universalit\"at 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\ss enden Vergleich von $\DET$ und
$\PER$.
Aufgrund von Satz~17 wissen wir, da\ss\ $\DET_n$ durch
ein straight-line Programm polynomialer L\"ange und Tiefe $O(\log^2n)$ berechnet werden
kann. (F\"ur direkte Konstruktionen verweisen wir auf
Csanky~\cite{csan:76}, 
Berkowitz~\cite{berk:84} und Chistov~\cite{chis:85}.)
Zusammen mit $D=\Theta(\log E)$ (Satz von Brent) ergibt das
$$E(\DET_n)=2^{O(\log^2 n)}.$$
Im Vergleich dazu ergibt sich f\"ur 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 Charakte\-ristik $\ne 2$) \"aquivalent zur folgenden 
rein algebraisch-kombinatorischen Aussage.

{\bf Erweiterte Hypothese von Valiant:}
$\PER$ ist keine $qp$-Projektion von $\DET$.

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

\begin{theorem}[von zur Gathen~\cite{vzg:87-1}]
$\PER_n$ ist keine Projektion von $\DET_m$, falls $m<\sqrt{2}n$.
\end{theorem}
Zum Beweis der erweiterten Valiantschen Hypothese m\"u\ss te 
dieses Resultat um astronomi\-sche Gr\"o\ss enordungen verbessert
werden! Vielleicht kann die Kombinatorik hier der
Komplexit\"atstheorie weiterhelfen.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{10}

\bibitem{berk:84}
S.~Berkowitz.
\newblock On computing the determinant in small parallel time using a 
small number of processors.
\newblock {\em Inf.~Proc.~Letters}, 18:147--150, 1984.

\bibitem{bren:75}
R.P.~Brent.
\newblock The complexity of multiprecision arithmetic.
\newblock In {\em Proc.~Seminar on Compl. of Comp. Problem Solving}.
\newblock Brisbaine, 126--165, 1975.

\bibitem{bucs:96}
P.~B\"urgisser, M.~Clausen, and M.A.~Shokrollahi.
\newblock {\em Algebraic Complexity Theory}, {\em {G}rundlehren
  der mathematischen {W}issenschaften}, Bd.~315.
\newblock Springer Verlag, 1996.

\bibitem{chis:85}
A.L.~Chistov.
\newblock Fast parallel calculation of the rank of matrices over a
          field of arbitrary characteristic.
\newblock In {\em Fundamentals of Computation Theory}, number 199 in 
          {\em Lecture Notes in Computer Science}, Springer-Verlag, 
          63--69, 1985.

\bibitem{cook:71}
S.A.~Cook.
\newblock The complexity of theorem proving procedures.
\newblock In {\em Proc.~3rd ACM STOC}, 151--158, 1971.

\bibitem{csan:76}
L.~Csanky.
\newblock Fast parallel matrix inversion algorithms.
\newblock {\em SIAM J.~Comp.}, 5:618--623, 1976.

\bibitem{gajo:79}
M.R.~Garey und D.S.~Johnson.
\newblock {\em Computers and intracrability: a guide to the theory of 
$\NP$-completeness.}
\newblock W.H.~Freeman and Company, New York, 1979.

\bibitem{vzg:87}
J.~von zur Gathen.
\newblock Feasible arithmetic computations: Valiant's hypothesis.
\newblock {\em J.~Symb.~Comput.}, 4:137--172, 1987.

\bibitem{vzg:87-1}
J.~von zur Gathen.
\newblock Permanent and determinant.
\newblock {\em Lin.~Alg.~Appl.}, 96:87--100, 1987.

\bibitem{hall:56}
M.~Hall.
\newblock An algorithm for distinct representatives.
\newblock {\em Amer.\ Math.\ Monthly}, 63:716--717, 1956.

\bibitem{hyaf:79}
L.~Hyafil.
\newblock On the parallel evaluation of multivariate polynomials.
\newblock {\em SIAM J.~Comp.}, 8:120--123, 1979.

\bibitem{john:90}
D.S.~Johnson.
\newblock A catalog of complexity classes.
\newblock In {\em J.~van Leeuwen (ed.): Handbook of Theoretical
Computer Science, volume A, chapter 2, 61--161}.
\newblock Elsevier Science Publishers B.~V., 1990.

\bibitem{stra:73-1}
V.~Strassen.
\newblock {Vermeidung} von {Divisionen}.
\newblock {\em Crelles J.\ Reine Angew.~Math.}, 264:184--202, 1973.

\bibitem{vali:79-0}
L.G.~Valiant.
\newblock The complexity of enumeration and reliability problems.
\newblock {\em SIAM J.~Comp.}, 8:410--421, 1979.

\bibitem{vali:79-1}
L.G.~Valiant.
\newblock Completeness classes in algebra.
\newblock In {\em Proc.~11th ACM STOC}, 249--261, 1979.

\bibitem{vali:79-2}
L.G.~Valiant.
\newblock The complexity of computing the permanent.
\newblock {\em Theoret.~Comput.~Sc.}, 8:189--201, 1979.

\bibitem{vali:82}
L.G.~Valiant.
\newblock Reducibility by algebraic projections.
\newblock In {\em Logic and Algorithmic: an International Symposium
          held in Honor of Ernst Specker}, volume 30, pp.~365--380, 1982.

\bibitem{vsbr:83}
L.G.~Valiant, S.~Skyum, S.~Berkowitz und C.~Rackoff.
\newblock Fast parallel computation of polynomials using few
processors.
\newblock {\em SIAM J.~Comp.}, 12(4):641--644, 1983.

\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}



----- End Included Message -----


