Complexity and Real Computation

Blum, Lenore; Cucker, Felipe; Shub, Michael; Smale, Steve

ISBN 10: 0387982817 / ISBN 13: 9780387982816

Editore: Springer, 1997

Used book that is clean, average condition without any missing pages. Codice articolo EBBV.0387982817.G

Riassunto:

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. Upper bounds on the computational complexity of a problem are usually derived by constructing and analyzing specific algorithms.

Contenuti: 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.

Dati bibliografici

Titolo: Complexity and Real Computation
Casa editrice: Springer
Data di pubblicazione: 1997
Legatura: Rilegato
Condizione: good