Mächtigkeit und Komplexität
von Berechnungen mit der
ganzzahligen Division
Dissertation
zur Erlangung des akademischen Grades
eines Doktors der Naturwissenschaften
dem Fakultätsrat der Fakultät
Elektrotechnik, Informatik und Mathematik
der Universität Paderborn vorgelegt von
Katharina Lürwer-Brüggemeier
Eingereicht: 15.09.2008
Erster Gutachter: Prof. Dr. Friedhelm Meyer auf der Heide
Zweiter Gutachter: Privatdozent Dr. Martin Ziegler
Inhaltsverzeichnis
1 Einleitung................................................... 1
1.1 Die Berechnungsmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Überblick................................................ 6
2 S-Berechnungsbäume für
S⊆ {+,−,∗,∗c,DIV,DIVc}
............. 10
2.1 S-Berechnungsbäume im Fall n=1 . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 S-Berechnungsbäume im Fall n>1 . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Beweise im Fall n= 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Beweise im Fall n> 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1 Operationsmengen mit
DIVc
............................... 24
4.2 Operationsmenge
{+,−,∗c,DIV}
.......................... 27
4.3 Operationsmenge
{+,−,∗,DIV}
........................... 29
4.4 Separationsresultate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Polynomauswertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.1 Polynome mit einer Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 Polynome mit mehreren Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3 Polynomauswertung mit bitweiser Konjunktion . . . . . . . . . . . . . . . 46
5.4 Speichern und Extrahieren algebraischer Zahlen. . . . . . . . . . . . . . . 51
6 Anwendungen in der Linearen Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1 Matrixmultiplikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Permanente und Determinante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.3 Potenzierung ganzzahliger Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.4 Lokale untere Schranke des ggT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.5 Primzahlbildung mit Hilfe der ganzzahligen Division. . . . . . . . . . . 63
ii
7 Rückblick und Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Abbildungsverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1
1 Einleitung
In dieser Arbeit wird die Mächtigkeit, d.h. was kann überhaupt berechnet wer-
den, und die Komplexität (d.h. wie schnell können die Berechnungen durchge-
führt werden) über verschiedene Operationsmengen
S⊆ {+,−,∗, ...}
mit der
Eingabemenge
Zn
betrachtet. Sowohl Berechnungsmächtigkeit als auch Kom-
plexität hängen stark von dem zugrundeliegenden Rechenmodell ab.
Die Turingmaschine als uniformes Rechenmodell wird allgemein als das geeig-
nete Modell für diese Art der Betrachtungen angesehen. Sie berechnet eine
Funktion
f:A∗→A∗
für ein endliches Alphabet
A
, i.a
A={0,1}.
Bei ihr
werden die Kosten bitweise berechnet, als eine Funktion
T:N→N
mit
T(n)
der Worst Case über alle Eingaben der Länge n.
Aber gerade bei der Entwicklung von Algorithmen zur Ableitung oberer Schran-
ken und insbesondere beim Beweis unterer Schranken bedient man sich häug
algebraischer Modelle, wie der uniformen Registermaschine RAM, die auf den
ganzen Zahlen (oder
R
oder
Q
) mit dem Einheitskostenmaÿ und nicht bitweise
operiert, d.h. bei ihr werden Funktionen
f:Z∗→Z∗
(bzw.
f:R∗→R∗
oder
f:Q∗→Q∗
) berechnet und die Komplexität
T(n)
wird als eine Funktion
T:N→N
als Worst Case über alle Eingaben aus
Zn
(bzw.
Qn
oder
Rn
) be-
rechnet. Die Durchführung einer Operation entspricht in diesem Modell einem
Zeitschritt und die Laufzeit wird nur in Abhängigkeit von der Dimension der
Eingabe und nicht von der Bitlänge bestimmt.
Die Berechenbarkeit und auch die Komplexität solch einer Registermaschine
hängt stark von der Wahl der Grundoperationen ab, z.B. Inkrementation, Ad-
dition, Subtraktion, Multiplikation, Vergleiche = oder <, ganzzahlige Divi-
sion, bitweise Konjunktion &, Shifts
x←y=x·2y
und
x→y=xDIV 2y
,
indirekte Adressierung usw.. Die bitweise Konjunktion und die ganzzahlige Di-
vision (wenn der Dividend kein Vielfaches des Divisors ist) gehören zwar nicht
zu den klassischen Grundoperationen, werden aber von digitalen Computern
unterstützt.
Wie sehr die Wahl der Operationsmenge die Mächtigkeit bestimmt, zeigt sich
darin, dass für RAMs mit der Eingabemenge
{0,1}∗
eine Berechnung mit der
2
Operationsmenge
{+,−,∗,=}
trotz exponentiell langer Zwischenergebnisse in
RP [39] simuliert werden kann, dagegen Berechnungen mit der Operations-
menge
{+,−,DIV,=}
bereits ganz NP abdecken [39] und mit
{+,−,∗,&,=}
sogar PSPACE [34], vergleiche auch [4,3] und [41].
Um untere Schranken zu beweisen, werden statt der uniformen Rechenmodelle
häug die entsprechenden nichtuniformen Modelle betrachtet, d.h. es werden
nicht Eingaben beliebiger Länge, sondern n-stellige Eingaben betrachtet. Eine
nichtuniforme RAM über den ganzen Zahlen bestimmt für eine Eingabe
¯x∈Zn
in Abhängigkeit von n, welche RAM M
n
ihr Programm auf
¯x∈Zn
ausführt.
Alle bekannten unteren Schranken für uniforme RAMs über
Zn
gelten auch für
nichtuniforme RAMs und es gibt bisher keine unteren Schranken für uniforme
RAMs, die explizit die Uniformität ausnutzen, sich also von unteren Schranken
für nichtuniforme RAMs unterscheiden. Als adäquates nichtuniformes Rechen-
modell zum Beweis unterer Schranken dient der S- Berechnungsbaum, kurz:
S-CT (CT = computation tree). Die Berechnungsmächtigkeit für n-stellige
Eingaben bei S-RAMs und S-CTs ist identisch, jedoch sind die Komplexitä-
ten unterschiedlich. Da die Registermaschine zusätzlich die Möglichkeit der
indirekten Adressierung hat, hat der S-Berechnungsbaum zur Simulation einer
nichtuniformen S-RAM einen zusätzlichen logarithmischen Faktor[31, Lemma
1].
Ziel dieser Arbeit ist es, die Berechnungsmächtigkeit und die Komplexität von
S-Berechnungsbäumen mit der Eingabemenge
Zn
für n>1 für verschiedene
Operationsmengen
S⊆ {+,−,∗, ...}
, die die ganzzahlige Division oder die
ganzzahlige Division mit Konstanten enthalten, zu untersuchen und Algorith-
men zu entwickeln, die durch die Hinzunahme der ganzzahligen Division und
auch weiterer nicht klassischer Operationen wie der bitweisen Konjunktion
und dem gröÿten gemeinsamen Teiler mit dem Einheitskostenmaÿ beschleu-
nigt werden.
3
1.1 Die Berechnungsmodelle
Ein
(S,C)-Berechnungsbaum
, kurz ein
(S, C)
-CT, mit der Operationsmenge
S⊆ {+,−,∗,∗c,DIVc,DIV}
und Konstanten aus der Menge
C
,
{1} ⊆ C⊆Q
,
für Eingaben
x1, . . . , xn
ist ein endlicher binärer Baum.
∗c,DIVc
bezeichnen
die Multiplikation und die Division, bei denen ein Faktor oder der Divisor
konstant ist, d.h. er hängt also nicht von den Eingabewerten ab.
Knoten
v
vom Grad 1 berechnen eine Funktion
gv:Qn→Q
.
gv
ist entweder
xi
für ein
i∈ {1, . . . , n}
oder
gv
ist
c
für ein
c∈C
oder
gv
ist von der Form
gv1op gv2
mit
v1, v2
Knoten auf dem Weg von der Wurzel zu
v
, und
op ∈S
.
Knoten
v
vom Grad 2, die Verzweigungen, sind mit Vergleichen
g(x1, . . . , xn)
>0
für eine Funktion
g
, die auf dem Weg zum Knoten
v
berechnet wurde,
beschriftet.
Knoten vom Grad 0 sind die Blätter. Sie sind mit akzeptiere oder ver-
werfe beschriftet.
f1
•
•
•
•
•
•
•
•
•
f3
p1>0
p2 >0
f4
f2
acc rej
acc
Abbildung 1.
Berechnungsbaum
Eine Eingabe
x= (x1, . . . , xn)∈Zn
folgt einem Weg von der Wurzel zu
einem Blatt. An einem Vezweigungsknoten
v
folgt sie dem linken Zweig, falls
g(x1, . . . , xn)>0
" wahr ist, sonst dem rechten Zweig. Die Eingabe
x
wird
akzeptiert, falls sie zu einem mit akzeptiere beschrifteten Blatt gelangt.
Die Menge der Eingaben, die zu den mit akzeptiere beschrifteten Blättern
gelangen, ist die von dem Berechnungsbaum erkannte Sprache
L⊆Zn
.
Die
Komplexität
eines S- Berechnungsbaumes ist seine Tiefe.
4
Werden zur Tiefe nur die Verzweigungsknoten gerechnet, spricht man von der
Verzweigungstiefe
des Baumes.
Der
Grad
eines
({+,−,∗}, C)
-CT ist der maximale Grad der Polynome, die in
seinen Knoten berechnet werden.
Die Berechnungen entlang eines Pfades im S- Berechnungsbaum, d.h. ohne
Verzweigungen, werden als
Straight-Line- Programm,
kurz SLP bezeichnet.
Die Familie
CCn(S)
der Sprachen
L⊆Zn
, die von einem Berechnungsbaum
mit der Operationsmenge
S
erkannt werden, bezeichnet die
Berechnungsmäch-
tigkeit
einer Operationsmenge
S
für
n
- dimensionale Eingaben.
Bemerkung 1
Da angenommen wird, dass
{+,−} ⊆ S
gilt, ist
CCn(S)
un-
abhängig von der Wahl von
C
,
{1} ⊆ C⊆Q
. Daher schreiben wir
S
-CTs
statt
(S, C)
-CTs, falls die Wahl von
C
nicht von Bedeutung ist.
Die Sprachen, die ein S- Berechnungsbaum für eine Operationsmenge
S
er-
kennt, lassen sich folgendermaÿen charakterisieren.
Eine Funktion
f:Zn→Z
wird als
S
-Funktion
bezeichnet, falls sie durch
ein Straight- Line- Programm mit Operationen aus
S
und Konstanten aus
Q
berechnet werden kann.
Bemerkung 2
Eine Sprache
L⊆Zn
kann genau dann durch einen
S
-CT
entschieden werden, wenn
L
eine Boolsche Kombination endlich vieler Mengen
{x∈Zn
,
f(x)>0}
für
S
-Funktionen
f
ist.
Dies ist bei wohlbekannten
S
-Funktionen eine hinreichende Charakterisierung.
Dies ist im Allgemeinen der Fall für
S={+,−,∗c}
,
S={+,−,∗}
,
S=
{+,−,∗, /}
(die
S
-Funktionen sind lineare Funktionen, Polynome, rationale
Funktionen).
In den Aufsätzen von David DOBKIN und Richard J. LIPTON [16] und Micha-
el BEN-OR [12] werden Argumente aus der algebraischen Geometrie benutzt,
um untere Schranken für
{+,−,∗, /}
-CTs mit rationalen oder reellen Eingaben
5
zu beweisen. Die Beweise basieren auf der Zahl der Zusammenhangskomponen-
ten der Sprache, die erkannt werden soll. Dies führt zu einer unteren Schranke
von z.B.
Ω(n2)
für das Rucksackproblem (knapsack problem). In dem Aufsatz
von Andrew YAO [42] werden diese Schranken auf eine groÿe Sprachklasse mit
ganzzahligen Eingaben übertragen, in [33], [23] und [30] werden diese Schran-
ken auf Registermaschinen, bei denen auch die indirekte Adressierung zulässig
ist, für den Fall
S={+,−}
übertragen.
Falls
DIV
oder
DIVc
in
S
ist, ist über die
S
-Funktionen viel weniger bekannt,
so dass Charakterisierungen der Sprachklassen und der Komplexitäten schwie-
riger sind.
In [2] wird ein sehr allgemeines Ergebnis für ein noch strengeres Modell, in
dem
DIV
und andere analytische Funktionen mit konstanten Kosten berech-
net werden, vorgestellt, nämlich dass im Allgemeinen die ganzzahlige lineare
Programmierung mit
n
Variablen und
m
Ungleichungen nicht in einer nur von
n
und
m
abhängigen Zeit, (aber nicht von der binären Eingabelänge) in diesem
Modell berechnet werden kann. Das gilt auch für die Berechnung des gröÿten
gemeinsamen Teilers ggT mit der Operationsmenge
{+,−,∗,DIV}
in [27].
Aus technischen Gründen, um die Theoreme 2 und 4 zu beweisen, wird noch der
etwas künstlich anmutende Modulo-Verzweigungs- Baum (kurz: MBT=modulo
branching tree) eingeführt.
X1mod a=0
:
Xnmod a=0
…
X1mod a=i1
:
Xnmod a=in…
X1mod a=a-1
:
Xnmod a=a-1
…
•
••
•
••
•
Abbildung 2.
Modulo-Verzweigungs-Baum
Ein
Modulo-Verzweigungs-Baum
ist ein
{+,−,∗}
- bzw.
{+,−,∗c}
- Berech-
nungsbaum, der zu einer Eingabe
x= (x1, . . . , xn)∈Zn
zusätzliche Verzwei-
6
gungsknoten von beliebigem endlichem Grad enthält. Gelangt die Eingabe
x
zu
einem Knoten vom Grad a
n
, folgt die Eingabe
x
genau dann dem
i
-ten Zweig,
falls
xjmod a=ij
für
i= (i1, . . . , in)∈ {0, . . . , a −1}n, j = 1, .., n
gilt. Eine
Eingabe
x∈Zn
wird akzeptiert, falls der zugehörige Pfad in einem akzeptie-
renden Blatt endet. Die
Komplexität
eines Modulo-Verzweigungs-Baumes ist
seine Tiefe.
1.2 Überblick
Da bei den klassischen Programmiersprachen die häugsten Operationen auf
den ganzen Zahlen
+,−,∗,∗c,DIV,DIVc
sind, wird im ersten Teil dieser
Arbeit die Berechnungsmächtigkeit und die Komplexität von Berechnungs-
bäumen mit den obigen Operationen und Verzweigungen betrachtet.
DIV
be-
zeichnet die ganzzahlige Division,
DIVc
die ganzzahlige Division durch Kon-
stanten und
∗c
die Multiplikation mit Konstanten. Für die Operationsmenge
{+,−,∗, /}
ohne ganzzahlige Division sind die Berechnungsmächtigkeit und
die Komplexitäten weitestgehend bekannt, da entlang der Pfade im Berech-
nungsbaum je nach Wahl der Operationsmenge lineare Funktionen, Polynome
oder rationale Funktionen berechnet werden. Es werden für die Komplexitäts-
betrachtungen Methoden aus der algebraischen Geometrie über Zusammen-
hangskomponenten im Reellen auf diskrete Mengen übertragen [42].
Dies ist bei Hinzunahme der ganzzahligen Division nicht mehr möglich.
Die Charakterisierungen mit den daraus abgeleiteten Schranken für Berech-
nungsbäume mit einer Operationsmenge
S⊆ {+,−,∗,∗c,DIVc,DIV}
werden
im nächsten Kapitel vorgestellt. Um den Zusammenhang zwischen den einzel-
nen Theoremen, Sätzen, Korollaren usw. zu verdeutlichen und die Lesbarkeit
zu erleichtern, werden die Beweise, da sie sehr technisch und aufwändig sind,
in den beiden folgenden Kapiteln für den eindimensionalen und mehrdimen-
sionalen Fall geführt.
Für den eindimensionalen Fall ist in [22] eine vollständige Charakterisierung
mit den daraus abgeleiteten Schranken gezeigt worden. Die Berechenbarkeit
und die Komplexität von Berechnungsbäumen mit einer Operationsmenge
S⊆
7
{+,−,∗,∗c,DIVc,DIV}
im eindimensionalen Fall werden im ersten Teil des
nächsten Kapitels vorgestellt. Dieser Abschnitt folgt weitestgehend den Aus-
führungen in [22].
Im zweiten Teil des nächsten Kapitels werden für den mehrdimensionalen Fall
bei Hinzunahme der ganzzahligen Division durch Konstanten eine vollständige
und für die allgemeine ganzzahlige Division eine partielle Charakterisierung
angegeben. Aus diesen Charakterisierungen werden Schranken abgeleitet und
Sprachklassen unterschieden. Dies sind die ersten neuen Ergebnisse. Es wird die
Berechenbarkeit im mehrdimensionalen Fall für die ganzzahlige Division durch
Konstanten vollständig charakterisiert und es werden daraus Schranken, die
ohne ganzzahlige Division bewiesen wurden, übertragen. Bei der allgemeinen
ganzzahligen Division wird nicht wie im eindimensionalen Fall eine vollständige
Charakterisierung der Sprachklassen angegeben, sondern sie werden nur teil-
weise charakterisiert. Aber aus diesen partiellen Charakterisierungen werden
wiederum untere Schranken abgeleitet, im Fall der mächtigsten Operations-
menge
S={+,−,∗,DIV}
sogar die erste untere Schranke bei Konstanten aus
Q.
Bis dahin waren nur untere Schranken bei der Konstantenmenge
C={0; 1}
bekannt. Über diese Charakterisierungen werden die Beziehungen der Sprach-
klassen
CCn(S)
für n>1 und Teilmengen
S⊆ {+,−,∗,∗c,DIVc,DIV}
voll-
ständig bewiesen.
Die Beweise zu den Charakterisierungen und den Schranken im Fall n=1 folgen
in Kapitel 3 dem Aufsatz von Friedhelm MEYER AUF DER HEIDE u.a. in
[22] mit Ausnahme von dem Beweis zu Lemma 3, der den Ausführungen von
Joao MEIDANIS in [29] folgt.
In Kapitel 4 werden die Beweise zu den Charakterisierungen und den Schran-
ken im Fall n> 1 geführt und auÿerdem werden noch Sprachen angegeben, die
die Sprachklassen unterscheiden, die im eindimensionalen Fall zusammenfallen.
Aus der ersten unteren Schranke für die Operationsmenge
S={+,−,∗,DIV}
bei Konstanten aus
Q
in diesem Kapitel kann gefolgert werden, dass der Al-
gorithmus von Nader BSHOUTY [6] zur Polynomauswertung über einer end-
lichen Menge in
N
nicht über ganz
N
konstant sein kann. Dieser Algorithmus
8
wertet ein univariates Polynom mit ganzzahligen Koezienten über einem end-
lichen Eingabebereich in 15 Schritten aus, d.h. unabhängig vom Grad des Po-
lynoms und von der Eingabe, aber durch Nutzung sehr groÿer Konstanten im
Verhältnis zum Grad und zur Eingabe.
Eine genauere Betrachtung der Komplexität der Polynomauswertung wird in
Kapitel 5 vorgenommen. Bekannt ist, dass es irreduzible Polynome vom Grad d
gibt, die über
{+,−,∗} Ω(d)
Schritte zur Auswertung benötigen [8, Theorem
6.5]. Es wird gezeigt, dass bei ganzzahligen Polynomen mit kleinen Koe-
zienten sich die Auswertung über
{+,−,∗}
beschleunigen lässt. Über einem
endlichen Bereich können Polynome in konstant vielen Schritten unabhängig
von dem Grad des Polynoms ausgewertet werden. Der von Nader BSHOU-
TY geführte Beweis für univariate Polynome wird auf multivariate Polynome
übertragen.
Die Polynomauswertung über
Zn
kann durch die Hinzunahme der bitweisen
Konjunktion & als weitere Operation beschleunigt werden. Mit dieser neuen
Operationsmenge
{+,−,∗,DIV,&}
kann jedes Polynom über
Z
in einer Va-
riablen mit einer leichten (doppellogarithmischen) Abhängigkeit von der Ein-
gabe unabhängig vom Grad des Polynoms oder aber mit einer logarithmischen
Abhängigkeit vom Grad berechnet werden. Bei Polynomen mit mehreren Va-
riablen kommt die Anzahl der Variablen als Faktor beim Aufwand hinzu. Wird
zusätzlich eine im Verhältnis zur Eingabe sehr groÿe ganze Zahl eingegeben, so
kann die Berechnung auf die Quadratwurzel der Laufzeit ohne diese Eingabe
im univariaten Fall beschleunigt werden. Im multivariaten Fall benötigt man
wiederum die Anzahl der Variablen als zusätzlichen Faktor.
Ohne & bleibt die doppellogarithmische Lücke zwischen der oberen Schranke
O(d)
und der unteren Schranke
Ω(log log d)
. Daher stellt sich die Frage, ob
jedes Polynom vom Grad d über
{+,−,∗,DIV}
in
o(d)
Schritten berechnet
werden kann. Die Antwort ist positiv, falls die Reihe
∞
X
n=0
2−dn2
algebraisch vom
Grad kleiner d ist. Dies ist aber ein in der Zahlentheorie ungelöstes Problem.
In Kapitel 6 werden Anwendungen in der Linearen Algebra betrachtet. Da-
zu zählen die Matrixmultiplikation und die Berechnung der Determinante, die
9
beide mit der ganzzahligen Division (aber ohne bitweise Konjunktion) eine
optimale quadratische Laufzeit haben. Das klassische Verfahren zur Matrix-
multiplikation benötigt kubische Laufzeit. Eingeleitet von Volker STRASSEN
wurde die Suche nach schnelleren Verfahren mit dem derzeitigen Rekord von
O(nω)
mit
ω
< 2,38, aufgestellt von Don COPPERSMITH und Shmuel WINO-
GRAD, siehe [8, Abschnitt 15]. In diesem Modell werden mit dem Einheits-
kostenmaÿ die arithmetischen Operationen
{+,−,∗}
benutzt, aber auch die
Hinzunahme der Division kann bewiesenermaÿen vergl. [8, Theorem 7.1] die
Laufzeit nicht verbessern. Wird aber nun die ganzzahlige Division als weite-
re Operation hinzugenommen, so wird gezeigt, dass die Matrixmultiplikation
über
Z
quadratische Laufzeit hat.
Über den Operationen
(+,−,∗)
sind die asymptotischen Komplexitäten der
Matrixmultiplikation und der Determinantenberechnung beliebig nahe beiein-
ander [8, Abschnitt 16.4], wenn auch, wie oben erwähnt, nicht bekannt ist, wo
zwischen
O(n2)
und
O(nω)
mit
ω
< 2,38 die genaue Komplexität liegt. Es wird
gezeigt, dass dieser Zusammenhang zwischen den Komplexitäten von Matrix-
multiplikation und Determinantenberechnung auch gilt, wenn die ganzzahlige
Division hinzugenommen wird. Dieser Zusammenhang wird nicht durch Re-
duktion, sondern durch die Angabe expliziter Algorithmen für beide Proble-
me bewiesen. Der Algorithmus zur Matrixmultiplikation nutzt eine geschickte
Kodierung der zu multiplizierenden Matrizen und Dekodierung der Produkt-
matrix aus.
Die Determinante einer
n×n
Matrix
A
kann relativ einfach in Polynomial-
zeit
O(n3)
mithilfe des Gauÿschen Eliminationsverfahren berechnet werden.
Solch eine einfache Berechnung der Permanente in Polynomialzeit ist nicht
bekannt. Dieses Problem ist
Valiant
NP
-vollständig in diesem algebraischen
Modell [8, Theorem 21.17] (und sogar
#P
-vollständig im Bitmodell). Wird
jedoch die ganzzahlige Division als weitere Operation hinzugenommen, kann
auch die Permanente sogar in quasi-optimaler Polynomialzeit
O(n2)
berechnet
werden [1, Proposition 2.4]. Die Tatsache, dass die Permanente in quadrati-
scher Laufzeit berechnet werden kann, wird zur Algorithmenentwicklung für
die Determinantenberechnung mit derselben Laufzeit verwendet.
10
Durch das k-fache wiederholte Quadrieren einer
n×n
Matrix erhält man die
2
k
-fache Potenz der Matrix und man benötigt also die k-fache quadratische
Laufzeit
O(k·n2)
. Bei der Hinzunahme des gröÿten gemeinsamen Teilers als
weitere Operation und zusätzlicher Eingabe einer Matrix B mit groÿen, aber
nicht zu groÿen Einträgen lässt sich die 2
k
-fache Potenz einer Matrix mit dem
√k−
fachen Aufwand der Matrixmultiplikation durchführen.
Im folgenden Abschnitt wird gezeigt, dass es unendlich viele solcher Matrizen B
gibt, die die dort geforderten Eigenschaften für den gröÿten gemeinsamen Teiler
der Dierenzen dieser Matrix B mit allen Matrizen, deren Einträge kleiner
als eine von k und n abhängige Konstante sind, erfüllen. Es wird eine obere
Schranke für die Gröÿe der Matrizeneinträge und eine obere Schranke für den
Aufwand zur Bildung solch einer Matrix B angegeben.
Da die Zahlen bei der Aufwandsabschätzung erheblich gröÿer sind als die obere
Schranke für die Gröÿe der Einträge, die dort als Primzahlen gewählt wurden,
stellt sich die Frage, ob die Laufzeit bei der Konstruktion von Primzahlen
durch Hinzunahme der ganzzahligen Division beschleunigt werden kann. Im
letzten Abschnitt von Kapitel 6 wird gezeigt, dass dies der Fall ist für ran-
domisierte Verfahren, aber der vorgestellte deterministische Algorithmus zur
Primzahlbildung ndet zu einer Zahl N nur dann in
O(log N)
Schritten eine
Primzahl gröÿer N, falls Mills Konstante
θ∈R
algebraisch ist. Aber auch dies
ist ein ungelöstes Problem der Zahlentheorie
2 S-Berechnungsbäume für
S⊆ {+,−,∗,∗c,DIV,DIVc}
In diesem Kapitel werden im ersten Abschnitt die vollständige Charakterisie-
rung der Berechnungsmächtigkeit der S-CTs im Fall n=1 und daraus abgeleite-
te untere Schranken und im zweiten Abschnitt für n>1 eine vollständige Cha-
rakterisierung der Berechnungsmächtigkeit der S-CTs für
S={+,−,DIVc}
und
S={+,−,∗,DIVc}
und eine partielle Charakterisierung der Berech-
nungsmächtigkeit der S-CTs für
S={+,−,DIV}
und
S={+,−,∗,DIV}
11
gezeigt. Auch im Fall n>1 werden aus den Charakterisierungen untere Schran-
ken abgeleitet. Die Beweise zu den Theoremen, Sätzen, Korollaren usw. dieses
Kapitels sind im Fall n=1 im 3. Kapitel und im Fall n>1 im 4. Kapitel, da sie
sehr umfangreich und technisch sind und den Leseuss stark beeinträchtigen
würden.
2.1 S-Berechnungsbäume im Fall n=1
Im Fall einer einzigen Eingabevariable wird eine vollständige Charakterisierung
der Berechnungsmächtigkeit der
S
-CTs gegeben [22]. Diese Sprachklassen sind
äquivalent für
{+,−,∗,DIV}
und
{+,−,DIVc}
; es sind genau die Sprachen
L⊆Z
, die aus einer endlichen Menge und endlich vielen arithmetischen
Progressionen bestehen.
Denition 1.
Seien
a1, a2∈N
,
A1, A2, B ⊂Z
,
A1, A2, B
endlich.
L(a,A,B) := B
∪{d+λa1|λ∈N, d ∈A1}∪{d−λa2|λ∈N, d ∈A2}
heiÿen
AP-Sprachen (AP = arithmetische Progression).
Theorem 1.
Sei L
⊂Z
. Folgende Aussagen sind äquivalent:
(i) L ist eine AP-Sprache.
(ii) L ist durch einen MBT entscheidbar.
(iii) L ist durch einen
{+,−,DIVc}
-CT entscheidbar.
(iv) L ist durch einen
{+,−,∗,DIV}
-CT entscheidbar.
Aber die Komplexitäten sind verschieden: Falls die Konstanten aus
Q
sind,
kann jede Sprache
L⊆Z
, die überhaupt erkannt werden kann, bereits in
konstanter Zeit über
{+,−,∗c,DIV}
erkannt werden. Dies folgt unmittelbar
aus der obigen Charakterisierung der Sprachklassen als AP-Sprache, da A
und B endlich sind und die Zugehörigkeit zu einer arithmetischen Progressi-
on über
{+,−,∗c,DIV}
in konstanter Zeit entschieden werden kann. Aber die
aus demTheorem abgeleitete Konstante aus [22] ist abhängig von der Sprache
L. Darüber hinaus zeige ich sogar, dass erstaunlicherweise jede Sprache L in
12
CC1({+,−,∗,DIV},Q)
in 40 Schritten, d.h. unabhängig von L, erkannt wer-
den kann. Der Beweis basiert auf dem bereits eingangs erwähnten Algorithmus
zur Polynomauswertung in 15 Schritten von Nader BSHOUTY.
Satz 1
Jede Sprache
L⊆Z
, die von einem
({+,−,∗,DIV},Q)
-CT erkannt
wird, kann in 40 Schritten, unabhängig von L, von einem
({+,−,∗,DIV},Q)
-
CT erkannt werden.
Auf der anderen Seite gibt es für einige Sprachen der Gröÿe
n
untere Schran-
ken
Ω(log(n)/loglog(n))
[22], falls nur Operationen aus
{+,−,DIVc}
benutzt
werden, (aber immer noch beliebige Konstanten aus
Q
).
Satz 2
Sei L
⊂Z,
#L=n. Falls L keine arithmetische Progression der Län-
ge k+1 enthält, hat ein
({+,−,DIVc},Q)−
CT, der L erkennt, die Tiefe
Ω(log n/log log n)
, falls k
≤
log n, ansonsten
Ω(log n/log k)
.
Aus diesem Satz ergeben sich für nachstehende Beispiele untere Schranken für
({+,−,DIVc},Q)−
CTs.
Beispiel 1
L
n
:= {2
i
, i = 1, ..., n}
hat n Elemente und keine arithmetische Progression
der Länge 3, daher gilt eine untere Schranke von
Ω(log n/log log n).
L
m
:= {i
2
, i = 1, ..., m}
hat m Elemente und keine Progression der Länge
4, daher gilt ebenfalls eine untere Schranke von
Ω(log n/log log n)
.
L
l,k
:= {j·(k+ 1)
i
, i = 0, ..., l −1; j= 1, ..., k}
hat n= l
·
k Elemente
und keine Progression der Länge k+1, daher gilt eine untere Schranke von
Ω(log n/log k)
.
Weitere untere Schranken sind nur bekannt, falls die Konstanten auf
{0,1}
beschränkt werden. In diesem Fall benötigt die Berechnung des gröÿten ge-
meinsamen Teilers von zwei
N
-Bit Zahlen mit den Operationen
{+,−,∗,DIV}
Ω(log log N)
Zeit, siehe [27], und
Ω(N)
mit den Operationen
{+,−,∗c,DIVc}
,
siehe [5].
13
2.2 S-Berechnungsbäume im Fall n>1
Es werden Sprachklassen
CCn(S)
mit
DIV
oder
DIVc
in
S
unterschieden und
untere Schranken bewiesen.
Zunächst betrachte ich die Operationsmengen
{+,−,∗,DIVc}
und
{+,−,∗c,DIVc}
.
Mit
{+,−,∗}
können Polynome und mit
{+,−,∗c}
nur lineare Funktionen be-
rechnet werden.
Für
a∈N
,
b∈Zn
bezeichne ich die Menge
aZn+b={ax +b
,
x∈Zn}
als
a
-Gitter. Die
a
-Gitter
aZn+b
für
b∈ {0, . . . , a−1}n
bilden eine Zerlegung des
Zn
in
a
-Gitter der Länge
a
.
In
Z
ist solch ein
a
-Gitter nichts anderes als eine arithmetische Progression
mit der Schrittlänge
a
.
Theorem 2.
Sei
S={+,−,∗,DIVc}
oder
S={+,−,∗c,DIVc}
.
a)
L⊆Zn
kann genau dann durch einen
S
-CT
D
entschieden werden, wenn
es ein
a∈N
gibt, so dass der
Zn
in
a
-Gitter zerlegt werden kann, so dass
L
auf jedem einzelnen
a
-Gitter durch einen
(S−{DIVc})
-CT erkannt wird.
b) Ist
D
ein
(S, Q)
-CT der Tiefe
T
, haben die obigen
((S−{DIVc},Q)
-CTs
die Tiefe
O(T)
.
c) Ist
D
ein
(S, {0,1})
-CT der Tiefe
T
, haben die obigen
(S−{DIVc},Q)
-CTs
die Tiefe
O(T)
, und die Schrittweite
a
der Gitter ist höchstens
222T
.
Das obige Ergebnis gibt eine Normalform" für Berechnungsbäume mit
DIVc
:
Zunächst bestimme mit
DIVc
, auf welchem Gitter die Eingabe liegt. Danach
entscheide mit einem Berechnungsbaum ohne
DIVc
, ob die Eingabe in
L
liegt.
Die untere Schranke in b) zeigt, dass die Tiefe sich nur um einen konstanten
Faktor unterscheidet, falls diese Normalform benutzt wird.
In
Z
ist die Darstellung als AP- Sprache solch eine Normalform", jedoch gilt
sie dort, anders als im Fall n>1, nicht nur für
DIVc
, sondern auch für
DIV
.
Als Korollar zu Theorem 1b) kann gezeigt werden, dass die untere Schranke
über die Zahl der Zusammenhangskomponenten für
{+,−,∗}
-CTs in [12],
14
die in [42] auf ganzzahlige Eingaben übertragen wird, auch für ganzzahlige
Eingaben und
{+,−,∗,DIVc}
-CTs gilt und daher auf eine groÿe Klasse von
Sprachen übertragen werden kann. Hierzu zählen folgende Beispiele
Korollar 1
Für
({+,−,∗,DIVc},Q)
- CTs gelten folgende unteren Schranken:
Ω(nlog(n))
für Element Distinctness (überprüfe, ob alle Eingaben
x1, . . . , xn
verschieden sind, (siehe [12]).
Ω(n2)
für das Rucksackproblem (Eingabe
a1, . . . , an, b
; überprü-
fe, ob es
y1, . . . , yn∈ {0,1}
gibt mit
Σn
i=1aiyi=b
, siehe
[16]).
Ω(n2log(k+ 1))
für lineare diophantische Gleichungen mit
k
-beschränkten
Lösungen (Eingabe
a1, . . . , an, b
, überprüfe, ob es
y1, . . . , yn∈ {0, . . . , k}
gibt mit
Σn
i=1aiyi=b
, siehe [30]).
Nun komme ich zu Berechnungen mit der allgemeinen ganzzahligen Division. In
diesem Fall kann keine vollständige Charakterisierung der Sprachklassen gege-
ben werden, sondern nur eine partielle. Zunächst betrachte ich
{+,−,∗c,DIV}
-
CTs
.
Theorem 3.
a) Falls
L⊆Zn
von einem
{+,−,∗c,DIV}
-CT
D
erkannt wird, gilt: Zu jeder
irrationalen Zahl
β
gibt es eine Pyramide
P:= {(x1, .., xn)∈Zn
,
c1<
xi+1
xi< c2, i = 2, ..., n}
mit
c1, c2∈Q
,
c1< β < c2
und
a∈N
, so dass es zu
jedem
¯
b∈ {0, . . . , a−1}n
einen
{+,−,∗c}
-CT gibt, der
L
auf
(aZn+¯
b)∩P
erkennt.
b) Falls
D
ein
({+,−,∗c,DIV},{0,1})
-CT der Tiefe
T
ist, gibt es
a∈N
und
eine Pyramide
P:= {(x1, .., xn)∈Zn
,
c1<xi+1
xi< c2, i = 2, ..., n}
mit
c1, c2∈Q
, so dass es zu jedem
b∈ {0, . . . , a −1}n
einen
({+,−,∗c},Q})
-
CT der Tiefe
O(T)
gibt, der
L
auf
(aZn+¯
b)∩P
erkennt.
15
c) Falls
D
ein
({+,−,∗c,DIV},{0,1})
-CT der Tiefe
T
ist, der eine Sprache
L⊆Z2
erkennt, gibt es
a∈N
,
a≤223T
, und eine Pyramide
P:= {(x, y)∈
Z2
,
c1<x
y< c2, i = 2, ..., n}
mit
c1, c2∈Q
,
c1< c2, c2−c1≥1
223T
, so dass
es zu jedem
b∈ {0, . . . , a −1}2
einen
({+,−,∗c},Q})
-CT der Tiefe
O(T)
gibt, der
L
auf
(aZ2+¯
b)∩P
erkennt.
x = c1y
x = c2y
x = √2 y
Abbildung 3.
Pyramide
In [10] wird ein Algorithmus vorgestellt, der den ggT von 2
N
-Bit Zahlen in der
Zeit
O(N)
berechnet. Er benutzt nur Operationen aus
{+,−,DIVc}
. Aus Er-
gebnissen in [5] und [22] folgt, dass für die Operationsmenge
{+,−,DIVc}
die
untere Schranke auch bei
Ω(N)
ist, d.h. eine scharfe Schranke ist. Aus Theo-
rem 2b) folgt, dass der Algorithmus aus [10] auch bei der Operationsmenge
{+,−,DIV}
optimal ist.
Korollar 2
Ein
({+,−,DIV},{0,1})
-CT, der die Teilerfremdheit von 2
N
-
Bit Zahlen
x, y
überprüft, hat eine Tiefe von
Ω(N)
.
Nun komme ich zur mächtigsten Operationsmenge, nämlich
{+,−,∗,DIV}
.
Wie bereits vorher erwähnt, ist es sehr schwierig, in diesem Fall untere Schran-
ken zu nden. Es wird die erste untere Schranke bei Konstanten
Q
bewiesen
.
16
Theorem 4.
a) Falls
L⊆Zn
durch einen
{+,−,∗,DIV}
-CT
D
erkannt werden kann,
gibt es für jedes
c1, .., cn∈N
Polynome
pi:Zn−i→Q
, i=1,...,n-1 und
k1, ..., kn, K ∈N
, so dass eingeschränkt auf
{(x1, ..., xn)∈Nnxi≥xki
i+1
,
xi≡cimod pi(xi+1, ..., xn), i = 1, ..., n −1
,
xn≡cnmod kn, xn> K, }L
durch einen
{+,−,∗}
-CT erkannt werden kann.
b) Falls
D
ein
({+,−,∗,DIV},Q)
-CT der Tiefe
T
ist, haben die
pi
einen Grad
≤22nT
,
ki≤22(n−1)T
und der
({+,−,∗},Q}
-CT hat eine Verzweigungstiefe
O(T)
und Grad
O(22nT )
.
Aus Teil b) kann die erste nicht-triviale untere Schranke für die Tiefe von
({+,−,∗,DIV},Q)
-CTs abgeleitet werden. Diese Sprachklasse ist sehr mäch-
tig, wenn man daran denkt, dass auch im mehrdimensionalen Fall jede endliche
Sprache, unabhängig von der Gröÿe der Sprache, in konstanter Zeit erkannt
werden kann.
Bemerkung 3
Jede endliche Sprache
L⊆Zn
kann durch einen
({+,−,∗,
DIV},Q)
-CT in konstanter Zeit unabhängig von L erkannt werden.
Korollar 3
Sei
r:Z→Z
ein irreduzibles Polynom vom Grad
d
mit positivem
Leitkoezienten. Jeder
({+,−,∗,DIV},Q)
-CT, der
Lr={(x, y)∈Z2, r(y)>
x}
erkennt, hat eine Tiefe
Ω(log log (d))
.
Diese untere Schranke zeigt, dass anders als im eindimensionalen Fall die Aus-
sage, dass jede Sprache L, die überhaupt von einem
({+,−,∗,DIV},Q)
-CT
erkannt werden kann, bereits in konstanter Zeit erkannt wird, im mehrdimen-
sionalen Fall nicht mehr gilt.
Ebenfalls anders als im Falle
n= 1
zeigen die Teile a) der obigen drei Theo-
reme, dass nicht nur Sprachklassen mit oder ohne ganzzahlige Division unter-
schieden werden.
Eine vollständige Übersicht über die Beziehungen dieser Sprachklassen zeigt
das folgende Theorem. In diesem Theorem bedeutet ein Pfeil
S→S0
für
17
Operationsmengen
S, S0
, dass
CCn(S0)⊂
6=CCn(S)
für
n≥2
gilt.
S−−−S0
bedeutet, dass
CCn(S)
und
CCn(S0)
nicht vergleichbar sind.
Theorem 5.
Folgende Beziehungen gelten für die Sprachklassen
CCn(S)
für
n≥2
:
für n > 1
CCn{+,-}
CCn{+,-,*}CCn{+,-,divc}
CCn{+,-,*, divc}CCn{+,-,div}
CCn{+,-,*, div}
Abbildung 4.
Sprachklassen für n>1
Bemerkung 4
Das obige Diagramm zerfällt in zwei Sprachklassen mit
DIV
oder
DIVc
bzw. ohne
DIV
oder
DIVc
, falls der Fall
n= 1
betrachtet wird, siehe
Theorem 1.
für n = 1
CC1{+,-}= CC1{+,-,*}
CC1{+,-,divc}= CC1{+,-,div}=
CC1{+,-, *,divc}= CC1{+,-,*,div}
Abbildung 5.
Sprachklassen für n=1
18
3 Beweise im Fall n= 1
Dieses Kapitel enthält die Beweise zu Theorem 1, zu Satz 1 und zu der unteren
Schranke in Satz 2, die bis auf Lemma 4 in [29] und Satz 1 in [25] den Beweisen
in [22] folgen.
Beweis.
[zu Theorem 1]
Es wird der Beweis in folgender Reihenfolge ausgeführt:
(i)
⇒
(iii)
⇒
(iv)
⇒
(ii)
⇒
(i)
(i)
⇒
(iii)
Sei L = L(a,A,B) eine AP-Sprache.
- Überprüfe durch Binärsuche, ob x
∈
B gilt.
- Falls ja, akzeptiere, ansonsten überprüfe für jedes d
∈
A
1
oder d
∈
A
2
, ob
x∈ {d+λa1, λ ∈N}
oder
x∈ {d−λa2, λ ∈N}
gilt.
Dies ist durch a
i
·
((x - d)
DIVc
a
i
)=x-d,i
∈
{1,2} möglich.
Da a
i
Konstanten sind, kann a
i
·
((x - d)
DIVc
a
i
) ohne Multiplikation berechnet
werden.
Der obige
{+,−,∗,DIV}
- CT entscheidet L.
ut
(iii)
⇒
(iv)
gilt trivialerweise, da
{+,−,DIVc} ⊂ {+,−,∗,DIV}
.
ut
(ii)
⇒
(i)
Sei T ein MBT, der eine Sprache L
⊂Z
entscheidet,
υ
ein akzeptierendes Blatt
von T und c(
υ
) die Eingabemenge, die zu
υ
gelangt. Da durch
{+,−,∗}
nur
Polynome berechnet werden können, sind die binären Verzweigungsknoten mit
p(x) >0 oder p(x)
≤
0 für Polynome p beschriftet, die auf dem Weg zu
υ
be-
rechnet wurden. Daher ist
c(υ)
entweder endlich oder
c(υ) = Bυ∪Iυ
.
Bυ
ist da-
bei eine endliche Menge, die alle Elemente von c(
υ
) enthält, die zu beschränk-
ten Zusammenhangskomponenten der Mengen
{x|p(x)>(≤)0}
, die von den
19
binären Verzweigungen kommen, gehören. Die Menge
Iυ
hat die Form
Iυ
=
{x|x >
βυ
, x mod
δj
=
ij
, j = 1,...,r}, wobei die r Modulo-Verzweigungsknoten
(kurz: MB-Knoten) auf dem Weg zu
υ
vom Grad
δ1
,...,
δr
sind, bei der j-ten
Verzweigung der
ij
-te Zweig gewählt wird und
βυ
= max
Bυ
ist.
Die Menge
Iυ
kann als eine einzige Progression dargestellt werden, d.h.
Iυ
=
{dυ+λaυ, λ ∈N}
für geeignete
dυ, aυ.
Sei V die Menge der Blätter, die un-
endlich viele Eingaben akzeptieren.
Dann ist I =
Sν∈VIυ
Vereinigung von endlich vielen arithmetischen Progres-
sionen.
Bekannterweise folgt aus der Zahlentheorie, dass I = B'
∪{d+λa, λ ∈Z, d ∈A
}
für ein a
∈Z
und endliche Mengen B' und A gilt.
Sei nun B die endliche Eingabemenge, die zu den akzeptierenden Blättern mit
endlicher Eingabemenge gelangt, und B':=
Sν∈VBυ
, B:=B'
∪
B
∪
B', dann
ist L = L(a,A,B), also eine AP-Sprache.
ut
(iv)
⇒
(ii)
Diese Beweisrichtung ist die umfangreichste.
Sei T ein
{+,−,∗,DIV}
- CT, der L erkennt.
Es wird gezeigt, dass die DIV-Knoten durch MB-Knoten ersetzt werden kön-
nen, so dass der so erhaltene MBT eine Sprache L' akzeptiert, die für be-
tragsmäÿig genügend groÿe x mit L übereinstimmt. Für betragsmäÿig kleine
x werden x
∈
L durch Binärsuche akzeptiert, so dass man einen MBT für L
erhält.
Um die DIV-Knoten durch MB-Knoten zu ersetzen, wird das folgende Lemma
benötigt.
Lemma 1.
Seien
p,q :Z→Q
Polynome mit rationalen Koezienten, deg(p)
≥
deg(q). Dann gibt es
β, z ∈N
, so dass es zu jedem
i∈ {0, ..., β −1}
ein
Polynom
ri:Z→Q
mit rationalen Koezienten gibt, so dass
p(x) DIV q(x) =
r
i
(x)
gilt.
20
Mit Hilfe dieses Lemmas wird zunächst der Beweis (iv)
⇒
(ii) beendet.
Sei
υ
der erste DIV-Knoten auf einem Weg von der Wurzel zu einem Blatt in
T. Dann ist dieser Knoten mit
p(x) DIV q(x)
beschriftet, wobei p,q Polynome
mit rationalen Koezienten sind, die auf dem Weg zu
υ
berechnet wurden.
Falls deg(p) < deg(q) gilt, wird
p(x) DIV q(x)
durch 0 ersetzt. Dies ist korrekt
für betragsmäÿig genügend groÿe x.
Im Folgenden sei deg(p)
≥
deg(q).
Nach dem obigen Lemma gibt es
β, z ∈N
, so dass es zu jedem
i∈ {0, ..., β −1}
ein Polynom
ri:Z→Q
mit rationalen Koezienten gibt, so dass
p(x) DIV q(x)
=r
i
(x)
gilt. Es wird nun der DIV- Berechnungsknoten durch einen MB-Knoten
vom Grad
β
ersetzt. Für
i∈ {0, ..., β −1}
wird an den i-ten Zweig die Be-
rechnung für das Polynom
ri
angehängt. Eine Kopie des Teilbaumes von T
unterhalb von
υ
wird an die Berechnung der
ri
gehängt. In diesem Teilbaum
wird jeweils
p(x) DIV q(x)
durch
r
i
(x)
ersetzt.
Von der Wurzel zu den Blättern wird so schrittweise jeder DIV- Berechnungs-
knoten ersetzt. Der dadurch entstandene MBT erkennt eine Sprache L' mit
L0∩{x∈Z,|x| ≥ z}
=
L∩{x∈Z,|x| ≥ z}
für ein genügend groÿes z.
Um L zu erkennen, wird zunächst nach
|x| ≥ z
verzweigt. Bei positiver Ant-
wort wird der MBT durchlaufen, ansonsten wird durch Binärsuche die endliche
Sprache
L∩{x∈Z,|x|< z}
erkannt.
ut
Beweis.
[von Lemma 1]
Aus der Algebra ist bekannt, dass man durch Polynomdivision Polynome
r,s:
Z→Q
mit rationalen Koezienten und deg(s)<deg(q) mit p = r
·
q + s gibt.
Wähle nun
β
, so dass es ein Polynom
˜r :Z→Q
mit ganzzahligen Koezienten
und
r=1
β˜r
gibt. Dann erhält man für
p(x) DIV q(x)
p(x) DIV q(x) = r(x) + s(x)
q(x)=1
β˜r(x) + s(x)
q(x)
21
Da deg(s) < deg(q) gilt, ist
lim
|x|→∞
s(x)
q(x)= 0
.
Das heiÿt, dass für genügend groÿes x
p(x) DIV q(x) = ˜r(x) DIV β
gilt.
Sei nun
i∈ {0, ..., β −1}
fest und
xmod β=i
, d.h.
x=λβ +i
für ein
λ∈Z
und
˜r(x) = Pn
j=0 ajxj, aj∈Z
.
Wird i als Konstante betrachtet, kann
˜r(x) = ˜r(λβ +i)
als Polynom in
λ
geschrieben werden.
˜r(x) = Pn
j=0 bj(λβ)jmit bj∈Z
(b
j
hängt von i ab)
˜r(x) = Pn
j=0 bj(λβ)j=b0+β·g(λ) mit g(λ) = Pn
j=0 bjβj−1λj∈Z
Daher erhält man für genügend groÿes x mit x mod
β
= i
p(x) DIV q(x) = ˜r(x) DIV β=b0DIV β+g(λ)
=b0DIV β+g((x−i)/β) = Polynom in x.
ut
Beweis.
[zu Satz 1]
Sei
L⊂Z
eine Sprache, die durch einen
({+,−,∗,DIV},Q)
-CT erkannt wird,
dann ist nach Theorem 1 L eine AP-Sprache. Jede solche AP-Sprache hat
folgende Darstellung
L(a, A, B) := B∪{d+λa1|λ∈N, d ∈A1}∪{d−λa2|λ∈N, d ∈A2}
Für eine Eingabe
x∈Z
entscheide, ob
x∈B
gilt. Falls
x∈B
akzeptiere,
ansonsten berechne x mod a
1
= x - a
1
(x div a
1
) für x>0 und x mod a
2
=x-
a
1
(x div a
2
) für x<0.
Ohne Einschränkung gelte für
d∈Aiddiv ai=ki
. Entscheide, ob
xmod ai+
ki∈Ai
. Falls ja, akzeptiere, ansonsten verwerfe. Da A
i
und B endlich sind,
22
können mit dem folgenden Lemma die Abfragen
x∈B
und
xmod ai+ki∈Ai
in konstanter Zeit, unabhängig von A
i
und B, entschieden werden, d.h L wird
in konstanter Zeit, unabhängig von L, erkannt.
ut
Lemma 2.
Sei
A⊂Z
endlich. A kann durch einen
({+,−,∗c,DIV},Q)
-CT
in 18 Schritten, unabhängig von A, erkannt werden.
Beweis.
[zu Lemma 2]
Da A endlich ist, kann A als Nullstellenmenge eines Polynoms p mit ganzzah-
ligen Koezienten betrachtet werden. Sei
N:= max{|x||x∈A}.
Der folgende
Berechnungsbaum erkennt A.
Für eine Eingabe
x∈Z
verwerfe, falls
|x|> N
gilt. Ansonsten berechne
p(x)
bzw.
p(−x)
für
x < 0
und akzeptiere, falls
p(x) = 0
bzw.
p(−x) = 0
für
x < 0
,
ansonsten verwerfe. Nach Theorem 7 kann solch ein Polynom mit ganzzahligen
Koezienten über einer endlichen Eingabemenge in 15 Schritten, unabhängig
von p und N, in konstant vielen Schritten berechnet werden.
ut
Beweis.
[zu Satz 2]
T sei ein
({+,−,DIVc},Q)−
CT der Tiefe D, der eine endliche Sprache L
(#L=n), die keine arithmetische Progression der Länge k+1 enthält, erkennt.
υ
sei ein Blatt von T und
υ
1
, ..., υd=υ
sei der Pfad zu
υ
, d
≤D. fi:Z→Q
seien die Funktionen, die an den Knoten
υ
i
berechnet werden, und
c(υ)
die
Menge der Eingaben, die zu
υ
gelangt.
Mit dem folgenden Lemma wird
c(υ)
charakterisiert.
Lemma 3.
Es gibt ein konvexes Polytop P im
Rd+1
mit
(i) x
∈c(υ)⇔ ∃(c1, . . . , cd)∈Zd
:
(x, c1, . . . , cd)∈P.
(ii) Für jedes x
∈c(υ)
gibt es genau ein
(c1, . . . , cd)∈Zd
mit
(x, c1, . . . , cd)∈P.
Beweis.
[zu Lemma 3]
23
Von der Wurzel zu den Blättern wird jede
DIVc−
Operation durch eine neue
Variable
cj
ersetzt. Es werden höchstens d neue Variablen benötigt. Im Fol-
genden wird, falls das Ergebnis dieser
DIVc−
Operation als Operand benutzt
wird, statt des Ergebnisses dieser
DIVc−
Operation diese neue Variable be-
nutzt. An jedem Knoten
υi
wird nun eine Funktion
gi(x, c1, . . . , cd)
berechnet.
Da nur +,- als Operationen benutzt werden, sind die
gi
linear.
I⊂1, .., d
sei
die Indexmenge, für die an den Knoten
υi
eine
DIVc−
Operation benutzt wird.
Wenn an dem Knoten
υi
, i
∈
I,
ai(x, c1, . . . , cd) DIVcbi
berechnet wird, werden
folgende Ungleichungen deniert.
(*)
bi·ci≤(≥)ai(x, c1, . . . , cd)<(>)bi(ci+ 1)
Falls
bi
positiv ist, steht dort (
≤
,<) ansonsten (
≥
>).
Es werden noch die Ungleichungen der Verzweigungsknoten
υi
(**)
gi(x, c1, . . . , cd)>(≤)0
zu dem Ungleichungssystem aus (*) hinzugefügt. Ob dort < oder
≥
steht,
richtet sich danach, ob der rechte oder linke Zweig zum Pfad gehört.
Nach der Konstruktion dieses Systems linearer Ungleichungen aus (*) und (**)
erfüllt dessen Lösungsmenge P gerade die Bedingungen (i) und (ii) und P ist
als Lösungsmenge eines linearen Ungleichungssystems ein konvexes Polytop.
ut
Sei
Pυ
das zum Pfad
υ
gehörende Polytop. Aus Lemma 2 folgt, dass
#Pυ∩Z
n
=
#c(υ)
. Im Folgenden wird gezeigt, dass #
Pυ∩Z
n
klein ist, falls
c(υ)
keine
lange arithmetische Progression enthält. Dazu benötigt man noch das folgende
Lemma. Man spricht von einer Progression der Länge k im
Z
n
, falls es k Punkte
gibt, die in jeder Koordinate zu einer arithmetischen Progression der Länge k
gehören.
Lemma 4.
Sei B die Menge der ganzzahligen Punkte in einer konvexen Teil-
menge des
Rn
.
Falls |B| > k
n
gilt, enthält B eine Progression der Länge k+1.
24
Beweis.
[zu Lemma4 ] [29]
Betrachte die Abbildung
Zn→Zn
k,
(x1, x2, . . . , xn)→(x1mod k, x2mod k, . . . , xnmod k).
Da |
Zn
k
|=k
n
und |B| > k
n
gilt, gibt es x, y
∈
B, die denselben Bildpunkt haben.
D.h. es gilt x - y = kv für einen von 0 verschiedenen Vektor v mit ganzzahligen
Koordinaten. Da B konvex ist, gehören dann aber die k + 1 auf einer Gerade
liegenden Punkte y, y + v, y + 2v, ..., y + kv = x ebenfalls zu B.
ut
Mit Hilfe dieses Lemmas kann nun Satz 2 bewiesen werden.
Sei
υ
ein akzeptierendes Blatt. Da L keine Progression der Länge k+1 enthält,
gibt es auch in
c(υ)
keine Progression der Länge k+1. Daher enthält auch
#Pυ∩Z
d+1
keine Progression der Länge k+1. Aus Lemma 4 und Lemma 7
folgt, dass
#c(υ) = #Pυ∩Z
d+1
≤k
d+1
gilt. Da T höchstens 2
D
akzeptierende
Blätter hat, hat L höchstens
2D·k
D+1
Elemente, d.h.
n≤2D·k
D+1
.
⇔D≥log n−log k
log k+ 1
Hieraus folgt unmittelbar die angegebene untere Schranke.
ut
4 Beweise im Fall n> 1
Dieses Kapitel folgt den Ausführungen in [25]. Die dort für den Spezialfall n=2
durchgeführten Beweise werden verallgemeinert für den Fall n
≥
2.
4.1 Operationsmengen mit
DIVc
Dieser Abschnitt enthält die Beweise zu Theorem 2 und die aus dem Theorem
folgenden allgemeinen unteren Schranken.
Beweis.
[von Theorem 2 a)]
⇐
" Sei
Zn
die disjunkte Vereinigung endlich vieler
a
-Gitter
aZn+¯
b,¯
b∈
{0, . . . , a −1}n
. Auf jedem dieser Gitter kann
L
durch einen
{+,−}
bzw.
25
{+,−,∗}
-CT erkannt werden. Der folgende Algorithmus mit
{+,−,DIVc}
bzw.
{+,−,∗,DIVc}
als Operationsmenge erkennt
L
.
Entscheide, in welchem Gitter
aZn+¯
b
die Eingabe
x
liegt. Der Startwert
¯
b
des
Gitters wird durch
bi=xi−(xiDIVca)·a
für
i= 1, . . . , n
berechnet. Dies geht
ohne Multiplikation, da
a
eine Konstante ist.
Für
¯x∈aZn+¯
b
entscheide mit dem zugehörigen
{+,−}
-CT bzw.
{+,−,∗}
-
CT, ob
¯x∈L∩(aZn+¯
b)
gilt.
⇒
" Ich führe den Beweis für
S={+,−,∗,DIVc}
. Der Beweis für
S=
{+,−,DIVc}
ist analog. Sei
D
ein
{+,−,∗,DIVc}
-CT, der
L
erkennt. Ziel
ist es, von der Wurzel zu den Blättern jeden Knoten
v
mit einer
DIVc
Operati-
on durch einen MB-Knoten zu ersetzen. Verzweigt wird an diesen Knoten nach
allen möglichen Ergebnissen
(x1mod a, . . . , xnmod a)∈ {0, . . . , a−1}n
für ei-
ne Konstante
a∈N
. Die Ersetzung des Berechnungsbaumes mit der Operation
DIVc
durch einen MB- CT wurde im eindimensionalen Fall in [22] eingeführt.
Sei
v
der erste Berechnungsknoten von der Wurzel zu einem Blatt, an dem die
Funktion
DIVc
benutzt wird. Angenommen, es wird
f(x) DIVca
b
berechnet,
wobei
f
auf dem Weg zu
v
berechnet wurde. Da
v
der erste Knoten auf dem
Weg mit
DIVc
ist, ist
f
ein Polynom mit rationalen Koezienten.
k∈N
sei
so gewählt, dass
k·f
ganzzahlige Koezienten hat. Ersetze
v
durch einen
MB-Knoten, bei dem nach den Ergebnissen von
(x1mod ka, . . . xnmod ka)
verzweigt wird.
Lemma 5.
Für Eingaben auf dem Gitter
kaZn+c
mit
c∈ {0, . . . , ka −1}n
,
kann man
f(x) DIVca
b
durch
b
af(x)−l
ka
, mit einer von
c
abhängigen Konstan-
ten
l
ersetzen.
Beweis.
[von Lemma 5]
Für lineare Funktionen und Polynome über
Z
ist
b·f(x) mod a
für
ximod a=
ij
,
i= 1, ..., n
,
ij∈ {0, ..., a −1}
eine Konstante
ci1,...,in
für jedes
(i1, ..., in)∈
{0, ..., a −1}n
.
26
Da
f(x) DIVca
b=b·f(x) DIVca=b
af(x)−b·f(x) mod a
a
an dem mit
ximod a=ij
,
i= 1, ..., n
,
ij∈ {0, ..., a −1}
beschrifteten Zweig gilt, kann nach diesem Zweig
f(x) DIVca
b
durch
b
af(x)−ci1,...,in
ka
ersetzt werden.
Für
b·f(x)∈Q[x] \Z[x]
sei k der Hauptnenner der Koezienten von
b·
f(x)
, dann ist
k·b·f(x)∈Z[x]
und damit ist wie oben
f(x) DIVca
b
durch
b
af(x)−ci1,...,in
ka
nach dem mit
ximod ka =ij
,
i= 1, ..., n
,
ij∈ {0, ..., ka −1}
beschrifteten Zweig substituierbar.
ut
Im Folgenden wird
f(x) DIVca
b
durch einen MB-Knoten vom Grad
(ka)n
er-
setzt. Die Zweige sind Kopien des Teilbaumes von
D
mit der Wurzel
v
, bei dem
DIVc
am Knoten
v
durch
b
af(x)−l
ka
wie im obigen Lemma ersetzt wird. Wenn
diese Ersetzungen von der Wurzel zu den Blättern für alle
DIVc
- Operationen
in dem Baum durchgeführt werden, erhält man einen Berechnungsbaum ohne
DIVc
, aber mit MB- Knoten, der
L
erkennt.
Um zur gewünschten Charakterisierung zu gelangen, kann hier festgestellt wer-
den, dass man einen
{+,−,∗}
-CT erhält, wenn man an den MB- Knoten jeweils
nur einen Ast wählt, d.h. wenn die Eingabemenge auf den Durchschnitt der zu-
gehörigen Gitter beschränkt wird. Da dieser Durchschnitt wiederum ein Gitter
ist und man diese erhaltenen Gitter als ein weiteres Gitter mit gemeinsamer
Schrittweite angeben kann, folgt Theorem 2 a).
Theorem 2 b) folgt unmittelbar, denn die Tiefe ändert sich nicht, da jeder
DIV- Berechnungsknoten durch einen MB- Knoten ersetzt wird und in dem
neu entstandenen
S−{DIVc}−CT
jeweils nur ein Ast ausgewählt wird.
Um Theorem 2 c) zu beweisen, muss zusätzlich noch die Schrittweite a der
Gitter analysiert werden. Da nur die Operationen
{+,−,∗}
zur Verfügung
stehen, sind die Konstanten ganzzahlig. In der Tiefe t sind die durch
{0,1}
erzeugten Konstanten kleiner gleich
22t
, somit ist auch die Schrittweite in der
Tiefe t höchstens
22t
. Um den Durchschnitt aller Gitter entlang aller Pfade
zu bilden, wird höchstens das Produkt all dieser Schrittweiten berechnet. Die
Schrittweite für den Durchschnitt der Gitter entlang eines Pfades ist kleiner
27
gleich
T−1
Y
t=0
22t≤22T
und da es höchsten
2T
Blätter gibt, ist die Schrittweite
höchstens
22T2T
= 222T
.
ut
Beweis.
[von Korollar 1]
Das Korollar folgt aus Theorem 2 b) und einem Ergebnis in [42] von An-
drew YAO. Er zeigt, dass Michael BEN-ORs untere Schranke über die Anzahl
der Zusammenhangskomponenten in [12] über
{+,−,∗, /}
-CTs auch für einige
Sprachen gilt, die nur ganzzahlige Eingaben erlaubt. Der dort geführte Beweis
gilt analog für Eingaben aus einem Gitter
aZn
mit einem beliebigen
a∈N
.
So erhält man die unteren Schranken aus Korollar 1 durch Anwendung von
Theorem 2 b).
ut
4.2 Operationsmenge
{+,−,∗c,DIV}
Dieser Abschnitt enthält den Beweis zu Theorem 3 und Korollar 2.
Beweis.
[von Theorem 3 a)]
Sei
β
irrational,
v
der erste Knoten mit einer
DIV
-Operation auf dem Weg
von der Wurzel zu einem Blatt in einem
{+,−,∗c, DIV }
-CT
D
. Da nur die
Multiplikation mit Konstanten und nicht die allgemeine Multiplikation zur
Operationsmenge gehört, sind die auf dem Weg berechneten Funktionen lineare
Funktionen. An dem Knoten
v
wird
f(¯x) DIV g(¯x)
berechnet mit
f(¯x) = a1x1+
... +anxn+an+1
,
g(¯x) = b1x1+... +bnxn+bn+1
,
ai, bi∈Q, i = 1, ..., n + 1
.
Falls
b1= 0, ..., bn= 0
, wird
f(¯x) DIV bn+1
berechnet, d.h. es wird nur
DIVc
benötigt.
In den anderen Fällen soll wie im folgenden Lemma die Berechnung an dem
Knoten
v
durch endlich viele Verzweigungen ersetzt werden.
Lemma 6.
Sei
β
irrational,
f, g :Zn→Z
seien lineare Funktionen mit
rationalen Koezienten,
g
nicht konstant, dann gibt es
c1< β < c2
, so dass
f(¯x) DIV g(¯x)
nur endlich viele Werte für Eingaben aus
P={(¯x)∈Zn, c1≤
xi+1
xi≤c2, i = 1, ..., n −1}
annimmt.
28
Beweis.
[von Lemma 6]
Da g nicht konstant ist, gibt es ein
j∈ {1, ..., n}
, so dass
bi= 0
für
i= 1, .., j−1
und
bj6= 0
. Seien
c1, c2∈Q, c1< β < c2
so gewählt, dass
bj+bj+1γj+1...+bnγn6=
0
für jedes
γk∈[c1, c2]
. Dies ist möglich, da
β
irrational ist. Wenn für Eingaben
aus
P
die Variablen
xk
durch
γkxj, γk∈[c1, c2]
ersetzt werden, erhält man
f(¯x) DIV g(¯x)
= ((a1x1+... +aj−1xj−1)+(aj+aj+1γj+1 +... +anγn)xj+an+1)
DIV ((bj+bj+1γj+1... +bnγn)xj+bn+1) =
Werden nun für Eingaben aus
P
die Variablen
xk
durch
γ0
kx1, γ0
k∈[c1, c2]
ersetzt, erhält man
((a1γ0
1+... +anγ0
n)x1+an+1)DIV(bj+bj+1γ0
j+1... +bnγ0
n)x1+bn+1)
Durch die Wahl von
c1, c2
, ist der obige Divisor von 0 verschieden, und sowohl
Dividend als auch Divisor sind auf P beschränkt. Daher nimmt
f(¯x) DIV g(¯x)
nur endlich viele Werte für Eingaben aus
P
an.
ut
Man kann nun nach Lemma 6 von oben nach unten jede
DIV
-Operation und
nach Lemma 5 jede
DIVc
-Operation ersetzen. Damit ist Theorem 3 a) bewie-
sen.
Da die Konstanten
c1, c2∈Q, c1< β < c2
so gewählt werden können, dass
f(¯x) DIV g(¯x)
nur konstant viele Werte annimmt, ist die Tiefe des
{+,−,∗c}
-
CT
O(T)
, wenn T die Tiefe des
{+,−,∗c,DIV}
-CT
.
Damit folgt Theorem 3 b).
Um Theorem 3 c) zu beweisen, werden die Konstanten genauer abgeschätzt.
In der Tiefe t sind die Konstanten
aj
und
bj
kleiner gleich
22t
und damit sind
die Konstanten, die
f(¯x) DIV g(¯x)
ersetzen, kleiner gleich
5·22t
. Daher sind
auch alle Konstanten in dem
{+,−,∗c,DIVc}
-CT nach Substitution der DIV-
Knoten kleiner gleich
222T
.
Die Schrittweite in dem
{+,−,∗c}
-CT ist somit
kleiner gleich
223T
.
29
Wird wie in Teil a) für Eingaben aus
P
die Variable
y
durch
γx, γ ∈[c1, c2]⊂
1
2,2
ersetzt, gilt
dγ +e6= 0
und
f(¯x) DIV g(¯x) = ((aγ +b)y+c) DIV ((dγ +
e)y+h)
. Die Dierenz zwischen den Polstellen zweier solcher Funktionen f und
f' mit Koezienten
≤222T
ist
≥222T2= 222T+1
(*)
.
Wird
γ
so eingeschränkt,
dass
c2−c1≥1/222T+4
(**) gilt, dann nimmt
f(¯x) DIV g(¯x)
nur 2 Werte an.
Da dieser
{+,−,∗c,DIVc}
-CT nun
22T+1
(***) Blätter hat, folgt aus (*), (**),
(***) die Abschätzung für
c2−c1≥1
2·22T+1 ·222T+4 ·222T+1 ≥1
223T.
ut
Beweis.
[von Korollar 2]
Sei
P={(x, y)∈N2, k1y < x < k2y, ki∈Q,Nenner der ki≤222T}
, p sei eine
Primzahl
p≤222T+ 1
und p teilt nicht die Schrittweite a des Gitters.
Betrachte das Gitter, das den Punkt (p,0) enthält. Dann gehören alle Punkte
(k1al +p, al)
, bei denen l Vielfache des Nenners von
k1
sind, ebenfalls zum
Gitter, d.h.
l=k1·l0
.
Wird
l0
von p geteilt, teilt p auch den
ggT(k1al +p, al)
und wird
l0
nicht von
p geteilt, gilt
ggT(k1al +p, al) = 1
.
Für
n= 222T+3
sind auf einem Geradenabschnitt in
P∩{(0, p) + (aZ)2}222T
Punkte (x,y), bei denen abwechselnd
ggT(k1al +p, al)=1
und
ggT(k1al +
p, al)6= 1
gilt. Daher ist die Tiefe eines
{+,−}
-CT auf diesem Gitter mindes-
tens
log 222T =1
8log 222T+3 =1
8log (n).
Da nach Theorem 3 b) die Tiefe
des
{+,−}
-CT
O(T)
ist, wenn T die Tiefe des
{+,−, DIV }
-CT ist, ist T
ebenfalls
Ω(log n)
.
ut
4.3 Operationsmenge
{+,−,∗,DIV}
Dieser Abschnitt enthält die Beweise zu Theorem 4 und die daraus folgende
spezielle untere Schranke in Korollar 2.
Folgende Bezeichnungen aus [27] für Polynome in 2 Variablen werden erweitert
auf Polynome in n Variablen.
30
Der
Grad
degxiP
, eines Polynoms
P(x1, . . . , xn)
in einer Variablen
xi
ist der
maximale Exponent von
xi
, der in einem Monom von
P(x1, . . . , xn)
vorkommt.
Der
Maximalgrad
maxdeg P ist das Maximum der Grade
degxiP
, nicht zu
verwechseln mit der klassischen Denition des Grades (des Totalgrades) eines
multivariaten Polynoms.
Die
Höhe
ht(P) von P ist das Maximum der Absolutbeträge der Koezienten
von P und das
Gewicht
wt(P) von P ist die Summe der Absolutbeträge von P.
Es wird noch die Denition einer lexikographischen Ordnung auf der Menge
der Polynome benötigt.
Denition 2.
Für zwei Monome
cxi1
1···xin
n
und
dxj1
1···xjn
n
gilt
cxi1
1···xin
ndxj1
1···xjn
n
, falls
1)
i1> j1
oder
2)
es ein
k∈ {1, . . . , n}
gibt mit
il=jl
für l < k und
ik> jk
oder
3)
il=jl
für alle
l∈ {1, . . . , n}
und
|c|>|d|
Ein Polynom ist in
Normalform
, falls die Darstellung minimal bezüglich der
Zahl der Monome ist und diese Monome bezüglich obiger Ordnung absteigend
sortiert sind.
Das erste Monom in der Normalform eines Polynoms
P(x1, . . . , xn)
heiÿt
Leit-
monom
von
P(x1, . . . , xn)
und der Koezient dieses Monoms heiÿt
Leitkoe-
zient
von
P(x1, . . . , xn)
.
Für zwei Polynome
P(x1, ..., xn)
und
Q(x1, ..., xn)
gilt
P(x1, ..., xn)Q(x1, ..., xn)
,
falls in den Normalformen dieser beiden Polynome für ein i > 1 das (i-te Mo-
nom von P)
(i-te Monom von Q) ist und alle vorhergehenden Monome gleich
sind.
Lemma 7.
Zu jedem Polynom
P(x1, . . . , xn)
gibt es positive ganze Zahlen
π1(P)
und
π2(P)
, so dass für alle
¯x∈Nn
mit
x1> xπ1(P)
i
und
xi> π2(P)
das Vorzeichen von
P(x1, . . . , xn)
mit dem Vorzeichen des Leitkoezienten
von
P(x1, . . . , xn)
übereinstimmt. Für
π1(P)
und
π2(P)
gilt
π1(P)≤Pn
i=2 di
+
1 und
π2(P)≤3n−1
qM
L
, wobei L der Leitkoezient von P, M die Höhe von P
und
di
der Grad von P in
xi
ist.
31
Beweis.
Sei
P(x1, . . . , xn) =Σd1
i=0fi(x2, . . . , xn)xi
1
mit
di= degxiP
Behauptung 1
|P(x1, . . . , xn)−Lxi1
1···xin
n|<|L|xi1
1···xin
n
für das Leitmo-
nom
Lxi1
1···xin
n
Beweis.
Sei M die Höhe von P. Es gilt
|P(x1, . . . , xn)−L xi1
1···xin
n|<
M xi1
1Σi2−1
j=0 xj
2···Σin−1
j=0 xj
n+M Σi1−1
j=0 xj
1Σd2
j=0xj
2···Σdn
j=0xj
n≤
2max nM xi1
1Σi2−1
j=0 xj
2···Σin−1
j=0 xj
n,M Σi1−1
j=0 xj
1Σd2
j=0xj
2···Σdn
j=0xj
no
.
Der erste Term beschränkt die Summe über alle Monome, deren Grad in
x1
gleich
i1
und der zweite Term die mit einem Grad in
x1
kleiner
i1
.
Da
|L|xi1
1···xin
n>2M xi1
1Σi2−1
j=0 xj
2···Σin−1
j=0 xj
n
für
xi>3n−1
qM
L
und
|L|xi1
1···xin
n>2MΣi1−1
j=0 xj
1Σd2
j=0xj
2···Σdn
j=0xj
n
für
x1> x
P
n
i=2 di+1
i
und
xi>3n−1
qM
L
gilt, folgt daraus
|P(x1, . . . , xn)−L xi1
1···xin
n|<|L|xi1
1···xin
n
ut
Korollar 4
Zu zwei Polynomen
P(x1, . . . , xn)
und
Q(x1, . . . , xn)
gibt es po-
sitive ganze Zahlen
π1(P−Q)
und
π2(P−Q)
, so dass für alle
¯x∈Nn
mit
x1> xπ1(P−Q)
i
und
xi> π2(P−Q)
entweder
P(x1, . . . , xn)<Q(x1, . . . , xn)
oder
immer
P(x1, . . . , xn)≥Q(x1, . . . , xn)
gilt.
Beweis.
[von Theorem 4 a)]
Sei
D
ein
{+,−,∗,DIV}
-CT, der
L⊆Zn
erkennt.
Um Theorem 4 zu beweisen, sollen wiederum alle Berechnungsknoten
v
mit
DIV
von oben nach unten durch Berechnungsknoten ohne
DIV
ersetzt werden,
in diesem Fall durch rationale Funktionen.
Die folgenden 3 Lemmata erläutern den Ersetzungsvorgang.
32
Lemma 8.
Seien
P, Q ∈Z[x1, . . . , xn]
Polynome
.
Dann gibt es Polynome
A, R ∈Z[x1, . . . , xn]
mit
P(x1, . . . , xn) = A(x1, . . . , xn)·Q(x1, . . . , xn) + R(x1, . . . , xn)
p(x2, . . . , xn),
wobei
Q(x1, . . . , xn) = Σd1
j=1fj(x2, . . . , xn)xj
1
,
δ=max
{-1,
degx1P−degx1Q
},
degx1R < degx1Q
,
degxiR < degxiP+ (δ+ 1) degxiQdegx1A≤max{0, δ}
,
degxiA≤degxiP+δdegxiQ
,
degxip≤(δ+ 1) degxiQ
,
i > 1
.
Beweis.
des Lemmas über Induktion nach
δ
Der Induktionsanfang gilt für
δ=−1
und
A(¯x) = 0
und
R(¯x) = Q(¯x)
Für den Induktionsschritt wird angenommen, dass die Induktionsannahme für
alle
δ < k
für ein
k > −1
gilt und es wird bewiesen, dass sie dann auch für k
gilt.
Seien
P(¯x) =Σd
j=1gj(x2, . . . , xn)xj
1
und
Q(¯x) =Σm
j=1fj(x2, . . . , xn)xj
1
. Dann ist
δ=d−m
Betrachte das Polynom
S(¯x) = fm(x2, . . . , xn)P(¯x)−xk
1gd(x2, . . . , xn)Q(¯x)
Da
degx1S < degx1P
, gilt die Induktionsannahme für die beiden Polynome
S(¯x)
und
Q(¯x)
. Daher gilt nach Induktionsannahme für geeignete
˜
A, ˜
R
mit
ganzzahligen Koezienten,
degx1(˜
R)<degx1(Q)
S(¯x) = ˜
A(¯x)·Q(¯x) + ˜
R(¯x)
(fm(x2, . . . , xn))δ.
Ersetzt man nun für
S(¯x)
obigen Quotienten
P(¯x) =
˜
A(¯x)·Q(¯x)+(fm(x2, . . . , xn))δxk
1gd(x2, . . . , xnQ(¯x) + ˜
R(¯x)
(fm(x2, . . . , xn))δ+1
=A(¯x)·Q(¯x) + ˜
R(¯x)
(fm(x2, . . . , xn))δ+1
33
Für die Grade gelten, da
degxiS≤degxiP+ degxiQ
und
degxi˜
A≤degxiS+
(δ−1) degxiQ
,
degxiA= max{degxi˜
A, δ degxiQ+ degxiP} ≤ degxiP+δdegxiQ,
degx1A= max{degx1˜
A, degx1P−degx1Q} ≤ degx1P−degx1Q.
ut
Lemma 9.
Seien
P, Q ∈Z[x1, . . . , xn]
Polynome
.
Dann gibt es Polynome
A1∈Z[x1, . . . , xn]
und
A2, p ∈Z[x2, . . . , xn]
und Konstanten
π1
und
π2
, so
dass für alle
¯x∈Nn
mit
x1> xπ1
i
,
x1≡cmod p(x2, . . . , xn)
und
xi> π2
P(¯x) DIV Q(¯x) = A1(x1, . . . , xn)
p(x2, . . . , xn)+A2(x2, . . . , xn)
p(x2, . . . , xn)
gilt.
Beweis.
[von Lemma 9]
Nach Lemma 8 gilt
P(x1, . . . , xn) DIV Q(x1, . . . , xn) =
A(x1, . . . , xn)
p(x2, . . . , xn)+R(x1, . . . , xn)
p(x2, . . . , xn)·Q(x1, . . . , xn).
Nun kann gefolgert werden
(i) Sei
k1=Pn
i=2 di+ 1
mit
di=degxi(Q−R)
.
Für
x1> xk1
j
,
j= 2, ..., n
, konvergiert
R(x1,...,xn)
(p(x2,...,xn)·Q(x1,...,xn)
gegen 0, wenn
k(x1, ..., xn)k1
gegen
∞
strebt.
(ii) Sei
c∈Z
fest. Für
x≡cmod p(x2, . . . , xn)
gilt
A(x1,...,xn)
p(x2,...,xn)=A1(x1,...,xn)
p(x2,...,xn)+
A2(x2,...,xn)
p(x2,...,xn)
und
A1(x1,...,xn)
p(x2,...,xn)∈Z
.
(i) folgt direkt aus den Denitionen von
R, p
, und
k1
.
(ii) kann folgendermaÿen festgestellt werden:
34
Sei
x1≡cmod p(x2, . . . , xn)
, d.h.
x1=l·p(x2, . . . , xn) + c
für ein
l∈N
. Dann
gilt
A(x1, . . . , xn)
p(x2, . . . , xn)=
d1,...,dn
X
k1,...,kn=0,
a0
k1,...,kn(x1−c)k1xk2·...
2xkn
n
p(x2, . . . , xn)
=
d1,...,dn
X
k1,...,kn=0,
a0
k1,...,kn(lk1(p(x2, . . . , xn))k1−1·xk2·...
2xkn
n
+
d2,...,dn
X
k2,...,kn=0,
a0
0,k2,...,knxk2·...
2xkn
n
p(x2, . . . , xn)
=: A1(x1, . . . , xn)
p(x2, . . . , xn)+A2(x2, . . . , xn)
p(x2, . . . , xn)
wobei die
a0
k1,...,kn
von
c
abhängige Koezienten sind.
ut
Mit Lemma 9 ist zwar immer noch die ganzahlige Division in dem Ausdruck,
aber nur noch als Quotient zweier Polynome mit n-1 Variablen, d.h. mit einer
Variablen weniger. Wird dieses Lemma 9 nun (n-1)-mal angewendet und in
jedem Durchgang mit einer Variablen weniger im Nennerpolynom, so erhält
man folgendes Lemma
Lemma 10.
Seien
P, Q ∈Z[x1, . . . , xn]
Polynome,
c1, ..., cn∈N
Konstan-
ten
.
Dann gibt es Konstanten
ki, K ∈N
und Polynome
Ai∈Z[x1i, . . . , xn]
,
Pi∈Z[xi+1, . . . , xn]
, i=1,...,n-1 ,
Pn∈Z
, so dass für alle
¯x∈Nn
mit
xi> xki
i+1, xn> K
,
xi≡cimod Pi+1(xi+1, . . . , xn)
P(¯x) DIV Q(¯x) =
n−1
X
i=1
Ai(xi, . . . , xn)
Pi(xi+1, . . . , xn)+An(xn)
gilt.
35
Beweis.
[von Lemma 10]
Nach dem (n-1). Durchgang ist bei dem letzten Summanden noch die DIV-
Operation
n−1
X
i=1
Ai(xi, . . . , xn)
Pi(xi+1, . . . , xn)+A0
n(xn)
Pn−1(xn).
Wie in Lemma 1 gezeigt, kann
A0
n(x) DIV Pn−1(xn)
als Polynom
An(xn)
für
Eingaben
xn≡cnmod Pn
,
xn> K
, für genügend groÿes
K
geschrieben wer-
den.
ut
Jede DIV-Operation in dem CT
D
kann nun durch die Berechnung einer ra-
tionalen Funktion ersetzt werden, wie in Lemma 10 gezeigt.
Wird nun von der Wurzel zu den Blättern jeder DIV- Berechnungsknoten durch
die rationale Funktion als Quotient zweier Polynome mit ganzzahligen Koe-
zienten ersetzt, bei der Addition und Subtraktion zweier rationaler Funktionen
nach der Rechenregel
P
Q+ (−)S
T=PT +(−)SQ
QT
und bei der Multiplikation nach
der Rechenregel
P
Q·S
T=P·S
QT
wiederum als Quotient zweier Polynome mit ganz-
zahligen Koezienten umgeformt, so werden nur Polynome mit ganzzahligen
Koezienten berechnet. Wenn nun an einem Verzweigungsknoten nach
P
Q>0
verzweigt wird, wird für
P > 0
und
Q > 0
oder aber
P < 0
und
Q < 0
der
Zweig für
P
Q>0
ist erfüllt und ansonsten der für
P
Q>0
ist nicht erfüllt
gewählt.
Dies ergibt einen
{+,−,∗}
-CT, der für eine wie in Theorem 4 eingeschränkte
Eingabemenge
L
erkennt. Die Polynome
pi(xi+1, . . . , xn)
sind die Produkte
aller Polynome
Pi
, die als Divisor bei der Ersetzung der DIV-Operationen wie
in Lemma 10 vorkommen.
Beweis.
[von Theorem 2 b)]
Durch Induktion über die Tiefe des Berechnungsbaumes werden die Grade der
rationalen Funktionen
n−1
X
i=1
Ai(xi,...,xn)
Pi(xi+1,...,xn)+An(xn) = S(¯x)
T(¯x)
und die Gröÿe der
ki
abgeschätzt.
36
Behauptung 2
Nach der Substitution der DIV-Operationen in den oberen
t
Levels von
D
sind die Grade der Zähler- und Nennerpolynome der in Lemma 10
denierten rationalen Funktionen
≤22(n−1)(t−1)
.
Beweis.
der Behauptung
Der Induktionsanfang für
t= 1
ist oensichtlich.
Die Induktionsannahme gelte für alle
k < t
.
Bei der Umformung der Berechnungsknoten, die mit
P(¯x)
Q(¯x))
+ (-)
S(¯x)
T(¯x))
beschrif-
tet sind, zu einem Quotienten zweier Polynome verdoppelt sich der Grad der
Polynome höchstens.
Daher müssen nur noch Berechnungsknoten in der Tiefe
t
, die mit
P(¯x)DIVQ(¯x) =
n−1
X
i=1
Ai(xi,...,xn)
Pi(xi+1,...,xn)+An(xn) = S(¯x)
T(¯x)
beschriftet sind, genauer betrachtet werden.
Nach Induktionsannahme gelten dort folgende Ungleichungen:
deg P≤22(n−1)(t−2)
,
deg Q≤22(n−1)(t−2)
und
deg Pi≤22(n−1)(t−2)
.
Nach Lemma 8 gilt für
δ= max
{-1,
degx1P−degx1Q
}
degx1Ai≤max{0, δ} ≤ 22(n−1)(t−2)
und
degxiAj≤degxiP+ (δ+ 1)jdegxiQ
,
degxiPj+1 ≤(δ+ 1)jdegxiQ≤(2δ)j22(n−1)(t−2) j≥i
und
degx1S≤degx1Q≤22(n−1)(t−2)
.
Daher gilt
degxiT≤
n−1
X
j=0
degxiPj+1 ≤22(n−1)(t−2)
n−1
X
j=1
(2δ)j
≤22(n−1)(t−2) (2 ·22(n−1)(t−2) )n≤22(n−1)(t−1)
und ebenso
degxiS≤22(n−1)(t−1)
und
degxiS≤22(n−1)(t−1)
.
Da es höchstens
2t
Knoten gibt, ist der Grad des Produkts dieser Polynome
höchstens
22(n−1)t
.
37
Aus der obigen Induktion und von Lemma 7 und Korollar 4 folgt unmittelbar
ki≤22(n−1)t
.
ut
Das Theorem 4 b) im 2-dimensionalen Fall wird nun benutzt, um die erste
untere Schranke für die mächtige Operationsmenge
{+,−,∗,DIV}
und Kon-
stanten aus
Q
zu beweisen.
Beweis.
[von Korollar 3]
Angenommen ein
({+,−,∗,DIV},Q)
-CT
M
der Tiefe
T
erkennt
Lr
.
Theorem 2 b) besagt, dass es
k2
und ein Polynom
p(y)
vom Grad
≤22T
gibt, so
dass es zu
y∈k2Z
,
x1(y); x2(y)
,
x1(y)< x2(y), x2(y)−x1(y)≤p(y), x1(y)<
r(y)< x2(y)
gibt, so dass
M A ={x1(y), y ∈k2Z}
akzeptiert und
B=
{x2(y), y ∈k2Z}
verwirft, d.h.
r(y)
trennt
A
von
B
.
Für
d≤max{k1,deg(p(y))}
folgt die untere Schranke direkt aus Theorem 4 b).
Für
d > max{k1,deg(p(y))}
erkennt der
({+,−,∗},Q)
-CT
D0
aus Theorem 4 b)
L
auch für Eingaben aus
A∪B
. Daher berechnet
D0
ein Polynom
s(y)
,
das
A
von
B
trennt. Da
s(y)∈ {x1(y), . . . , x2(y)} ⊆ {r(y)−p(y), . . . , r(y) + p(y)}
und
d > deg(p(y))
, hat
s(y)
Grad
d
. Da
D0
nur Polynome vom Grad
O(22T)
berechnet, gilt
d=O(22T)
.
ut
4.4 Separationsresultate
Dieser Abschnitt enthält die Beweise und die fehlenden Sprachen, um die
Sprachklassen zu unterscheiden.
Beweis.
[von Theorem 5]
CC2{+,−}⊂
6=CC2{+,−,∗}
gilt oensichtlich, da bekannterweise
L={(x, y), x2>
y} ∈ CC2{+,−,∗}−CC2{+,−}
.
Die folgenden Unterscheidungen der Sprachklassen folgen bereits aus [22], sie
gelten schon im Fall
n= 1
.
38
CCn({+,−})⊂
6=CCn{+,−,DIVc}
CCn{+,−,DIVc}−CCn{+,−,∗} 6=∅
CCn{+,−,∗}⊂
6=CCn{+,−,∗,DIVc}
Aus Theorem 2 folgt:
CCn{+,−, DIVc}⊂
6=CCn{+,−,∗,DIVc}
.
Das folgende Korollar der Theoreme 4 und 2 beweist die fehlenden Beziehun-
gen.
Korollar 5
a)
{(x, y)∈Z2, x2>2y2} ∈ CC2({+,−,∗})−CC2({+,−,DIV})
b)
{(x, y)∈Z2,(y−1)DIV x−yDIV x < 0} ∈ CC2(
{+,-,
DIV
}
)−CC2({+,−,∗,
DIVc})
"
Beweis.
zu a) durch Widerspruch
Nach der Denition von L gilt
L∈CC2({+,−,∗}
.
Es wird gezeigt, dass unter der Annahme, dass ein
{+,−,DIV}
-CT diese Spra-
che erkennt, sie bereits von einem
{+,−}
-CT erkannt wird.
Nach Theorem 4 gibt es k
1
, k
2
∈Q
, so dass L auf
{(x, y)∈N2|k1y <
x < k2y}∩(aZ)2
, dem Gitter, das den Nullpunkt enthält, bereits durch einen
{+,−}
-CT erkannt wird. Da
√2/∈Q
ist, können k
1
, k
2
∈Q
so gewählt werden,
dass
k1<√2< k2
gilt. Folgendermaÿen wird dann L durch einen
{+,−}
-CT
erkannt: akzeptiere, falls
|x| ≤ k1|y|
, und verwerfe, falls
|x| ≥ k2|y|
.
Für
k1|y|<|x|< k2|y|
entscheide mit dem obigen
{+,−}
-CT, ob
(a|x|, a |y|)∈
L
gilt. Falls ja, akzeptiere, ansonsten verwerfe. Dies ist im Widerspruch zu
L
/∈CC2({+,−}).
zu b) durch Widerspruch
Nach der Denition von L gilt
L∈CC2({+,−,DIV}
.
Annahme L =
{(x, y)∈Z2,(y−1)DIV x −yDIV x < 0} ∈ CC2({+,−,∗,
DIVc})
39
Nach Theorem 2 b) ist der
Z2
endliche disjunkte Vereinigung aner Gitter
und L kann auf jedem dieser Gitter ohne
DIVc
entschieden werden. Dies gilt
insbesondere für das Gitter S, das den Nullpunkt enthält. Nach Theorem 2 b)
gibt es einen
{+,−,∗}
-CT, der L auf
S∩Z2
entscheidet.
Da S den Nullpunkt enthält, ist
S= (a, 0)Z+(0,a)Z
.
Sei nun (x,y)
∈S,
d.h. (x,y)=(ax',ay'). Da
(y−1)DIV x−yDIV x < 0⇔
ymod x= 0
, wird
ay0mod ax0= 0 ⇔y0mod x0= 0
ohne
DIV
entschieden.
Dies ist im Widerspruch zu L
/∈CC2({+,−,∗}).
ut
5 Polynomauswertung
Diese beiden folgenden Kapitel entsprechen weitestgehend dem Aufsatz von
Martin ZIEGLER und mir in [26]. Anders als in den Kapiteln zu Berechenbar-
keits - und Komplexitätsbetrachtungen von S-CTs werden in den Kapiteln 5
und 6 die einzelnen Ergebnisse direkt mit den dazugehörigen Beweisen vorge-
stellt. Es wird in diesen beiden Kapiteln vorausgesetzt, dass auÿer, wenn ein
Algorithmus explizit als SLP angegeben wird, bei den vorgestellten Algorith-
men
≤
zur Operationsmenge gehört.
Aus der unteren Schranke über
{+,−,∗,DIV}
ergibt sich eine doppelexponen-
tielle Lücke zwischen oberer Schranke zur Polynomauswertung über
{+,∗}
und
unterer Schranke zur Polynomauswertung über
{+,−,∗,DIV}
. Daher stellt
sich in diesem Kapitel die Frage, ob die Polynomauswertung mit zusätzlichen
nicht klassischen Grundoperationen beschleunigt werden kann, ob z.B. Po-
lynome vom Grad d über
{+,−,∗,DIV}
in
o(d)
berechnet werden können.
Da gerade die Polynomauswertung in den Computerwissenschaften an vielen
Stellen benutzt wird, z.B. bei Splines oder Reed-Solomon-Codes, ist deren Be-
schleunigung wünschenswert.
5.1 Polynome mit einer Variablen
Das klassische Verfahren zur Polynomauswertung bei univariaten Polynomen
ist das Hornerschema und benötigt
O(d)
Schritte, wenn d den Grad des Po-
40
lynoms bezeichnet. Dieses Verfahren ist in vielen Fällen mit den Operationen
{+,−,∗}
optimal [8, Theorem 6.5]
.
Dies gilt nicht für ganzzahlige Polynome
mit im Verhältnis zum Grad kleinen Koezienten.
Theorem 6.
Gegeben sei ein Polynom
P(x) = Σd−1
n=0anxn∈Z[x]
mit
a0, ..., ad−1
∈Z
und
|an|< P
. Dann kann P(x) in
O(d/logpd)
Schritten über
{+,∗,}
be-
rechnet werden.
Beweis.
Da P(x) als Dierenz zweier Polynome mit positiven Koezienten
betrachtet werden kann, sei o.B.d.A.
P(x)∈N[x]
. Zerlege P in
dd/ke
Polynome
qi
vom Grad kleiner gleich k. Wie dieses k in Abhängigkeit vom Grad d und
der maximalen Gröÿe der Koezienten P zu wählen ist, wird später gezeigt.
Es gibt höchstens P
k
verschiedene Polynome vom Grad kleiner k und mit
Koezienten aus {0,1,..,P-1}. Mit dem Hornerschema wird jedes dieser P
k
verschiedenen Polynome an der Stelle
x∈Z
in
O(k)
Schritten berechnet, d.h.
es werden für alle P
k
verschiedenen Polynome insgesamt
O(k ·Pk)
Schritte zur
Auswertung benötigt.
Danach wird das Polynom
Σdd/ke
i=0 qi(x)·Yi
an der Stelle
Y=xk
mit dem
Hornerschema in
O(d/k)
Schritten berechnet und erhält so P(x)
.
Es werden zur Berechnung also
O(d/k+k·Pk)
Schritte benötigt.
Für k:= log
p
d
-
2 log
p
log
p
d ist
O(d/k+k·Pk) =
O(d/(log
p
d−2 log
p
log
p
d) + (log
p
d−2 log
p
log
p
d) ·Plog
p
d−2 log
p
log
p
d)
=O(d/logpd)
ut
Wird als weitere Operation die ganzzahlige Division hinzugenommen, so kann
die Berechnung eines Polynoms über einem endlichen Bereich beschleunigt
werden.
Satz 3
Zu
X∈N
und
Z > max0≤x≤XP(x)
speichere
Y:= PX
x=0 Zx·P(x)
.
Folgendermaÿen wird für
0≤x≤X
, aus den gespeicherten Werten
P(x)
41
berechnet: durch wiederholtes Quadrieren in
O(log x)
Schritten berechne
Zx
.
Es gilt
P(x) = (YDIV Zx)mod Z
.
Die Laufzeit ist unabhängig von
deg(P)
und logarithmisch in
x
.
Katharina Lürwer-Brüggemeier/Martin Ziegler 8
YP(0)P(1)P(2)….P(x-1)P(x)P(x+1)…P(X)
ZZ2
Zx-1
Zx
Zx+1
ZX
Y div ZxP(x)P(x+1)…P(X)
ZZ2
ZX-x
Ymod Z P(x)
Abbildung 6.
Berechnungen im Beweis von Satz 3
Aber auch die Abhängigkeit von der Eingabe ist zur Berechnung nicht not-
wendig [6].
Theorem 7.
Ein Polynom
P(x)∈Z[X]
kann über einer endlichen Menge
D⊂Z
in 15 Schritten (unabhängig von P und D) berechnet werden.
Beweis.
Für negative Argumente
x∈Z
berechne P(-x). Da jedes Polynom mit
ganzzahligen Koezienten als Dierenz zweier Polynome mit natürlichen Ko-
ezienten dargestellt werden kann, wird o.B.d.A. der Beweis für Polynome mit
natürlichen Koezienten und
D⊂N
geführt.
Sei
P(x) = Pd
i=0 pixi
,
pi∈N
,
degp=d
und
wt(P)≤P
.
Behauptung 3
Für
Z > max{Xd·P, (Xd+1 + 1) ·X}
berechnet der folgende
Algorithmus p(x) für
|x| ≤ X=max{|x|, x ∈D}
.
Z, Z
d
und p(Z) sind Konstanten und werden vorher berechnet und gespeichert.
g=Zd+1DIV (Z−x)
2 Operationen
h=p(Z)·g
1 Operation
a=hDIV Zd
1 Operation
b=amod Z=a−(aDIV Z)·Z
3 Operationen
42
Katharina Lürwer-Brüggemeier/Martin Ziegler 8
Z2d
*P(Z) pd
pd-1
pd-2
….p2
p1
p0
Zo
Zd
gxd
Xd-1
Xd-2
….X²x1
Zo
Z1
Z2
Zd-2
Zd-1
Zd
=p0 xd
p1 xd+poxd-1
…po+ p1 x +…. +pd-1 xd-1 + pdxd
…pd
Abbildung 7.
Berechnungen in Bshoutys Algorithmus
Beweis.
Um die Korrektheit des Algorithmus zu beweisen, folge ich dem Be-
weis von Nader BSHOUTY [6].
Für x
∈
{1,...,X} gilt b=p(x)
(*)
g(x) = Zd+1
Z−x=Zd
1−x
Z=jZd·P∞
i=0 x
Zik=
d
X
i=0
Zd−i·xi
| {z }
+
∞
X
i=d+1
Zd·x
Zi
| {z }
=Pd
i=0 Zd−i·xi,
∈N=xd+1
Z−x<1
da laut Voraussetzung
Z > (Xd+1 + 1) ·X
gilt.
h(x) = p(Z)·Pd
i=0 Zd−i·xi=
Pd
j=0 pj·Zj·
d
X
i=0
Zd−i·xi=
d
X
i=0
(
d
X
j=0
pj·Zd−i+j)·xi
a(x) = h(x) DIV Zd=
d
X
i=0
(
d
X
j=0
pjZd−i+j)·xiDIV Zd=
$d
X
i=0
(
d
X
j=0
pjZ−i+j)·xi%=
d
X
i=0
(
d
X
0≤i≤j
pj·Z−i+j)·xi.
43
Da für
i6=j
die Summanden ganzzahlig sind und laut Voraussetzung
Z >
Xd·wt(P)
ist, gilt
b(x) = a(x) mod Z=Pd
j=0 pj·xj=p(x)
ut
Korollar 6
Mit der Operationsmenge
{+,−,∗c,DIV}
kann jede endliche Fol-
ge
y0, y1, . . . , yN
(oder formaler die Abbildung
{0,1, . . . , N} 3 n7→ yn
) in
konstanter Zeit
unabhängig
von (der Länge N) der Folge erkannt werden.
Beweis.
Betrachte das Interpolationspolynom
p∈Q[X]
vom Grad
≤N+ 1
,
so dass
p(n) = yn
,
n∈ {0, . . . , N}
gilt. Wähle
M∈N
, so dass
M·p∈Z[X]
.
Nach Theorem 7 kann
n7→ M·p(n)
in konstanter Zeit berechnet werden. Nach
ganzzahliger Division durch
M
erhält man
p(n)
.
ut
Aus diesem Korollar folgt für eine Sprache
L⊆Z
ebenfalls Bemerkung 2,
wenn es auf die charakteristische Folge
(y0, . . . , yN)
von
L
, die durch
yn:= 1
für
n∈L
und
yn:= 0
für
n6∈ L
deniert ist, angewendet wird.
Wie der nächste Abschnitt zeigt, gelten diese Aussagen auch für Folgen
( ¯y0,..., ¯yN)
in
Zd
und für endliche Sprachen
L⊆Zd
für ein festes
d
.
5.2 Polynome mit mehreren Variablen
Dieser Algorithmus von Nader BSHOUTY wird erweitert zu einem Algorith-
mus für multivariate Polynome.
Theorem 8.
Ein Polynom
P(x1, . . . , xn)∈Z[x1, . . . , xn]
kann über einer end-
lichen Menge
D⊂Zn
in
O(n)
Schritten unabhängig von p und D mit der
Operationsmenge
{+,−,∗,DIV}
berechnet werden.
Beweis.
Um nur Polynome für nicht-negative Argumente
¯x = (x1,...,xn)∈Nn
zu berechnen, wird zu einer Eingabe
¯x ∈Zn
zunächst
44
in
O(n)
Schritten entschieden, welches der 2
n
im Allgemeinen verschiedenen
Polynome
P(±x1,±x2,...,±xn)
an der Stelle
(|x1|,|x2|,...,|xn|)
berechnet
werden muss, um den Wert von
P(¯x)
zu berechnen.
Sei o.B.d.A.
P(¯x) = Σd1,...,dn
i1,...,in=0pi1,...,inxi1
1···xin
n∈N[x1,...,xn]
, andernfalls be-
trachte wie im univariaten Fall , falls
P(¯x)∈Z[x1,...,xn]
,
P(¯x)
wiederum als
Dierenz zweier Polynome mit natürlichen Koezienten.
Behauptung 4
Der folgende Algorithmus berechnet
f(¯x) = P(¯x)
für
¯x∈D
,
falls
Z > dn·wt (P)·max {xi;i= 1, ..., n}nd
mit
d:= max {di;i=1, ..., n}+ 1
,
di= degxiP(¯x)
gilt.
g(¯x) = Qn
i=1 ZdiDIV (Zdi−1−xi)
3n Operationen
h(¯x) = P(Z, Zdi, ..., Zdn−1)·g(¯x)
1 Operation
k(¯x) = h(¯x) DIV Zdn−1
1 Operation
f(¯x) = k(¯x) mod Z=k(¯x) −(k(¯x) DIV Z)·Z
3 Operationen
Beweis.
der Behauptung
Es gilt die Gleichung (*) auf Seite 42
jZd
Z−xk=Pd−1
i=0 Zd−1−i·xi
im univariaten
Fall für alle
Z > Ω(xd)
.
Wird diese Gleichung auch auf x
2
und
Z2:= Zd
angewendet, führt dies zur
folgenden Gleichung
Zd2DIV (Zd−x2)·ZdDIV (Z−x1)=
d−1
X
i2=0
Zd(d−1−i2)·xi2
2·
d−1
X
i1=0
Zd−1−i1·xi1
1=
Xd−1
i1,i2=0 Zd2−1−(di2+i1)·xi2
2·xi1
1.
Induktiv für
i= 1, ..., n
wird diese Gleichung auf
xi
und
Zi:= Zdi−1
angewen-
det und man erhält in
O(n)
Schritten über
{+,−,∗,DIV}
g(¯x) =
n
Y
i=1
ZdiDIV (Zdi−1−xi) =
45
Xd−1
i1,...,in=0 Zdn−1−(dn−1in+···+di2+i1)·xin
n···xi2
2·xi1
1
Diese Summe wird nun mit der Konstanten
P(Z, Zd, Zd2, . . . , Zdn−1) = Xd−1
i1,...,in=0 p¯
i·Zi1+di2+d2i3+···+dn−1in
multipliziert.
h(¯x) = P(Z, Zdi, ..., Zdn−1)·g(¯x)
d−1
X
k1,...,kn=0
p¯
kZk1+dk2+······+dn−1kn·
d−1
X
i1,...,in=0
Zdn−1·Z−i1···Z−dn−1in·xi1
1···xin
n
d−1
X
k1,...,kn,i1,...,in=0
p¯
kZdn−1·Z(k1−i1)···Z(dn−1kn−dn−1in)·xi1
1···xin
n
Wie im Fall einer Variablen wird wiederum durch Anwendung der ganzzahligen
Division und anschlieÿender Restbildung P(x) extrahiert.
k(¯x) = h(¯x) DIV Zdn−1=
(
d−1
X
k1,...,kn,i1,...,in=0
p¯
kZdn−1·Z(k1−i1)···Zdn−1(kn−in)·xi1
1···xin
n)DIV Zdn−1=
$d−1
X
k1,...,kn,i1,...,in=0
p¯
k·Z(k1−i1)···Zdn−1(kn−in)·xi1
1···xin
n%=
$d−1
X
k1,...,kn,i1,...,in=0
p¯
k·ZΣn
i=0(kj−ij)dj−1·xi1
1···xin
n%=
Für
Σn
i=0(kj−ij)dj−1≥0
sind die Summanden ganzzahlig.
Für
Σn
i=0(kj−ij)dj−1<0
ist die Summe dieser Summanden kleiner 1
,
da
Z >
dn·wt(P)·max {xi;i= 1, ..., n}nd
gilt.
46
=
d−1
X
k1, ..., kn,i1, ..., in= 0
Σn
i=0(kj−ij)dj−1≥0
p¯
k·ZΣn
i=0(kj−ij)dj−1·xi1
1···xin
n
f(¯x) = k(¯x) mod Z=
(
d1,...,dn
X
k1,...,kn=0,
dn,...,d
X
i1, ..., in= 0
Σn
i=0(kj−ij)dj−1≥0
p¯
k·ZΣn
i=0(kj−ij)dj−1·xi1
1···xin
n)mod Z
Falls
kn< in
ist, gilt
Σn
i=0(kj−ij)dj−1<0
für
j= 1, ..., n
, da
d > kj
gilt. Dies
ist im Widerspruch zu
Σn
i=0(kj−ij)dj−1≥0
.
Falls
kn> in
ist, teilt
Z
die Summanden
p¯
k·ZΣn
i=0(kj−ij)dj−1·xi1
1···xin
n
Daraus kann gefolgert werden, dass
p¯
k·ZΣn
i=0(kj−ij)dj−1·xi1
1···xin
nmod Z6= 0
nur für
kn=in
gilt.
In der gleichen Weise wird
kj=ij
induktiv für
j=n−1
bis
j= 1
gezeigt.
Nach Denition von Z gilt nun
d1,...,dn
X
k1,...,kn=0,
p¯
kxk1
1···xkn
n=P(¯x).
ut
5.3 Polynomauswertung mit bitweiser Konjunktion
Im Gegensatz zum Hornerschema erfolgt die Polynomauswertung mit dem Al-
gorithmus von Nader BSHOUTY und dessen Erweiterung auf multivariate
47
Poynome nur über
endliche
Eingabebereiche. Für ein im Verhältnis zur Ein-
gabe genügend groÿes Z, so dass es bei dem Produkt von
Zd+1DIV (Z−x)
und P(Z) nicht zu unerwünschten Überlappungen kommt, wurde P(Z) als Kon-
stante vorher gespeichert. Wird die bitweise Konjunktion als weitere Opera-
tion hinzugenommen und das Z im Verhältnis zur Eingabe geeignet gewählt,
lässt sich die Polynomauswertung im Vergleich zum Hornerschema deutlich
beschleunigen.
Satz 4
Sei
p∈N[x]
ein Polynom vom Grad
d
, dann kann
N3x7→ p(x)
in
O(log d)
Schritten über
{+,−,∗,DIV,&}
berechnet werden.
Beweis.
Sei
P(x) = Σd
i=0pixi∈N[x]
mit
pi∈N
und
pi<2l
für
i= 0, ..., d
.
Zu gegebenem
x∈N
berechne durch wiederholtes Quadrieren in
O(log d)
Schritten
Z0:= x
d+2
.
Z:= Z0·Y
mit
Y:= 2l
erfüllt die Bedingungen zu Satz 3.
P(Y) =
d
X
i=0 ,
pi2li =P(2l)
ist für ein festes Polynom eine Konstante und kann
vorab gespeichert werden.
W:=
d
X
i=0 ,
Z0i
und ebenso
V:=
d
X
i=0 ,
(Z0·Y)i
werden in
O(log d)
Schritten
berechnet, indem zunächst wiederum durch sukzessives Quadrieren
Z0d+1
bzw.
(Z0·Y)d+1
berechnet wird und V bzw. W werden nach der folgenden Gleichung
W:=
d
X
i=0 ,
Z0i=Z0d+1DIV (Z0−1)
bzw.
V:=
d
X
i=0 ,
(Z0·Y)i= (Z0·Y)d+1DIV (Z0·
Y−1)
berechnet.
In der folgenden Abbildung ist zu sehen , wie P(Z) aus U, V, W und Y mit der
bitweisen Konjunktion als weiterer Operation nach den obigen Abschätzungen
in
O(log d)
Schritten als
P(Z) = (P(Y)·W)&((Y−1) ·V)
berechnet wird.
48
Abbildung 8.
Berechnungen im Beweis von Satz 4
P(Y)·W=
d
X
i=0
d
X
j=0
pi2liZ0j=
d
X
i=0
d
X
j=0
pi2liZ0j
(Y−1) ·V=
d
X
i=0
l−1
X
i=0
(Z0·Y)i2j=
d
X
i=0
l−1
X
j=0
2li+jZ0j
Da
(Y−1)·V
nur Koezienten
6= 0
bei
2li+j
für
i= 0, ..., d
und
j= 0, ..., l −1
hat, sind es genau die Koezienten
pi
in binärer Darstellung für
i= 0, ..., d
,
P(Z) = (P(Y)·W)&((Y−1) ·V)
.
ut
Nach dem obigen Beweis werden die
O(log d)
Schritte benötigt, um durch
wiederholtes Quadrieren
Z0:= x
d+2
und Z
d
zu berechnen. Alle anderen Be-
rechnungen gehen in konstanter Zeit, wenn die Konstanten wie Y
d
oder P(Y)
vorher berechnet werden. Ist x<
O(2d)
können
Z0:= x
d+2
und Z
d
schneller
in
O(log log |x|)
Schritten berechnet werden, wenn nicht x, sondern
2d
und
2d2
sukzessive quadriert werden. In diesem Fall wird auch nicht die Multiplika-
tion, sondern nur die Multiplikation mit Konstanten benötigt.
Korollar 7
Sei
p∈N[x]
ein Polynom vom Grad
d
, dann kann
N3x7→
p(x)
in
O(log log|x|)
Schritten über
{+,−,∗c,DIV,&}
berechnet werden.
49
Ohne Einschränkung kann der Grad des Polynoms als Zweierpotenz vorausge-
setzt werden, da ansonsten das Polynom durch Hinzufügen von Summanden
mit den Koezienten Null erweitert wird. Die Laufzeit in der
O
-Notation
ändert sich nicht dabei. Wird zusätzlich noch das schnellere Quadrieren mit
der ganzzahligen Division aus dem Aufsatz von Yishay MANSOUR, Baruch
SCHIEBER, PrasoonTIWARI [28] verallgemeinert für beliebige positive ganze
Zahlen, erhält man die Zeitabschätzung in Theorem 9 zur Polynomauswertung.
Satz 5
Gegeben seien
a, k ∈N
und eine beliebige ganze Zahl
b≥a2k
, dann
lässt sich
a2k
über
(+,−,∗,DIV)
in
O(√k)
Schritten berechnen.
Beweis.
Zunächst wird
m
mit
k=m2+b
mit
0≤b < 2m+ 1
gesucht. Dies
geht in
O(√k)
Schritten, indem nacheinander
i
für
i= 1, ..., m + 1
quadriert
wird, bis
i2> k
gilt. Da
m=j√kk
gilt, kann durch sukzessives Quadrieren
von
a2m2
in
O(√k)
Schritten
a2k
berechnet werden. Es bleibt zu zeigen, dass
a2m2
in
O(m) = O(√k)
Schritten berechnet werden kann.
Sei
b1,0=ab
. Durch m-faches Quadrieren von
b1,0=ab
erhält man für
i=
1, ..., m
b1,i =b1,i−12= (ab)2i
Sei
b0,0=a
und berechne
b0,i =b1,m mod (b1,0−b0,i−1)
für
i= 1, ..., m
.
Es wird gezeigt, dass
b0,i =a2mi
und daher
b0,m =a2m2
gilt.
Es wird ausgenutzt, dass für
yr<(x−y)
xrmod (x−y) = ((x−y) + y)rmod (x−y) = yr
gilt. Aus
b1,m = (ab)2m
und
b1,0−b0,i−1> a2m2
folgt daher
b0,i =b2m
0,i−1=a2mi
.
ut
Ohne ganzzahlige Division benötigt man für die
2
k
. Potenz einer natürlichen
Zahl durch wiederholtes Quadrieren
O(k)
Schritte. Die zusätzliche Eingabe
von dem
b
kann gewissermaÿen als 'Katalysator' zur Beschleunigung betrachtet
werden, vergleiche Abschnitt 6.3.
50
Theorem 9.
Ein Polynom
P∈Z[x]
vom Grad
d
kann an der Stelle
x∈Z
in
O(min{log d,log log |x|})
Schritten über
{+,−,∗,DIV,&}
berechnet werden.
Ist zusätzlich eine natürliche Zahl
y≥ |x|d2
gegeben, kann
P(x)
über
{+,−,∗,
DIV,&}
in
O(pmin{log d, log log |x|})
berechnet werden.
Dieses Theorem kann wie im endlichen Fall von Poynomen mit einer Variablen
auf solche mit mehreren Variablen übertragen werden.
Theorem 10.
Ein Polynom
P(x1, . . . , xn)∈Z[x1, . . . , xn]
mit maximalem
Grad kleiner d kann über
Zn
in
O(n ·min{log d,log log max {|xi|, i = 1, ..., n})
Schritten mit der Operationsmenge
{+,−,∗,&,DIV}
berechnet werden.
Ist zusätzlich eine natürliche Zahl
y≥max{|xi|, i = 1, ..., n}dn+1
gegeben, kann
P(x1, . . . , xn)
in
O(n·pmin{log d, log log max {|xi|, i = 1, ..., n})
üver
{+,−,∗,
&,DIV}
berechnet werden.
Beweis.
Sei
P(¯x)∈Z[x1,...,xn]
.
Wie im endlichen Fall wird in
O(n)
Schritten entschieden, welches der 2
n
Poly-
nome
Pk(|x1|,...,|xn|)∈Z[|x1|,...,|xn|]
mit
P(x1, . . . , xn) = Pk(|x1|,...,|xn|)
für eine Eingabe
¯x ∈Zn
an der Stelle
(|x1|,|x2|,...,|xn|)
berechnet werden
muss, um den Wert von
P(¯x)
zu berechnen.
Sei o.B.d.A.
P(¯x) = Σd1,...,dn
i1,...,in=0ai1,...,inxi1
1···xin
n∈N[x1,...,xn]
. Andernfalls, falls
P(¯x)∈Z[x1,...,xn]
, unterteile P wiederum in die Dierenz zweier Polynome
mit natürlichen Koezienten.
Um Theorem 8 auf eine Eingabe
¯x∈Zn
anwenden zu können, muss wie in
Theorem 8
(Z, Zd, ..., Zdn−1)
für ein
Z > Ω(max{xi;i= 1, ..., n}dn)
mit
d:=
max {2,d1+1, ..., dn+1};di= degxiP(¯x)
gefunden werden. Dies geht durch
wiederholtes Quadrieren von
max {|xi|, i = 1, ..., n}
oder von
(2d,2d2, ..., 2dn)
in
O(n ·min{log d,log log max {|xi|, i = 1, ..., n})
.
Bei zusätzlicher Eingabe von
y≥max{|xi|, i = 1, ..., n}dn+1
kann wiederum wie in [28] das Quadrieren zu
O(n·pmin{log d, log log max {|xi|, i = 1, ..., n})
beschleunigt werden.
51
Als nächstes muss
P(Z, Zd, ..., Zdn−1)
berechnet werden.
P(Z, Zd, ..., Zdn−1) =
d1,...,dn
X
k1,...,kn=0,
pk1,...,kn(Z)k1···(Zdn−1)kn=
d1,...,dn
X
k1,...,kn=0,
pk1,...,kn(Z)k1+...+dn−1kn
Da
k1+... +dn−1kn
für
k1, ..., kn∈ {0, ..., d −1}
verschiedene Zahlen in d-
adischer Darstellung sind, kann
P(Z, Zd, ..., Zdn−1)
als ein univariates Polynom
P0(Z)
mit
P0(x)∈N[x]
und
deg P0≤dn
betrachtet werden.
ut
Für Eingaben aus den natürlichen Zahlen ist der Algorithmus ein SLP, bei Ein-
gaben aus den ganzen Zahlen werden als zusätzliche Operation noch Vergleiche
≤
benötigt.
5.4 Speichern und Extrahieren algebraischer Zahlen
Wenn die bitweise Konjunktion nicht hinzugenommen wird, bleibt das Hor-
nerschema das schnellste bekannte Verfahren, um ein beliebiges, aber festes
Polynom über ganz
N
mit der Operationsmenge
{+,−,∗, DIV }
auszuwerten.
In [25] ist eine untere Schranke von
Ω(log log d)
für einige Polynome zur Poly-
nomauswertung bewiesen worden, wenn d den Grad des Polynoms bezeichnet.
Es entsteht also eine doppelexponentielle Lücke zur oberen Schranke von
O(d)
des Hornerschemas über
{+,−,∗}
. Damit stellt sich folgende
Frage 1
Kann jedes beliebige, aber feste Polynom
p∈N[X]
an jeder Stelle
x∈N
in
o(deg p)
über
{+,−,∗, DIV }
ausgewertet werden.
Nach den Überlegungen des letzten Abschnitts kann diese Frage positiv be-
antwortet werden, falls es möglich ist, zu
x∈N
die Zahl
p(Z)
für irgend-
ein
Z > Ω(xd)
mit
d > deg p
zu berechnen. Dazu wähle
Zn:= Y·2n
mit
Y= 2k>wt(p)
und stelle die binäre Erweiterung der Folge
p0(Zn) = 2p(Zn)<
52
Zd
n·wt(p)≤2K+dn+1
mit
n∈N
und
K:= k·(d+ 1)
, wie in Satz 3 folgender-
maÿen als reelle Zahl dar:
ρp:=
∞
X
n=0
p0(Zn)·2−n·(K+dn+1).
Um zu gegebenem
x∈N
aus dieser reellen Zahl
p0(Zn)
zu extrahieren, genügt
es,
ρp
bis auf eine Abweichung
ε < 2−n·(K+dn+1)
für ein
n > Ω(d·log x)
zu
approximieren.
Es wird
2p(Zn)
extrahiert, da das kleinste Bit bei
2p(Zn)
eine 0 ist und sollte
es bei der Approximation durch wiederholte Überträge kleinerer Bits zu einem
falschen Ergebnis des kleinsten Bits von
2p(Zn)
kommen, liefert die ganzzahlige
Division durch 2 das korrekte Ergebnis
p(Zn)
.
Lemma 11.
Sei
α∈R
algebraisch vom Grad
< d
. Dann können zu gegebe-
nem
n∈N
über
{+,−,∗}
in
O(δ·log n) u, v ∈N
berechnet werden, so dass
|α−u/v| ≤ 2−n
gilt.
Für einige transzendente Zahlen wurden ähnliche Ergebnisse, obwohl mit un-
terschiedlichen Methoden, erzielt [7].
Beweis.
Sei
q∈Z[X]
das Minimalpolynom von
α
. Mit dem Newtonschen
Nährungsverfahren lassen sich mit quadratischer Konvergenzgeschwindigkeit
die Nullstellen eines Polynoms approximieren. Zu einem festen
α∈R
können
das Minimalpolynom
q∈Z[X]
, seine Ableitung
q0∈Z[X]
und ein geeigneter
Ausgangspunkt vorab als Konstanten gespeichert werden.
ut
Aus diesem Lemma folgt für Polynome mit einer leichten Abhängigkeit von der
Eingabe x die Antwort auf die eingangs in diesem Abschnitt gestellte Frage.
Theorem 11.
Sei
p∈N[X]
ein Polynom vom Grad <d und angenommen
∞
X
n=0
2−dn2
ist algebraisch vom Grad <
δ
. Dann kann p(x) für
x∈N
über
{+,−,∗,
DIV }
in
O(δ·log log x)
Schritten berechnet werden.
Leider ist es weder bekannt, ob die Reihe
∞
X
n=0
2−dn2
algebraisch ist, noch, falls
sie algebraisch ist, von welchem Grad. Dies stellt ein ungelöstes Problem in
der Zahlentheorie dar [38, Abschnitt 10.7.B, Beispiel 1, S.314, ].
53
Um die zu Beginn dieses Abschnittes gestellte Frage zu beantworten, könnte
man, statt alle
p(Zn)
in einer Reihe zu speichern, eventuell eine linear rekurren-
te Folge von Polynomen
p(Zn)
suchen, die mit einer leichten Abhängigkeit von
x
schnell berechnet werden kann. Ein Ansatz hierzu könnte durch die in [17]
beschriebenen Algorithmen bei Hinzunahme der ganzzahligen Division und in
Verbindung mit der folgenden Bemerkung gegeben sein.
Bemerkung 5
Sei
p∈Z[x]
vom Grad
< d
und
c∈N
. Dann ist die ganzzah-
lige Folge
p(1), p(c), p(c2), . . . , p(cn), . . .
linear rekurrent vom Grad d, d.h. es
gibt
a0, . . . , ad−1, ad∈Z
, so dass
p(cn+1) = a1·p(cn) + ···+ad·p(cn−d+1)/a0
für alle
n∈N
gilt.
Beweis.
Für
k=d−1
haben die
(d+1)
Polynome
p(cx), p(x), p(x/c), . . . , p(xc−k)
alle einen Grad
< d
. Daher sind sie linear abhängig über
Q
.
q0·p(cx) + q1·
p(x) + ··· +qk+1 ·p(xc−k)≡0
; o.B.d.A.
qi∈Z
. Falls
k
minimal ist, folgt
q06= 0
.
ut
6 Anwendungen in der Linearen Algebra
Wie eingangs erwähnt und im letzten Kapitel für die Polynomauswertung ge-
zeigt, hängt die Berechnungsmächtigkeit und die Komplexität einer Register-
maschine RAM stark von der zugrundeliegenden Operationsmenge ab. Im fol-
genden Kapitel geht es um ausgewählte Probleme, deren Laufzeiten durch
diese zusätzlichen Operationen wie ganzzahlige Division usw. linear oder sogar
sublinear sind, wie auch in den folgenden Beispielen.
Beispiel 2
a) Über
{+,−,∗,DIV)}
ist nicht nur der Primzahltest, sondern sogar die Fak-
torisierung einer ganzen Zahl
x
in
O(log x)
Schritten möglich, d.h. linear
in der Binärlänge von
x
.
b) Über
{+,−,∗,DIV)}
und mit indirekter Adressierung lässt sich der gröÿ-
te gemeinsame Teiler
ggT(x, y)
zweier Zahlen x,y mit
N= max{x, y}
in
O(log N/log log N)
Schritten berechnen.
0
Ich danke
Riko Jacob
für den Hinweis auf die Punkte d) und e) in diesem Beispiel.
54
c) Über
{+,−,&,←,→}
(aber ohne indirekte Adressierung wie bei Bucket
Sort) können
n
ganze Zahlen
x1, . . . , xn
in
O(n)
Schritten sortiert werden
und über
{+,−,∗,DIV}
in
O(n·log log maxixi)
Schritten.
d)
3SUM
, die Frage, ob es zu
x1, . . . , xn, y1, . . . , yn, z1, . . . , zni, j, k
mit
xi+
yj=zk
gibt, kann in
O(n)
Schritten über
{+,−,∗,&}
entschieden werden.
e)
Die Permanente
Perm(A) = Pπ∈Sna1,π(1) ···an,π(n)
einer
n×n
Matrix
A
kann in
O(n2)
Schritten über
{+,−,∗,DIV}
berechnet werden, d.h. in
quasioptimaler Zeit.
b) Die Laufzeit des Euklidischen Algorithmus benötigt
Θ(log N)
für Fibonac-
cizahlen
x=Fn=N
,
y=Fn−1
.
c) Um die Permutation von der Eingabe zur sortierten Ausgabe zu beschreiben
erfordert bereits
Ω(n·log n)
Bits.
e) Ohne ganzzahlige Division ist Perm
VALIANT-NP
-
vollständig [8, Theorem
21.17], wenn das Einheitskostenmodell vorausgesetzt wird, im Bitmodell ist
Perm sogar
#P
-vollständig.
d) Auch 3SUM wird ohne DIV als `
n2
-vollständig' betrachtet, vergl. [19].
Beweis.
a) Siehe [40]; b) siehe [5]; c) siehe [24], für aktuellere Ergebnisse zu den
Aufwandsabschätzungen beim Sortieren mit verschiedenen Operationsmengen
siehe [20];
e) siehe [1, Proposition 2.4] und den Beweis zu Satz 6.
Die Behauptung aus d) kann von den allgemeineren Betrachtungen in [9] ab-
geleitet werden. Auf dieses Beispiel angewendet führt dies zu:
Für
0≤a0, . . . , aN−1, b0, . . . , bN−1<2t−1
, sei
A:= PN−1
i=0 ai·2ti
,
B:= Pibi·2ti
,
und
C:= Pi2t−1·2ti
. Dann gilt
∀i= 0, . . . , N −1 : ai≥bi⇔(A+C−B)&C=C .
Aufgrund der obigen Kodierung kann die folgende Aussage
∃i:ai=bi
in
konstanter Zeit über
{+,−,&}
überprüft werden. Diese Kodierung erhält man
für die doppelte Folge
(xi+yj)i+nj
in Linearzeit
O(n)
über
{+,−,∗}
, vergl.
dazu den Beweis von Satz 12.
ut
55
6.1 Matrixmultiplikation
Der derzeitige Rekord bei der Matrixmultiplikation ohne ganzzahlige Division
liegt bei
O(nω)
mit
ω
< 2,38, aufgestellt von Don COPPERSMITH und Shmu-
el WINOGRAD
[15], [8, Chapter 15].
Es wird in diesem Abschnitt gezeigt,
dass bei Hinzunahme der ganzzahligen Operation als weitere Operation die
Matrizen in quadratischer Zeit, d.h. quasi-optimaler Zeit, berechnet werden
können.
Theorem 12.
Seien
A∈Zkxn
und
B∈Znxm
.
C := A ·B∈Zkxm
kann über
{+,−,∗,DIV}
in
O((k + m)n + km)
Schritten berechnet werden.
Beweis.
Für
i= 1, ..., k
und
j= 1, .., m
soll
ci,j =Σn
l=1ai,l ·bl,l
berechnet
werden. O
.
B.d.A. seien
ai,l, bl,l≥0
, ansonsten zerlege die Matrizen und multi-
pliziere nach dem nicht-kommutativen Distributivgesetz für Matrizen.
Z sei eine Zweierpotenz und so gewählt, dass
Z > (maxi,lai,l)·(maxl,jbl,j)·n
.
Die Matrizen A und B werden folgendermaÿen als ganze Zahlen in
O(kn)
und
O(nm)
Schritten kodiert.
α:= Σk
i=1Σn
l=1ai,l ·Z
(l-1)+2nm(i-1)
und β:= Σk
i=1Σn
l=1bl,i ·Z
(n-l)+2n(j-1)
Vorab werden alle zur Kodierung und späteren Dekodierung benötigten Po-
tenzen von Z in
O(log (knm))
berechnet.
Wie in der folgenden Abbildung dargestellt, stehen die gesuchten Zahlen
ci,j
bei dem Produkt
γ:= α·β
in Z-adischer Darstellung genau an den Positionen
Z
2n(j-1)+(n-1)+2nm(i-1)
. Mittels ganzzahliger Division werden die
ci,j
in
O(km)
Schritten aus dem Produkt
γ
extrahiert.
Abbildung 9.
Kodierung der Matrizen A und B und Dekodierung der Matrix C
56
Die Berechnungszeit wird zum Kodieren und Dekodieren der Matrizen benötigt
und die eigentliche Multiplikation erfolgt in konstanter Zeit.
ut
6.2 Permanente und Determinante
Dass bei Hinzunahme der ganzzahligen Division die Permanente einer Matrix
in quadratischer Zeit berechnet werden kann, wurde für Matrizen mit Einträ-
gen aus
{0,1}
von Eric ALLENDER, Peter BÜRGISSER et al. in [1] gezeigt.
Dieser Beweis wird auf Matrizen mit Einträgen aus
N
übertragen. In Verbin-
dung mit der Polynomberechnung bei multivariaten Polynomen über einem
endlichen Bereich lässt sich diese Laufzeit auf die Berechnung der Determi-
nante einer Matrix mit ganzzahligen Einträgen übertragen.
Satz 6
Man kann
Nn×n3A7→ Perm(A) = X
π∈Sn
a1,π(1) ···an,π(n)
über
{+,−,∗, DIV }
in
O(n2)
Schritten berechnen.
Beweis.
Betrachte das multivariate Polynom f
n
.
fn:=
n2n−1
X
i=1
fn,iYi=
n
Y
i=1
(
n
X
j=1
Xi,jY2j−1)
Die f
n,i
sind Polynome mit natürlichen Koezienten in n
2
Variablen.
Alle
Y2j−1
für j=1,...,n und damit auch jede Summe für i=1,...,n lassen sich
in
O(n)
berechnen. Da es n Summen sind und das Produkt über diese Sum-
me wiederum in
O(n)
berechnet werden kann, ist dieses Polynom in
O(n2)
Schritten über
{+,−,∗}
berechenbar.
Zu einer Matrix A mit Einträgen
ai,j ∈N
wird dieses Polynom f
n
für
Xi,j =
ai,j
und für ein genügend groÿes Y=Z>
(maxn
i,j=1ai,j)n3> nn·(maxn
i,j=1ai,j)n
,
ebenfalls in
O(n2)
berechenbar, ausgewertet. Nach Wahl von Z ist
fn,2n−1
an
der Stelle
Xi,j =ai,j
gerade die Permanente von A. Durch die ganzzahlige
Division und Restbildung lässt sich
fn,2n−1
aus
fn(Z)
extrahieren.
ut
57
Im Folgenden wird gezeigt, dass diese quasi-optimale Polynomialzeit
O(n2)
nicht nur für die Berechnung der Permanente, sondern auch für die Berechnung
der Determinante gilt.
Theorem 13.
Sei
A∈Zn×n
,
Det(A)
kann in
O(n2)
Schritten über
{+,−,∗,
DIV} berechnet werden.
Im Gegensatz zu Theorem 10 wird die bitweise Konjunktion & hier nicht als
weitere Operation benötigt.
Beweis.
Zunächst wird die Matrix
A∈Zn×n
zu einer Matrix
A0∈Nn×n
, deren
Determinante sich höchstens um das Vorzeichen von der Determinante von A
unterscheidet, in
O(n2)
Schritten umgeformt.
Sei
ai0,j0=max{|ai,j|, i, j = 1, ..., n}∈ N
, ansonsten, falls
ai0,j0
negativ ist,
multipliziere die
i0.
Zeile mit -1. Die beiden Determinanten unterscheiden sich
dann um das Vorzeichen.
Addiere zu jeder Zeile das Doppelte der Zeile
i0
. In der Spalte
j0
haben nun
alle Einträge dasselbe Vorzeichen wie
ai0,j0
und sind betragsmäÿig gröÿer als
ai0,j0
und die Einträge in den anderen Spalten sind
≤3·ai0,j0
.
Wird nun zu jeder Spalte das Vierfache der Spalte
j0
addiert, so sind alle
Einträge positiv und haben sich betragsmäÿig höchstens verachtfacht. Da sich
die Determinante bei diesen Zeilen- und Spaltenumformungen nicht ändert,
wird im Folgenden o.B.d.A.
A∈Nn×n
angenommen.
Wird die Determinante für Matrizen mit natürlichen Einträgen in ihren posi-
tiven Teil und ihren negativen Teil aufgeteilt,
Det+(A) = X
π∈Sn
sgn(π)=+
a1,π(1) ···an,π(n)
und
Det−(A) = X
π∈Sn
sgn(π)=−
a1,π(1) ···an,π(n),
so lassen sich die Permanente und die Determinante folgendermaÿen aus-
drücken:
Perm(A) = Det+(A) + Det−(A)
und
Det (A) = Det+(A)−Det−(A)
.
58
Da sowohl
Det+(A)
als auch
Det−(A)
Polynome in
n2
Variablen
xi+n(j−1) :=
ai,j
mit Maximalgrad kleiner als
d:= 2
(
der totale
Grad ist
n
) und Koezi-
enten
0,1
sind, genügt es wie in Abschnitt 5.2 und dem Beweis von Satz 8,
die Werte von
Det+= (Perm + Det)/2
und von
Det−= (Perm −Det)/2
an
der Stelle
x= (x0, . . . , xn2−1) := (Z0, Z02, Z04, . . . , Z02n2−1)
zu berechnen, wobei
Z0:= Z·Y
für
Z:= (maxk|xk|)2n2
und eine geeignete Konstante
Y
in
O(n2)
Schritten berechnet werden. Nach Satz 6 kann die Permanente ebenfalls in
O(n2)
Schritten berechnet werden.
Um die Determinante dieser Matrix zu berechnen, wird sie folgendermaÿen
umgeformt:
Z0Z02Z04Z08··· Z02n−1
Z02nZ02n+1 Z02n+2 ··· Z022n−1
Z022nZ022n+1
...
Z023n−1
Z023n
...
Z024n−1
.
.
..
.
.
Z02(n−1)n··· ···Z02n2−1
=
=
Z0Z02Z04Z08··· Z02n−1
Z02nZ02n2Z02n4Z02n8Z02n2n−1
Z022nZ022n2Z022n4Z022n8Z022n2n−1
Z023nZ023n2
...
Z023n2n−1
.
.
..
.
.
Z02(n−1)nZ02(n−1)n2··· ···Z02(n−1)n2n−1
=
Da dies die Determinante einer Vandermondematrix ist, gilt für diese
=Z0·Z02n·Z022n···Z02(n−1)n·Y
1≤i<j≤nZ02(j−1)n−Z02(i−1)n.
Dieser Ausdruck lässt sich ebenfalls in
O(n2)
Schritten berechnen.
ut
59
Frage 2
Sei
P ⊆ Sn
eine beliebige Familie von Permutationen von
[n]
. Kann
auch
Pπ∈P Qn−1
i=0 xi+nπ0(i))
in
O(n2)
Schritten über
{+,−,∗, DIV }
berechnet
werden?
6.3 Potenzierung ganzzahliger Matrizen
Bekannterweise kann
a2k
durch wiederholtes Quadrieren in k Schritten be-
rechnet werden. In [11] wurde gezeigt, dass bei Hinzunahme der ganzzahligen
Division als weitere Operation und einer ganzen Zahl b gröÿer als
a2k
nur
O(√k)
Schritte benötigt werden. Dieses Verfahren wird auf die Potenzierung
von Matrizen übertragen. Um eine Laufzeitverbesserung gegenüber der Lauf-
zeit von
O(k ·d2)
für die k-fache Matrixmultiplikation von d x d-Matrizen aus
dem vorherigen Abschnitt zu erzielen, benötigt man als zusätzliche Operation
auf den ganzen Zahlen die Bildung des gröÿten gemeinsamen Teilers ggT.
Denition 3.
Seien X,C
∈Zdxd
a)
ggT
(C):=
ggT
(c
ij
:1
≤i, j ≤d
)
b) X
rem
C:= (x
ij
mod ggT
(C))
c) X
≡
Y
mod
C, falls der
ggT
(C) jeden Eintrag x
ij
- y
ij
von X - Y teilt.
Dies ergibt für festes C eine Äquivalenzrelation auf
Zdxd
, sogar eine zweiseitige
Kongruenzrelation
1
wie das folgende Lemma zeigt.
Lemma 12.
a) Falls X
≡
Y
mod
C ist, gilt S
·
X
·
T
≡
S
·
Y
·
T
mod
C.
b) Für jedes
n∈N
gilt
Xn≡Yn(mod (X−Y)
.
c) X
rem
C
≡
X (
mod
C).
d) Falls 0
≤x
ij
<ggT(C)
ist, gilt X
rem
C = X.
Beweis.
a) gilt nach dem Distributivgesetz für Matrizen.
b) folgt aus a) und dem nicht-kommutativen Binomialtheorem.
c) und d) folgen unmittelbar aus den Denitionen.
ut
1
Umgekehrt hat jedes zweiseitige Ideal in
Zd×d
diese Form [21, Proposition III.2.1]
60
Theorem 14.
Seien
k∈N
,
A∈Ndxd
gegeben und
γ:= d2k−1·(maxija
ij
)2k
.
Ferner sei noch ein
B∈Ndxd
gegeben, so dass für alle
C∈ {0,1, ..., γ}dxd
ggT(B - C) >
γ
gilt, dann kann
A2k
in
O(√k·d2)
Schritten über
{+,−,∗,DIV,
ggT}
berechnet werden.
Bemerkung 6
Nach der Wahl von B kann nicht nur
A2k
in
O(√k·d2)
Schrit-
ten über
{+,−,∗,DIV,ggT}
berechnet werden, sondern auch jedes
A02k0
für
jedes
0≤k0≤k
und
0≤maxij|a0
ij
| ≤ maxij|a
ij
|
in
O(√k0·d2)
Schritten .
Beweis.
Es genügt den Fall k=l
2
zu betrachten. Nach Theorem 12 wird zu-
nächst die Matrix
B2l
durch wiederholtes Quadrieren in
O(l ·d2)
Schritten
berechnet.
Durch Anwendung von Lemma 12 auf
n:= 2
l
,
X:= A2l(j−1)
,
Y:= B2l
und
C:= Y−X
erhält man folgende Gleichung
(*)
A2lj = (A2l(j−1) )2l=B2lrem (B−A2l(j−1) ),
falls der ggT(
B−A2l(j−1)
) gröÿer als die Einträge von
A2l2
ist.
Induktiv wird für
j= 1, ..., l
nach Gleichung (*)
A2lj
aus
A2l(j−1)
jeweils in
O(d2)
Schritten berechnet.
Da die m-te Potenz einer d x d-Matrix A mit Einträgen aus der Menge
{0,1, ..., s}
Einträge aus der Menge
{0,1, ..., d
m-1
·s
m
}
hat, gilt nach der Voraussetzung für
B die obige Gleichung.
Die Operation ggT wird benötigt, um den ggT(C) in
O(d2)
Schritten und
damit X rem C nach der obigen Denition zu berechnen.
ut
Erstaunlicherweise erhält man die Folge von Matrizen
A2lj
,
j= 1, ..., l
nur
durch Modulo-Berechnungen der Matrizeneinträge.
Es fehlt noch der Beweis, dass es solch ein B, bei dem der ggT(B-C )>
γ
für
alle Matrizen
C∈ {0,1, ..., γ}dxd
ist, überhaupt gibt.
61
Im Fall d = 1 heiÿt das gerade, dass, wie in Satz 5, B=(b) gröÿer als
a2l2
für
A=(a) ist, vgl. [11].
Für den Fall d>1 wird im Lemma des nächsten Abschnitts gezeigt, dass es
viele solcher B gibt, und es wird beschrieben, wie man sie erhält.
6.4 Lokale untere Schranke des ggT
Eine reelle Funktion
f:Rd→R
heiÿt halbstetig nach oben an der Stelle
x
,
wenn für alle
u
in einer Umgebung von
x
die Funktionswerte von
x
und
u
nicht
zu weit auseinander liegen, siehe [36]. Da der ggT eine diskrete Funktion ist,
sind diese topologischen Kriterien streng genommen nicht auf diese Funktion
anwendbar. Aber dennoch lassen sich auch für den gröÿten gemeinsamen Teiler
Punkte
x
angeben, die dem Begri der oberen Halbstetigkeit ähnlich sind.
Lemma 13.
Für alle d, r, s
∈N
gibt es
x1, x2, ..., xd∈N
, so dass für alle
v1, v2, ..., vd∈ {0,1, ...,s−1}
ggT
(
x1+v1, ..., xd+vd
)
≥r
gilt.
Beweis.
Man nehme paarweise teilerfremde natürliche Zahlen
pv> r
,
v∈
{0,1, ...,s−1}d
, man kann im Allgemeinen die
pv
als Primzahlen wählen. Für
i= 1, ..., d
und
j= 0, ..., d−1
sei
ui,j := Qv,vi=jpv
. Die Zahlen
ui,0, ui,1, ..., ui,s−1
sind bei festem i wiederum teilerfremd. Nach dem Chinesischen Restsatz gibt es
ein
xi∈N
, so dass
ui,j
für alle
j= 0,1, ..., s−1xi+j
teilt. Da insbesondere alle
pv
in den
ui,vi
als Teiler vorkommen, teilen sie
xi+vi
für jedes
i= 1, ..., d
und
damit auch den ggT(
x1+v1, ..., xd+vd
). Daher muss der ggT(
x1+v1, ..., xd+vd
)
mindestens so groÿ sein wie
pv> r
.
ut
Bemerkung 7
a) Die
x1, x2, ..., xd∈N
aus dem vorherigen Lemma können
so gewählt werden, dass sie zwischen 0 und
(r·S)O(S)
mit S:=s
d
liegen.
b) Über
{+,−,∗,DIV,eggT}
können sie in
O(S)
Schritten gebildet werden
(aber nicht notwendigerweise innerhalb obiger Schranke).
eggT bezeichnet den erweiterten gröÿten gemeinsamen Teiler, d.h. dass es zu
gegebenen
x, y ∈Ns, t ∈Z
(o.B.d.A. s, t teilerfremd) gibt mit ggT(x,y)= sx
+ty.
62
Beweis.
a) Nach dem Primzahltheorem hat die k-te Primzahl eine Gröÿenord-
nung von
O(k·log k)
und es gibt höchstens
π(n)≤ O(n/log n)
Primzahlen,
die kleiner als n sind. Daher hat die erste Primzahl, die wenigstens so groÿ wie
r ist, den Index
kr:= π(r)≤ O(r/log r)
.
Es soll das Produkt
N:= pkr·... ·pkr+S
beschränkt werden, das ist gerade der
Quotient der Primfakultäten
2
(r + l)#/r# mit
r+l=pkr+S=r+ (S·log S)
.
In [32] ist gezeigt worden, dass
π(r+l)−π(r)≤2π(l)
3
gilt. Also gibt es
zwischen r und r + l mindestens
O(l/log l) = O(S)
Primzahlen und jede
dieser Primzahlen ist natürlich nicht gröÿer als r + l. Daher gilt
N= (r+l) #/r#≤(r+l)O(S·log S)≤(r·l)O(S·log S)
für
l=O(S·log S)
.
b) Die paarweise teilerfremden ganzzahligen
pi≥r
erhält man folgendermaÿen:
p1:= r
,
p2:= p1+1
,
p3:= p1·p2+1
,...,
pi+1 := p1·...·pi+1
. Durch Anwendung
des folgenden Lemmas, dem Chinesischen Restsatz mit Laufzeitabschätzungen,
folgt der Beweis zu b).
Lemma 14.
(Chinesischer Restsatz)
Zu gegebenen
a1, a2, ..., an∈Z
und tei-
lerfremden
m1, m2, ..., mn∈N
kann ein
x∈N
mit
x≡aimod mi
für
i=
1, ..., n
in
O(log n·Σn
i=1log mi)
Schritten über
{+,−,∗,DIV}
berechnet wer-
den. Wird der erweiterte gröÿte gemeinsame Teiler eggT als weitere Operation
hinzugenommen, reduziert sich die Laufzeit auf
O(n)
4
.
Beweis.
Berechne
N:= m1·m2·... ·mn
und mit der Operation eggT berechne
si, ti∈Z
mit
1 = ggT(mi, N/mi) = simi+tiN/mi
. Für
ei:= tiN/mi
,
i=
1, ..., n
gilt
ei≡1 mod mi
und
ei≡0 mod mj
für
i6=j
. Daraus folgt, dass
x:= Σn
i=1aiei
die geforderten Kongruenzen erfüllt.
Über
{+,−,∗,DIV}
benötigt die Berechnung von
eggT(mi, N/mi)O(log N) =
O(Σn
i=1log mi)
Schritte für jedes
i= 1, .., n
, also eine Gesamtlaufzeit von
O(n·Σn
i=1log mi) = O(n·log N)
, falls diese n Berechnungen mit Hilfe des
2
Eine Primfakultät (engl. primorial) p# ist das Produkt der ersten p Primzahlen.
3
Ich danke Stephan Wehmeier für den Hinweis auf diese Schranke.
4
Da
m1, ..., mn
teilerfremd sind, gilt
Σn
i=1log mi> Ω(n)
.
63
erweiterten gröÿten gemeinsamen Teiler nacheinander durchgeführt werden.
Über
{+,−,∗,DIV,eggT}
benötigt man
O(n)
Schritte.
Um den Faktor n in der obigen Berechnung nach log n zu verbessern, werden
die simultanen Kongruenzen
x≡aimod mi
für
i= 1, .., n
folgendermaÿen in
einem Binärbaum angeordnet:
Berechne zunächst die simultanen Kongruenzen
y
j
für
j= 1, ..., n/2
. Da-
nach berechne folgende simultane Kongruenzen
x≡y2j(mod m4j·m4j+1)
und
x≡y2j+1(mod m4j+2 ·m4j+3)
für
j= 1, ..., n/4
. Auf der k-ten Ebene sind
n/2
k
simultane Kongruenzen, bei denen für die Berechnungen der Moduli als Pro-
dukte disjunkte k-tupel aus
{m1, m2, ..., mn}
benutzt werden. Auf jede dieser
log n Ebenen werden
O(Σn
i=1log mi)
Schritte unabhängig von
k = 1, ...,O(log n)
benötigt, d.h. eine Gesamtlaufzeit von
O(log n·Σn
i=1log mi)
.
ut
6.5 Primzahlbildung mit Hilfe der ganzzahligen Division
Die gröÿten der in dem Beweis zur Bermerkung 7 b) konstruierten Primzah-
len und damit aber auch die
x
i
aus Lemma 13 sind von der Gröÿenordnung
Ω(r2s−1)
und damit erheblich gröÿer als die möglichen in Teil a) als Primzah-
len gewählten p
j
. Es stellt sich dann natürlich die Frage, ob die genannten
nicht klassischen Operationen die Berechnung dieser Primzahlen ermöglicht,
d.h. kann die Suche nach einer Funktion, die als Funktionswerte nur Primzah-
len hat, mit diesen Operationen gelingen? Diese Frage wird am Anfang von
Kapitel 3 in [37] gestellt und in Abschnitt II dieses Kapitels weiter erörtert.
Das Sieb des Eratosthenes ndet alle Primzahlen kleiner N in
O(N)
Schrit-
ten über
{+,−}
. Dies kann zu
O(N/log log N)
beschleunigt werden [35]. Da
nach dem Primzahltheorem es
Θ(N/log N)
Primzahlen kleiner N gibt, ist die-
se Schranke im Vergleich zur Ausgabe optimal. Damit lassen sich in einem
einfachen randomisierten Verfahren Primzahlen nden.
Bemerkung 8
Zu
N∈N
rate irgendein
N≤n < 2N.
Mit einer Wahr-
scheinlichkeit von
Θ(1/log N)
ist n eine Primzahl. Nach
O(log N)
unabhängi-
gen Versuchen hat man mit konstanter Wahrscheinlichkeit eine Primzahl ge-
64
funden. Mit dem Primzahltest aus [14] führt dies über
{+,−,∗,DIV}
zu einer
Laufzeit von
O(log2N)
.
Da das Bertrand-Chebyshev Theorem besagt, dass es stets eine Primzahl zwi-
schen N und 2 N gibt, lässt sich dieser einfache Algorithmus etwas verbessern.
Theorem 15.
Zu
N∈N
gibt es einen Algorithmus über
{+,−,∗,DIV}
, mit
dem man mit konstanter Wahrscheinlichkeit und in
O(log2N/log log N)
Schrit-
ten eine Primzahl
p≥N
erhält.
Beweis.
Prüfe zunächst, ob N eine Primzahl ist, indem nach Wilson`s Theorem
geprüft wird, ob
(N−1)!
von
N
geteilt wird. Das geht über
{+,−,∗,DIV}
in
O(log N)
Schritten [40, Abschnitt 3].
Alle benachbarten Fakultäten
(N+k)!
,
k= 1, ..., K
können in konstanter Zeit
berechnet werden, d.h. nach dem Primzahltest für N erhöht sich in der
O
-
Notation für die Primzahltests von
N+ 1, N + 2, ..., N +K
für
K:= O(log N)
nichts.
Rate nun irgendeine
O(log N)
-Bit-Zahl
M≤N
und teste danach wie oben in
O(log N)
Schritten, ob die Zahlen
N+M, N +M+1, ..., N +M+K
Primzahlen
sind.
Behauptung 5
Mit einer Wahrscheinlichkeit von
Ω(log log N/log N)
wird ei-
ne Primzahl gefunden.
Nach
O(log N/log log N)
unabhängigen Versuchen hat man mit konstanter
Wahrscheinlichkeit eine Primzahl gefunden.
Beweis.
der Behauptung
Nach dem Primzahltheorem liegen zwischen N und 2N
Ω(N/log N)
Primzah-
len, auÿerdem liegen in jedem Intervall der Länge K zwischen N und 2N höchs-
tens
π(K)≤ O(K/log K)
Primzahlen [32].
Daher besagt das Dirichletsche Schubfachprinzip, dass innerhalb dieser
N/K
Intervalle mindestens
Ω(log K/log N)
viele Intervalle wenigstens eine Primzahl
enthalten, d.h.
Ω(log log N/log N)
für K:=
O(log N)
.
ut
65
Einen Ansatz zu einem sogar noch schnelleren und deterministischen Weg zur
Primzahlbildung erhält man folgendermaÿen:
Bemerkung 9
1947 bewies W.H.MILLS die Existenz einer reellen Zahl
θ≈
1,3063789
[14],
so dass
pn:= θ3n
eine Folge von Primzahlen bildet mit
pn+1 > p3
n
.
Nicht bekannt ist, ob
θ
rational ist. Falls
θ
rational ist, kann man in
O(n) =
O(log N)
Schritten über
{+,−,∗,DIV}
eine Primzahl
pn>3n=: N
nden.
Aber wir erhalten auch diese Schranke, selbst wenn
θ
irrational und
algebraisch
ist. Um
θN
zu berechnen, betrachte
(θ+ε)N=θN+N·εN−1+
N
X
k=2
N
k
·εk·θN−k
| {z }
<1
Aus dieser Abschätzung folgt, dass es genügt eine rationale Approximation
θ0
von
θ
mit einer Abweichung von
ε≈2−N/N
zu berechnen.
Nach Lemma 11 geht das, falls
θ
algebraisch ist, in
O(log N)
Schritten und
dann kann man, da
θN
=
θ0N
gilt, in
O(log N)
Schritten über
{+,−,∗,DIV}
eine Primzahl >N nden
7 Rückblick und Ausblick
In dieser Arbeit wurden die Sprachklassen, die mit der ganzzahligen Division
erkannt werden können, auch für den n-dimensionalen Fall vollständig unter-
schieden. Eine Charakterisierung dieser Sprachen gelang vollständig nur für
die ganzzahlige Division mit Konstanten. Für die anderen Operationsmengen
S⊆ {+,−,∗,∗c,DIVc,DIV}
gelang eine Charakterisierung nur für sehr ein-
geschränkte Eingabemengen. Es könnte im Folgenden untersucht werden, für
welche Sprachen sich weitere untere Schranken aus diesen Charakterisierungen
von den unteren Schranken für diese Sprachen mit Operationsmengen ohne
ganzzahlige Division ableiten lassen.
66
Die doppellogarithmische Lücke zwischen oberer Schranke
O(d)
und unterer
Schranke
Ω(log log (d))
, falls d den Grad des Polynoms bezeichnet, zur Po-
lynomauswertung über dieser mächtigen Operationsmenge
{+,−,∗,DIV}
mit
rationalen Konstanten konnte nicht geschlossen werden, sondern führte zu ei-
nem seit langem oenen Problem der Zahlentheorie, ob die Reihe
∞
X
n=0
2−dn2
algebraisch ist, und, wenn ja, von welchem Grad. Das Ziel ist weiterhin für
eine unendliche Folge von Eingabewerten eine Möglichkeit zu nden, die zuge-
hörigen Werte des Polynoms in
o(deg p)
zu berechnen, so dass in Verbindung
mit dem Algorithmus von Bshouty insgesamt Polynome in
o(deg p)
ausgewertet
werden können. Eine Beschleunigung zu
O(log d)
gelang nur bei Hinzunahme
der bitweisen Konjunktion als weiterer Operation. Da es aber nicht bekannt
ist, ob die bitweise Konjunktion
&
in Polynomialzeit mit der Operations-
menge
{+,−,∗,DIV}
simuliert werden kann, führt dieser Weg nicht zu einem
Algorithmus zur Polynomauswertung in
o(deg p)
über
{+,−,∗,DIV}
, sondern
zu der seit langem oenen Frage NP=PSPACE.
Ausgehend von diesem schnellen Algorithmus von Bshouty zur Polynomaus-
wertung über einem endlichen Bereich stellt sich die Frage, ob dieser Algo-
rithmus auf einem modernen Computer schneller ist als andere Algorithmen
wie z.B. das Hornerschema. Statt der maximal d Multiplikationen, wenn d der
Grad des Polynoms ist, werden 2 ganzzahlige Divisionen benutzt. Dies ist der
entgegengesetzte Weg zur Vorgehensweise in z.B. [18], bei der Multiplikationen
durch ganzzahlige Divisionen ersetzt werden. Ein Nachteil ist, dass bei diesem
Algorithmus riesige Zahlen zur Berechnung benötigt werden und kein realer
Rechner in der Lage ist, solch groÿe Zahlen in konstanter Zeit zu verarbeiten.
Heiÿt das von vornherein, dass dieser Algorithmus nicht praktikabel ist. In den
letzten Jahrzehnten ist der technische Fortschritt dermaÿen angewachsen, dass
es in der Bandbreite der arithmetisch-logischen Einheiten (ALU=arithmetical-
logical unit) von Prozessoren einen exponentiellen Zuwachs gab. Heutige Com-
puter können auf 64 oder sogar 128 Bits in einer einzigen Anweisung operieren,
d.h. das Einheitskostenmodell gilt bereits für sehr groÿe Eingaben und dieser
Bitbereich wird immer noch gröÿer.
67
Nicht nur für die Polynomauswertung wurde ein Algorithmus vorgestellt, der
die ganzzahlige Division und bitweise Konjunktion zur Beschleunigung be-
nutzt, sondern es wurden auch Algorithmen entwickelt, die die ganzzahlige
Division und andere Operationen wie den gröÿten gemeinsamen Teiler nutzen,
um die Matrixmultiplikation und -potenzierung und zahlentheoretische Rech-
nungen zu beschleunigen. Es wurden einige Lösungsansätze vorgestellt, die zu
wirklich eektiven Lösungen führen, wenn gleichzeitig seit langem oene Fra-
gestellungen der Zahlentheorie bewiesen werden könnten. Andere Probleme
lieÿen sich dadurch beschleunigen, dass zusätzlich im Vergleich zur Eingabe
sehr groÿe Zahlen mit eingegeben werden. Die Laufzeit dabei ist sogar kürzer
als die informationstheoretischen unteren Schranken.
Würde als weitere Operation mit Einheitskosten der Linksshift
←:y7→ 2y
wie in [41] hinzugenommen oder sogar allgemein die Exponentiation
N×N3
(x, y)7→ xy
lieÿen sich auch diese Zahlen, da sie doppelexponentiell groÿ sind,
schnell berechnen.
Abbildungsverzeichnis
1 Berechnungsbaum............................................ 3
2 Modulo-Verzweigungs-Baum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Pyramide ................................................... 15
4 Sprachklassen für n>1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Sprachklassen für n=1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Berechnungen im Beweis von Satz 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7 Berechnungen in Bshoutys Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 42
8 Berechnungen im Beweis von Satz 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
9 Kodierung der Matrizen A und B und Dekodierung der Matrix C . . . 55
68
Literatur
1.
E.Allender, P. Bürgisser, J. Kjeldgaard-Pedersen
, On the complexity of numerical
analysis, 21 IEEE CCC, 331-339, 2006.
2.
L. Babai, B. Just, F. Meyer auf der Heide
, On the limits of computations with the oor
function, Information and Computation 78(2), 99107, 1988.
3.
A. Bertoni, G. Mauri, N. Sabadini
, A characterization of the class of functions computable
in polynomiel time on random access machines ,
STOC,
168176, (1981).
4.
A. Bertoni, G. Mauri, N. Sabadini
, Simulations among classes of Random Access Machines
and equivalence among numbers succinctly represented , Ann. Discrete Math. vol.
25,
6590,
(1985).
5.
N. Bshouty
, Euclidean GCD algorithm is not optimal, preprint 1989.
6.
N. Bshouty
, private communication, 1992.
7.
J. Borwein, P. Borwein
, PI and the AG, Wiley (1987).
8.
P.Bürgisser, M.Clausen, M.A. Shokrollah
, Algebraic complexity theory, Springer 1997.
9.
I. Baran, E.D. Demaine, M. Patrascu
, Subquadratic algorithms for 3 SUM, 9th WADS,
Springer LNCS vol. 3608, 409421, 2005.
10.
R. Brent, H. Kung
, Systolic VLSI-arrays for linear time GCD-computation, Proc.Int. Conf.
on Very Large Scale Integration. (VLSI 83, IFIP), F.Anceau and E. J. Aas(eds), 145-154, 1983.
11.
N.Bshouty, Y. Mansour, B.Schieber, P.Tiwari
, Fast exponentiation using the truncation
operation, computational complexity vol.2, 244255, 1992.
12.
M. Ben-Or
, Lower bounds for algebraic computation trees, 15th ACM-STOC, 8086, 1983.
13.
Q. Cheng
, On the ultimate complexity of factorials,20 th STACS 2003, Springer LNCS
vol.2607, 157166, 2003.
14.
C.K. Caldwell, Y. Cheng
, Determing Mill's constant and a note on Honaker' problem,
Journal of Integer Sequences vol. 8, article 05.4.1, 2005.
15.
D. Coppersmith, S. Winograd
, Matrix multiplication via arithmetic progressions, Journal
of symbolic computation vol. 9, 251280, 1990.
16.
D. Dobkin, R. L. Lipton
, A lower bound of
1
2n2
on linear search programs for the knapsack
problem, JCSS 16, 417421, 1975.
17.
C.M. Fiduccia
, An ecient formula for linear recurrences, SIAM J. Comput. vol.
14:1,
106
112 , (1985).
18.
T. Granlund, P.L. Montgomery
, Division by invariant integers using multiplication, ACM
SIGPLAN Notices, 6172, June 1994.
19.
A. Gajentaan, M.H. Overmars
, On a class of
O(n2)
problems in computational geometry,
Computational Geometry: Theory and Applications vol.5, 165185, 1995.
20.
Y. Han
, Deterministic sorting in
O(n log log n)
time and linear space, Journal of algorithms
vol. 50, 96105, 2004.
21.
N. Jacobson
, Structure of Rings, American Mathematical Society Colloquium Publications
vol.
37
(1964).
22.
B. Just, F. Meyer auf der Heide, A. Wigderson
, On computations with integer division,
RAIRO Informatique Theoretique 23(1), 101111, 1989.
23.
P. Klein, F. Meyer auf der Heide
, A lower bound for the knapsack problem on random
access machines, Acta Informatica 19(3), 385396, 1983.
69
24.
D. Kirkpatrick, S. Reisch
, Upper bounds on sorting integers on random access machines,
Theoretical computer science 28 (3), 263276, 1989.
25.
K. Lürwer-Brüggemeier, F. Meyer auf der Heide
, Capabilities and complexity of com-
putations with integer division, 10th STACS, Springer LNCS vol 665, 463472, 1993.
26.
K. Lürwer-Brüggemeier, M. Ziegler,
On faster integer calculations using non-arithmetic
primitives, 7th UC, Springer LNCS vol 5204, 111128, 2008.
27.
Y. Mansur, B. Schieber, P. Tiwari
, Lower bounds for integer greatest common divisor
computation, 29th IEEE FOCS, 5463, 1988.
28.
Y. Mansour, B. Schieber, P. Tiwari
, The complexity of approximating the square root,
30th IEEE FOCS, 325330, 1989.
29.
J. Meidanis
, private communication, 1992.
30.
F. Meyer auf der Heide
, Lower bounds for solving linear Diophantine equations on random
access machines, J. ACM 32(4), 929937, 1985.
31.
F. Meyer auf der Heide
, On genuinely time bounded computations, 5th STACS, 1
16,1989Nr. 285,1988
32.
H.L.Montgomery, R.C. Vaughan
, The large sieve, Mathematika vol. 20, 119134, 1973.
33.
W. J. Paul, J. Simon
, Decision trees and random access machines, Monographie 30,
L'Enseignement Mathematique, Logique et Algorithmique, Univ. Geneva, Switzerland, 331
340, 1992.
34.
V.R. Pratt, M.O. Rabin, L.J. Stockmeyer
, A Characterization of the Power of Vector
Machines, Proc. 6th Annual ACM Symposium on Theory of Computing, 122134, (STOC
1974).
35.
P. Pritchard
, a sublinear additive sieve for nding prime numbers, Communications of the
ACM, vol.24, 1823, 1981.
36.
J.F. Randolph
, Basic real and abstract analysis, Academic Press, 1968.
37.
P. Ribenboim
, The new book of prime number records, 3rd edition springer, 1996.
38.
P. Ribenboim
, My numbers, my friends, Springer, 2000.
39.
A.Schönhage
, On the Power of Random Access Machines, Automata Languages and Pro-
gramming, 6th Colloquium, Springer LNCS vol. 71,520-529, 1979
40.
A.Shamir
, Factoring numbers in
O
(log n) arithmetic steps, Information Processing Letters
vol. 8(1), 28-31, 1979.
41.
J. Simon
, Division is good, 20th IEEE FOCS, 411420, 1979.
42.
A. Yao
, Lower bounds for algebraic computation trees with integer inputs, 30th IEEE FOCS,
308313, 1989.
