The Resource Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale, (electronic resource)

Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale, (electronic resource)

Label
Complexity and Real Computation
Title
Complexity and Real Computation
Statement of responsibility
by Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale
Creator
Contributor
Author
Subject
Language
  • eng
  • eng
Summary
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
Cataloging source
PQKB
http://library.link/vocab/creatorName
Blum, Lenore
Dewey number
004.0151
Image bit depth
0
Language note
English
LC call number
QA75.5-76.95
Literary form
non fiction
http://library.link/vocab/relatedWorkOrContributorName
  • Cucker, Felipe.
  • Shub, Michael.
  • Smale, Steve.
http://library.link/vocab/subjectName
  • Computer science
  • Computers
  • Mathematical logic
  • Computer Science
  • Theory of Computation
  • Mathematical Logic and Foundations
Label
Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale, (electronic resource)
Instantiates
Publication
Note
Bibliographic Level Mode of Issuance: Monograph
Antecedent source
mixed
Carrier category
online resource
Carrier category code
cr
Color
not applicable
Content category
text
Content type code
txt
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
Dimensions
unknown
Extent
1 online resource (XVI, 453 p.)
File format
multiple file formats
Form of item
online
Isbn
9781461207016
Level of compression
uncompressed
Media category
computer
Media type code
c
Other control number
10.1007/978-1-4612-0701-6
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
  • (CKB)3400000000089234
  • (SSID)ssj0001296205
  • (PQKBManifestationID)11802290
  • (PQKBTitleCode)TC0001296205
  • (PQKBWorkID)11347728
  • (PQKB)11033524
  • (DE-He213)978-1-4612-0701-6
  • (EXLCZ)993400000000089234
Label
Complexity and Real Computation, by Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale, (electronic resource)
Publication
Note
Bibliographic Level Mode of Issuance: Monograph
Antecedent source
mixed
Carrier category
online resource
Carrier category code
cr
Color
not applicable
Content category
text
Content type code
txt
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
Dimensions
unknown
Extent
1 online resource (XVI, 453 p.)
File format
multiple file formats
Form of item
online
Isbn
9781461207016
Level of compression
uncompressed
Media category
computer
Media type code
c
Other control number
10.1007/978-1-4612-0701-6
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
  • (CKB)3400000000089234
  • (SSID)ssj0001296205
  • (PQKBManifestationID)11802290
  • (PQKBTitleCode)TC0001296205
  • (PQKBWorkID)11347728
  • (PQKB)11033524
  • (DE-He213)978-1-4612-0701-6
  • (EXLCZ)993400000000089234

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...