Coverart for item
The Resource Complexity theory : exploring the limits of efficient algorithms, Ingo Wegener

Complexity theory : exploring the limits of efficient algorithms, Ingo Wegener

Label
Complexity theory : exploring the limits of efficient algorithms
Title
Complexity theory
Title remainder
exploring the limits of efficient algorithms
Statement of responsibility
Ingo Wegener
Creator
Subject
Language
  • eng
  • ger
  • eng
Summary
"Complexity theory is the theory of determining the necessary resources for the solution of algorithmic problems and, therefore, the limits of what is possible with the available resources. An understanding of these limits prevents the search for non-existing efficient algorithms." "This textbook considers randomization as a key concept and emphasizes the interplay between theory and practice. New branches of complexity theory continue to arise in response to new algo-rithmic concepts, and its results - such as the theory of NP-completeness - have influenced the development of all areas of computer science. The topics selected have implications for concrete applications, and the significance of complexity theory for today's computer science is stressed throughout."--Jacket
Cataloging source
GW5XE
http://library.link/vocab/creatorName
Wegener, Ingo
Dewey number
518.1
Illustrations
illustrations
Index
index present
Language note
Translated from the German
LC call number
QA9.58
LC item number
.W44 2005eb
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/subjectName
  • Algorithms
  • Informatique
  • Algorithms
  • Complexiteit
  • Algoritmen
  • Automatentheorie
Target audience
specialized
Label
Complexity theory : exploring the limits of efficient algorithms, Ingo Wegener
Instantiates
Publication
Bibliography note
Includes bibliographical references (pages 295-299) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
Algorithmic Problems & Their Complexity -- Fundamental Complexity Classes -- Reductions -- Algorithmic Relationships Between Problems -- The Theory of NP-Completeness -- NP-complete and NP-equivalent Problems -- The Complexity Analysis of Problems -- The Complexity of Approximation Problems -- Classical Results -- The Complexity of Black Box Problems -- Additional Complexity Classes and Relationships Between Complexity Classes -- Interactive Proofs -- The PCP Theorem and the Complexity of Approximation Problems -- Further Topics From Classical Complexity Theory -- The Complexity of Non-uniform Problems -- Communication Complexity -- The Complexity of Boolean Functions
Control code
262677781
Dimensions
unknown
Extent
1 online resource (xi, 308 pages)
Form of item
online
Isbn
9783540210450
Lccn
2005920530
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/3-540-27477-4
Other physical details
illustrations
http://library.link/vocab/ext/overdrive/overdriveId
978-3-540-21045-0
Specific material designation
remote
System control number
(OCoLC)262677781
Label
Complexity theory : exploring the limits of efficient algorithms, Ingo Wegener
Publication
Bibliography note
Includes bibliographical references (pages 295-299) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
Algorithmic Problems & Their Complexity -- Fundamental Complexity Classes -- Reductions -- Algorithmic Relationships Between Problems -- The Theory of NP-Completeness -- NP-complete and NP-equivalent Problems -- The Complexity Analysis of Problems -- The Complexity of Approximation Problems -- Classical Results -- The Complexity of Black Box Problems -- Additional Complexity Classes and Relationships Between Complexity Classes -- Interactive Proofs -- The PCP Theorem and the Complexity of Approximation Problems -- Further Topics From Classical Complexity Theory -- The Complexity of Non-uniform Problems -- Communication Complexity -- The Complexity of Boolean Functions
Control code
262677781
Dimensions
unknown
Extent
1 online resource (xi, 308 pages)
Form of item
online
Isbn
9783540210450
Lccn
2005920530
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/3-540-27477-4
Other physical details
illustrations
http://library.link/vocab/ext/overdrive/overdriveId
978-3-540-21045-0
Specific material designation
remote
System control number
(OCoLC)262677781

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012
    • Engineering Library & Technology CommonsBorrow it
      W2001 Lafferre Hall, Columbia, MO, 65211, US
      38.946102 -92.330125
Processing Feedback ...