AC 0 k : = |y| AC 0 : = 1 - y 2- k NC 1 berechne für i = 0,1,...,n - 1 parallel NC 1 z : = 2- k
= | = = 2- k = | ||
= | 2- k = 2- k( + ) | ||
= | 2- k( + ) |
Mit (y,n) = 2- k erhalten wir
d : = - (y,n) = = ,
denn 1 - y 2- k = 1 - = y 2- k 2k(1 - ) = y = , und wegen gilt ( d 0 klar)
0 d .
Die Berechnung einer Potenz lässt sich auf die Berechnung des Produkts xi von n natürlichen Zahlen x1,...,xn zurückführen. Der naheliegendste Algorithmus dafür ist aber in NC 2. Idee für einen NC 1-Algorithmus:
log(xi) = (logxi)
Zurückführung auf eine Summe von Logarithmen. Da wir nur Ganzzahl-Arithmetik zur Verfügung haben, benötigen wir den diskreten Logarithmus.