Borrow it
Coverart for item
The Resource Computability and complexity theory, Steven Homer, Alan L. Selman

Computability and complexity theory, Steven Homer, Alan L. Selman

Creator
Contributor
Summary
This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations. Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable. Substantial new content in this edition includes: a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp-Lipton. a chapter studying properties of the fundamental probabilistic complexity classes a study of the alternating Turing machine and uniform circuit classes. an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Toda a thorough treatment of the proof that IP is identical to PSPACE With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential and practical learning tool. Topics and features: Concise, focused materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes Contains information that otherwise exists only in research literature and presents it in a unified, simplified manner Provides key mathematical background information, including sections on logic and number theory and algebra Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes
Language
eng
Work
Publication
Edition
2nd ed.
Extent
1 online resource (xvi, 298 pages)
Contents
  • 1. Preliminaries
  • 2. Introduction to computability
  • 3. Undecidability
  • 4. Introduction to complexity theory
  • 5. Basic results of complexity theory
  • 6. Nondeterminism and NP-completeness
  • 7. Relative computability
  • 8. Nonuniform complexity
  • 9. Parallelism
  • 10. Probabilistic complexity classes
  • 11. Introduction to counting classes
  • 12. Interactive proof systems
Isbn
9781489989710
Instance
Label
Computability and complexity theory
Title
Computability and complexity theory
Statement of responsibility
Steven Homer, Alan L. Selman
Creator
Contributor
Subject
Language
eng
Summary
This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations. Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable. Substantial new content in this edition includes: a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp-Lipton. a chapter studying properties of the fundamental probabilistic complexity classes a study of the alternating Turing machine and uniform circuit classes. an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Toda a thorough treatment of the proof that IP is identical to PSPACE With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential and practical learning tool. Topics and features: Concise, focused materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes Contains information that otherwise exists only in research literature and presents it in a unified, simplified manner Provides key mathematical background information, including sections on logic and number theory and algebra Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes
Member of
Cataloging source
GW5XE
http://library.link/vocab/creatorName
Homer, S.
Dewey number
004
Illustrations
illustrations
Index
index present
Language note
English
LC call number
QA76
LC item number
.H66 2011
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
Selman, Alan L
Series statement
Texts in computer science,
http://library.link/vocab/subjectName
  • Computer science
  • Information theory
  • Computational complexity
  • Informatique
  • Computational complexity
  • Computer science
  • Information theory
Label
Computability and complexity theory, Steven Homer, Alan L. Selman
Instantiates
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 283-288) and indexes
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
1. Preliminaries -- 2. Introduction to computability -- 3. Undecidability -- 4. Introduction to complexity theory -- 5. Basic results of complexity theory -- 6. Nondeterminism and NP-completeness -- 7. Relative computability -- 8. Nonuniform complexity -- 9. Parallelism -- 10. Probabilistic complexity classes -- 11. Introduction to counting classes -- 12. Interactive proof systems
Control code
769643967
Dimensions
unknown
Edition
2nd ed.
Extent
1 online resource (xvi, 298 pages)
File format
unknown
Form of item
online
Isbn
9781489989710
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
  • 10.1007/978-1-4614-0682-2
  • 10.1007/978-1-4614-0
Other physical details
illustrations.
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)769643967
Label
Computability and complexity theory, Steven Homer, Alan L. Selman
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 283-288) and indexes
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
1. Preliminaries -- 2. Introduction to computability -- 3. Undecidability -- 4. Introduction to complexity theory -- 5. Basic results of complexity theory -- 6. Nondeterminism and NP-completeness -- 7. Relative computability -- 8. Nonuniform complexity -- 9. Parallelism -- 10. Probabilistic complexity classes -- 11. Introduction to counting classes -- 12. Interactive proof systems
Control code
769643967
Dimensions
unknown
Edition
2nd ed.
Extent
1 online resource (xvi, 298 pages)
File format
unknown
Form of item
online
Isbn
9781489989710
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
  • 10.1007/978-1-4614-0682-2
  • 10.1007/978-1-4614-0
Other physical details
illustrations.
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)769643967

Subject

Member of

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

Library Links

Structured data from the Bibframe namespace is licensed under the Creative Commons Attribution 4.0 International License by University of Missouri Libraries. Additional terms may apply to data associated with third party namespaces.
Processing Feedback ...