TOPICS IN REAL AND COMPLEX NUMBER COMPLEXITY THEORY 3

The paper is written in the style of an exposition. We do not cover all the

interesting work that has been done since introduction of the Blum-Shub-Smale

model about 20 years ago. Instead, the focus will be on topics the authors have

also worked on themselves. With one exception dealing with long transparent

proofs we most of the time do not present full proofs of the results treated. Instead

it is tried to give the reader a feeling of the ideas behind such proofs, some more

detailed and some not. More interested readers will easily find all details in the

cited literature. Finally, we expect the reader to have a basic knowledge of classical

complexity theory and the theory of NP-completeness [44], [1]. This is not crucial

for understanding the flow of ideas, but we frequently refer to the Turing model

in order to pinpoint similarities and differences between real number and classical

complexity theory.

2. A motivating example

A typical problem in kinematics asks for finding suitable mechanisms that fulfil

given motion tasks. Having chosen a mechanism which in principle can solve the

problem the dimensions of the mechanism’s components have to be determined. In

its mathematical formulation this often leads to solving polynomial systems. As

example of such a motion synthesis task consider the following one. Construct a

mechanism which is able to generate a rigid body motion such that some constraints

are satisfied. Constraints, for example, could be certain positions that have to be

reachable by the mechanism. Figure

11

shows as typical example the motion of a

plane in relation to a fixed base. Here, a ξ − η-system with its origin P is attached

to the moving plane and a x − y-system is attached to the base. The rigid body

motion now can be defined by certain poses of the ξ − η-system with respect to the

x − y-system.

y

y

p,1

x

p,1

x

P1

P2

P3

P4

P5

A0

γ1

η

η

η

η η

ξ

ξ

ξ

ξ

ξ

Figure 1. Synthesis-task “Motion generation for five precision poses”

The engineer’s task is to choose a suitable mechanism being able to solve the

task. Then, its precise dimensions have to be determined. Here it is often desirable

to perform a complete synthesis, i.e., to find all possible realizations of a synthe-

sis task. This gives the engineer the possibility to choose particular mechanisms

optimized with respect to additional criteria not reflected in the mathematical de-

scription, and to fine-tune. A class of mechanisms suitable for the above task are

so-called Stephenson mechanisms, one example of which is shown in Figure 2.

1the

figures are taken from [92]