Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

1998 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Complexity and Real Computation

verfasst von: Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale

Verlag: Springer New York

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Computational complexity theory provides a framework for understanding the cost of solving computational problems, as measured by the requirement for resources such as time and space. The objects of study are algorithms defined within a formal model of computation. Upper bounds on the computational complexity of a problem are usually derived by constructing and analyzing specific algorithms. Meaningful lower bounds on computational complexity are harder to come by, and are not available for most problems of interest. The dominant approach in complexity theory is to consider algorithms as oper­ ating on finite strings of symbols from a finite alphabet. Such strings may represent various discrete objects such as integers or algebraic expressions, but cannot rep­ resent real or complex numbers, unless the numbers are rounded to approximate values from a discrete set. A major concern of the theory is the number of com­ putation steps required to solve a problem, as a function of the length of the input string.

Inhaltsverzeichnis

Frontmatter

Basic Development

Frontmatter
1. Introduction
Abstract
The classical theory of computation had its origins in the work of logicians—of Gödel, Turing, Church, Kleene, Post, among others— in the 1930s. The model of computation that developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
2. Definitions and First Properties of Computation
Abstract
We begin the development of our theory of computation with the definition of a finite-dimensional machine over a ring. Although it is necessary to define a machine to be a more general object in order to fully develop a uniform theory —in particular with regard to complexity issues— a great deal can already be gleaned from the finite-dimensional case.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
3. Computation over a Ring
Abstract
A pillar of the classical theory of computation is the existence of a universal Turing machine, a machine that can compute any computable function. This theoretical construct foretold and provides a foundation for the modern general-purpose computer. Classical constructions of universal machines generally utilize computable encodings of finite sequences of integers by a single integer in finite time. These codings also ensure that our theory of finite-dimensional machines over ℤ is sufficient to capture the full classical theory. However, such computable codings are not possible over the real numbers. Nor, from a strictly algebraic point of view, are they necessarily desirable. If we wish to construct universal machines over the reals, and to develop a general theory of computation, we are led naturally to consider machines that can handle finite but unbounded sequences. This in fact is closer to Turing’s original approach.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
4. Decision Problems and Complexity over a Ring
Abstract
Classical complexity theory deals primarily with combinatorial (discrete, integer) problems. We extend the theory here to consider a wider class of problems.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
5. The Class NP and NP-Complete Problems
Abstract
Although it may not be at all obvious given a polynomial over R how to decide whether it has a zero over R, it is a straightforward procedure to verify a solution that may be presented to us. Just plug the purported solution into the polynomial and evaluate it. Is this verification tractable in our model of computation? An affirmative answer will depend on the underlying mathematical properties of the ring or field, as well as our measure of complexity, and is at the core of the notion of NP.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
6. Integer Machines
Abstract
Computations with integers are at the core of a long-standing tradition in both computer science and number theory. A common feature is a measure of magnitude of an integer x given by the number of zeros and ones necessary to write the binary expansion of x (i.e.,\( \left\lceil {\log (|{\text{x}}| + 1)} \right\rceil \)). The relevant complexity measure is the bit cost. In the first section of this chapter, we show that machines over ℤ with bit cost and over ℤ2 with unit cost are polynomially equivalent. Thus, we refer to either setting as classical.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
7. Algebraic Settings for the Problem “P ≠ NP?”
Abstract
When complexity theory is studied over an arbitrary unordered field K, the classical theory is recaptured with K = ℤ2. The fundamental result that the Hilbert Nullstellensatz as a decision problem is NP-complete over K allows us to reformulate and investigate complexity questions within an algebraic framework and to develop transfer principles for complexity theory.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
Backmatter

Some Geometry of Numerical Algorithms

Frontmatter
8. Newton’s Method
Abstract
We have called Newton’s method the “…’ search algorithm’ sine qua non of numerical analysis and scientific computation.” Yet we have seen that even for a polynomial of one complex variable we cannot decide if Newton’s method will converge to a root of the polynomial on a given input. In this chapter we begin a more comprehensive study of Newton’s method. We introduce quantities α, β, and γ which play an important role in analyzing the complexity of algorithms that approximate the solutions of systems of equations. Our main results, Theorems 1 and 2, give the speed of convergence to a root in terms of these quantities, while other results such as Proposition 3 estimate them. In particular, Theorem 2 gives us a criterion, computable at a point x, to confirm that x is “close” to an actual zero ζ of a system of equations. Here close is defined in a strong sense and Newton’s method doubles precision at each step starting with x.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
9. Fundamental Theorem of Algebra: Complexity Aspects
Abstract
This chapter is devoted to producing a complexity analysis of a “homotopy method” for finding approximately a zero of a polynomial. The homotopy method is realized as a sequence of applications of Newton’s method. This algorithm is a prototype of the main methods of numerical analysis for solving a nonlinear system of equations. The complexity analysis here (and extensions in later chapters) gives a depth of understanding of these methods which is missing in the usual treatment based on convergence proofs. In this chapter we only consider the one-variable case. We use from the previous chapter only the easily proved Proposition 2. We also use a result from the theory of Schlicht functions due to Loewner.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
10. Bézout’s Theorem
Abstract
Bézout’s Theorem is the n-dimensional generalization of the Fundamental Theorem of Algebra. It “counts” the number of solutions of a system of n complex polynomial equations in n-unknowns. It is the goal of this chapter to prove Bézout’s Theorem. In Chapter 16 we use Bézout’s Theorem as a tool to derive geometric upper bounds on the number of connected components of semi-algebraic sets and complexity-theoretic lower bounds on some problems such as the Knapsack.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
11. Condition Numbers and the Loss of Precision of Linear Equations
Abstract
The condition number of an invertible real or complex n x n matrix A is defined as
$$ \kappa (A) = \left\| A \right\|\;\left\| {{{A}^{{ - 1}}}} \right\|, $$
where ‖A‖ is the operator norm
$$ \left\| A \right\| = \mathop{{\sup }}\limits_{{x \ne 0}} \frac{{\left\| {Ax} \right\|}}{{\left\| x \right\|}} $$
and ℝ n or ℂ n is given the usual inner product. The condition number measures the relative error in the solution of the system of linear equations
$$ {\text{Ax = v}}{\text{.}} $$
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
12. The Condition Number for Nonlinear Problems
Abstract
The goal of this chapter is to describe a measure of condition for problems that search for a solution of nonlinear systems of equations. Eventually a condition number μ is defined as a bound on the infinitesimal error of a solution caused by an infinitesimal error in the defining system of equations. With our emphasis on polynomial systems, we impose a norm on the space of such systems that reflects an important computational invariant, the distance between the zeros. To avoid the distortion caused by very large zeros, the analysis and metrics are defined in a projective space setting. The result is a unitarily invariant theory.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
13. The Condition Number in ℙ(H (d))
Abstract
In this chapter we study the condition numbers μ(f) and μnorm(f) as functions on ℙ(H (d)) in greater depth. Our main theorem is proven in Section 13.6.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
14. Complexity and the Condition Number
Abstract
The focus of this chapter is on the result that the complexity of a continuation algorithm can be bounded essentially by the square of the condition number of the homotopy.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
15. Linear Programming
Abstract
The aim of this chapter is to prove that the linear programming feasibility problem over ℚ can be solved in polynomial time. As a preliminary step, in Section 15.1 we show that inputs for rational machines can be supposed to be given by pairs of integers without substantially altering the complexity of the considered problem. In Section 15.2 we define an auxiliary problem which is a modification of the linear programming optimization problem and exhibit an algorithm to solve it with a homotopy method. The proof of correctness of this algorithm relies on the α theorem for Newton’s method proved in Chapter 8. In the two sections following 15.2 we first reduce the LPF over ℚ to this auxiliary problem and then prove that the algorithm resulting from this reduction is polynomial time. The proof relies on an efficient method for solving linear systems over ℚ which is developed in Section 15.5.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
Backmatter

Complexity Classes over the Reals

Frontmatter
16. Deterministic Lower Bounds
Abstract
The aim of this chapter is to provide a general technique for computing lower bounds for decision problems over the reals. These bounds come from upper bounds on the number of connected components of real algebraic sets. Besides being interesting in their own right, results proved here are used in later chapters.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
17. Probabilistic Machines
Abstract
Probabilistic methods are widely used in the design and analysis of algorithms. We have already seen several examples of this. In Chapter 11 we computed bounds for the expected loss of precision in solving large linear systems. This expected value suggests why, in general, we do not lose much precision solving linear systems.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
18. Parallel Computations
Abstract
If time is of the essence in solving a problem, we may be willing to devote the resources of many computers to its resolution. It is a challenge to formulate an appropriate mathematical notion of parallel machine over the reals.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
19. Some Separations of Complexity Classes
Abstract
In this chapter we continue to study the nature of parallel computation. The focus now is the limits of the power of parallelism. Thus, in Section 19.1 we prove that there are problems in Pℝ that cannot be efficiently parallelized. These problems are not in NCℝ. Section 19.2 contains lower bound estimates for parallel time in terms of the number of connected components as in Chapter 16.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
20. Weak Machines
Abstract
In this chapter we study machines over ℝ that penalize multiplication by modifying their cost in such a way that iterated multiplications become increasingly expensive. This situation is close to the classical where iterated multiplications can generate very large numbers and thus cause an increase in running time. We show that the complexity determined by this modified cost is closely related to the behavior of the algorithm on integer inputs in a very precise sense.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
21. Additive Machines
Abstract
A number of computational problems considered thus far have algorithms that make no use of multiplication or division. This is the case for the Knapsack or Traveling Salesman problems.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
22. Nonuniform Complexity Classes
Abstract
In Part I (Chapters 2 and 3) we introduced finite-dimensional machines with inputs from R n for some n ∈ ℕ and (uniform) machines whose inputs are from R n for all n ∈ ℕ. On the other hand, one can imagine a machine where inputs are taken from R ∞ but where the program to be executed depends on the size of the given input. The simplest example of such a machine is a family of finite-dimensional machines containing one machine for each input dimension. These machines are called nonuniform.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
23. Descriptive Complexity
Abstract
Complexity classes over a ring R are classes of problems categorized according to their solvability with respect to a given machine model and prescribed resource restrictions. We have seen various such classifications in the preceding chapters. In this chapter we show that a number of classes can be characterized in terms of the “complexity” of their descriptions. This provides machine-independent characterizations of important complexity classes and sheds some light on their comparison.
Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
Backmatter
Metadaten
Titel
Complexity and Real Computation
verfasst von
Lenore Blum
Felipe Cucker
Michael Shub
Steve Smale
Copyright-Jahr
1998
Verlag
Springer New York
Electronic ISBN
978-1-4612-0701-6
Print ISBN
978-1-4612-6873-4
DOI
https://doi.org/10.1007/978-1-4612-0701-6