Information Technology Reference
In-Depth Information
-
A
radicalcomputation tree
is an algebraic computation tree in which the set of
allowable functions is augmented with the
k
th
root operation, where
k
is an integer
parameter to the operation, and with complex conjugation. These trees capture the
calculations whose results can be expressed as nested radicals.
-
A
root computation tree
is an algebraic computation tree in which the allowable
functions include the ability to find complex roots of polynomials whose coeffi-
cients are integers or previously computed values, and to compute complex con-
jugates of previously computed values. For instance, this model can compute any
algebraic number. As a measure of complexity in this model, we define the
degree
of a root computation tree as the maximumdegree of any of its polynomials. A
bounded-degree root computation tree
has its degree bounded by some constant
unrelated to the size of its input. Thus, a quadratic computation tree is exactly a
bounded-degree root computation tree (of degree two).
Our impossibility results and degree lower bounds for these models imply the same
results for algorithms in more realistic models of computation that use as a black box
the corresponding primitives for constructing and representing algebraic numbers in
symbolic computation systems. Because ourresults are lower bounds, they also apply
a
fortiori
to weaker primitives, such as systems limited to
real
algebraic numbers, which
don'tinclude complex conjugation.
It is important to note that each of the above models can generate algebraic numbers
of unbounded degree. For instance, even the quadratic computation tree (compass and
straightedge model) can construct regular 2
k
-gons, whose coordinates are algebraic
numbers with degrees that are highpowersoftwo.Thus, to prove lower bounds and
impossibility results in these models, it is not sufficient to prove that a problem is
described by a high-degree polynomial; additional structure is needed.
Algebraic Graph Theory.
In algebraic graph theory, the properties of a graph are
examined via the spectra of several matrices associated with the graph. The
adjacency
matrix
A
=adj(
G
) of a graph
G
is the
n
n
matrix with
A
i,j
equal to 1 if there is
an edge between
i
and
j
and 0 otherwise. The
degree matrix
D
=deg(
G
) of
G
is the
n
×
n
matrix with
D
i,i
=deg(
v
i
). From these two matrices we define the
Laplacian
matrix
,
L
=lap(
G
)=
D
×
A
,andthe
transitionmatrix
,
T
=tran(
G
)=
D
−
1
A
.
−
Lemma 1.
Fo r a regular graph
G
,
adj(
G
)
,
lap(
G
)
, and
tran(
G
)
havethesamesetof
eigenvectors.
Lemma 2.
Fo r t hecycle on
n
vertices, theeigenvalues of
adj(
G
)
are
2cos(2
ˀk/n
)
,
for
0
≤
k<n
.
M obius Transformations.
We may represent each point
p
in the plane by a complex
number,
z
, whose real part represents
p
's
x
coordinate and whose imaginary part rep-
resents
p
's
y
coordinate. A
Mobiustransformation
is a fractional linear transformation,
z
(
az
+
b
)
/
(
cz
+
d
), defined by a 4-tuple (
a,b,c,d
) of complex numbers, or the
complex conjugate of such a transformation. We prove the following in the full version
of the paper.
ₒ
Lemma 3.
Given any two disjoint circles, a Mobiustransformationmapping them to
twoconcentric circles can be constructed using a quadratic computation tree.
