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]
Previous Page Next Page