Complexity and Real Computation
Foreword by Richard M. Karp
- Publisher's listprice EUR 85.55
-
36 290 Ft (34 562 Ft + 5% VAT)
The price is estimated because at the time of ordering we do not know what conversion rates will apply to HUF / product currency when the book arrives. In case HUF is weaker, the price increases slightly, in case HUF is stronger, the price goes lower slightly.
- Discount 20% (cc. 7 258 Ft off)
- Discounted price 29 032 Ft (27 650 Ft + 5% VAT)
Subcribe now and take benefit of a favourable price.
Subscribe
36 290 Ft
Availability
Estimated delivery time: In stock at the publisher, but not at Prospero's office. Delivery time approx. 3-5 weeks.
Not in stock at Prospero.
Why don't you give exact delivery time?
Delivery time is estimated on our previous experiences. We give estimations only, because we order from outside Hungary, and the delivery time mainly depends on how quickly the publisher supplies the book. Faster or slower deliveries both happen, but we do our best to supply as quickly as possible.
Product details:
- Edition number 1998
- Publisher Springer
- Date of Publication 30 October 1997
- Number of Volumes 1 pieces, Book w. online files / update
- ISBN 9780387982816
- Binding Hardback
- No. of pages453 pages
- Size 235x155 mm
- Weight 956 g
- Language English
- Illustrations XVI, 453 p. With online files/update. Illustrations, black & white 0
Categories
Short description:
This book develops a formal theory of computation which integrates major themes of the classical theory and which applies directly to problems in mathematics, numerical analysis, and scientific computing. Following an extensive introduction are proofs and extensions of relevant theorems. Along the way, the authors consider such fundamental questions as: Is the Mandelbrot set decidable? Is the Hilbert Nullstellensatz intractable? And, What is the real complexity of Newton's method?
MoreLong description:
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.
MoreTable of Contents:
1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem ?P ? NP??.- 8 Newton?s Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bézout?s Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References.
More
