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 P 1 P 2 P 3 P 4 P 5 A 0 γ 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. 1 the figures are taken from [92]

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.