Nothing Special   »   [go: up one dir, main page]
Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×

Menu links

  1. Browse
    1. Subjects
      1. Subjects (A-D)
        1. Anthropology
        2. Archaeology
        3. Area Studies
        4. Art
        5. Chemistry
        6. Classical Studies
        7. Computer Science
        8. Drama, Theatre, Performance Studies
      2. Subjects (E-K)
        1. Earth and Environmental Science
        2. Economics
        3. Education
        4. Engineering
        5. English Language Teaching – Resources for Teachers
        6. Film, Media, Mass Communication
        7. General Science
        8. Geography
        9. History
      3. Subjects (L-O)
        1. Language and Linguistics
        2. Law
        3. Life Sciences
        4. Literature
        5. Management
        6. Materials Science
        7. Mathematics
        8. Medicine
        9. Music
        10. Nutrition
      4. Subjects (P-Z)
        1. Philosophy
        2. Physics and Astronomy
        3. Politics and International Relations
        4. Psychiatry
        5. Psychology
        6. Religion
        7. Social Science Research Methods
        8. Sociology
        9. Statistics and Probability
    2. Open access
      1. All open access publishing
        1. Open access
        2. Open access journals
        3. Research open journals
        4. Journals containing open access
        5. Open access articles
        6. Open access books
        7. Open access Elements
    3. Journals
      1. Explore
        1. All journal subjects
        2. Search journals
      2. Open access
        1. Open access journals
        2. Research open journals
        3. Journals containing open access
        4. Open access articles
      3. Collections
        1. Cambridge Forum
        2. Cambridge Law Reports Collection
        3. Cambridge Prisms
        4. Research Directions
    4. Books
      1. Explore
        1. Books
        2. Open access books
        3. New books
        4. Flip it Open
      2. Collections
        1. Cambridge Companions
        2. Cambridge Editions
        3. Cambridge Histories
        4. Cambridge Library Collection
        5. Cambridge Shakespeare
        6. Cambridge Handbooks
      3. Collections (cont.)
        1. Dispute Settlement Reports Online
        2. Flip it Open
        3. Hemingway Letters
        4. Shakespeare Survey
        5. Stahl Online
        6. The Correspondence of Isaac Newton
    5. Elements
      1. Explore
        1. About Elements
        2. Elements series
        3. Open access Elements
        4. New Elements
      2. Subjects (A-E)
        1. Anthropology
        2. Archaeology
        3. Classical Studies
        4. Computer Science
        5. Drama, Theatre, Performance Studies
        6. Earth and Environmental Sciences
        7. Economics
        8. Education
        9. Engineering
      3. Subjects (F-O)
        1. Film, Media, Mass Communication
        2. History
        3. Language and Linguistics
        4. Law
        5. Life Sciences
        6. Literature
        7. Management
        8. Mathematics
        9. Medicine
        10. Music
      4. Subjects (P-Z)
        1. Philosophy
        2. Physics and Astronomy
        3. Politics and International Relations
        4. Psychology
        5. Religion
        6. Sociology
        7. Statistics and Probability
    6. Textbooks
      1. Explore
        1. Cambridge Higher Education
        2. Title list
        3. New titles
    7. Collections
      1. Book collections
        1. Cambridge Companions
        2. Cambridge Editions
        3. Cambridge Histories
        4. Cambridge Library Collection
        5. Cambridge Shakespeare
        6. Cambridge Handbooks
      2. Book collections (cont.)
        1. Dispute Settlement Reports Online
        2. Flip it Open
        3. Hemingway Letters
        4. Shakespeare Survey
        5. Stahl Online
        6. The Correspondence of Isaac Newton
      3. Journal collections
        1. Cambridge Forum
        2. Cambridge Law Reports Collection
        3. Cambridge Prisms
        4. Research Directions
      4. Series
        1. All series
    8. Partners
      1. Partners
        1. Agenda Publishing
        2. Amsterdam University Press
        3. Anthem Press
        4. Boydell & Brewer
        5. Bristol University Press
        6. Edinburgh University Press
        7. Emirates Center for Strategic Studies and Research
        8. Facet Publishing
      2. Partners (cont.)
        1. Foundation Books
        2. Intersentia
        3. ISEAS-Yusof Ishak Institute
        4. Jagiellonian University Press
        5. Royal Economic Society
        6. Unisa Press
        7. The University of Adelaide Press
        8. Wits University Press
  2. Services
    1. About
      1. About Cambridge Core
        1. About
        2. Accessibility
        3. CrossMark policy
        4. Ethical Standards
      2. Environment and sustainability
        1. Environment and sustainability
        2. Reducing print
        3. Journals moving to online only
      3. Guides
        1. User guides
        2. User Guides and Videos
        3. Support Videos
        4. Training
      4. Help
        1. Cambridge Core help
        2. Contact us
        3. Technical support
    2. Agents
      1. Services for agents
        1. Services for agents
        2. Journals for agents
        3. Books for agents
        4. Price list
    3. Authors
      1. Journals
        1. Journals
        2. Journal publishing statistics
        3. Corresponding author
        4. Seeking permission to use copyrighted material
        5. Publishing supplementary material
        6. Writing an effective abstract
        7. Journal production - FAQs
      2. Journals (cont.)
        1. Author affiliations
        2. Co-reviewing policy
        3. Digital Author Publishing Agreement - FAQs
        4. Anonymising your manuscript
        5. Publishing open access
        6. Converting your article to open access
        7. Publishing Open Access - webinars
      3. Journals (cont.)
        1. Preparing and submitting your paper
        2. Publishing an accepted paper
        3. Promoting your published paper
        4. Measuring impact
        5. Journals artwork guide
        6. Using ORCID
      4. Books
        1. Books
        2. Marketing your book
        3. Author guides for Cambridge Elements
    4. Corporates
      1. Corporates
        1. Commercial reprints
        2. Advertising
        3. Sponsorship
        4. Book special sales
        5. Contact us
    5. Editors
      1. Information
        1. Journal development
        2. Peer review for editors
        3. Open access for editors
        4. Policies and guidelines
      2. Resources
        1. The editor's role
        2. Open research for editors
        3. Engagement and promotion
        4. Blogging
        5. Social media
    6. Librarians
      1. Information
        1. Open Access for Librarians
        2. Transformative agreements
        3. Transformative Agreements - FAQs
        4. Evidence based acquisition
        5. ebook news & updates
        6. Cambridge libraries of the world podcast
        7. Purchasing models
        8. Journals Publishing Updates
      2. Products
        1. Cambridge frontlist
        2. Cambridge journals digital archive
        3. Hot topics
        4. Other digital products
        5. Perpetual access products
        6. Price list
        7. Developing country programme
        8. New content
      3. Tools
        1. Eligibility checker
        2. Transformative agreements
        3. KBART
        4. MARC records
        5. Using MARCEdit for MARC records
        6. Inbound OpenURL specifications
        7. COUNTER report types
      4. Resources
        1. Catalogues and resources
        2. Making the most of your EBA
        3. Posters
        4. Leaflets and brochures
        5. Additional resources
        6. Find my sales contact
        7. Webinars
        8. Read and publish resources
    7. Peer review
      1. Peer review
        1. How to peer review journal articles
        2. How to peer review book proposals
        3. How to peer review Registered Reports
        4. Peer review FAQs
        5. Ethics in peer review
        6. Online peer review systems
        7. A guide to Publons
    8. Publishing ethics
      1. Journals
        1. Publishing ethics guidelines for journals
        2. Core editorial policies for journals
        3. Authorship and contributorship for journals
        4. Affiliations for journals
        5. Research ethics for journals
        6. Competing interests and funding for journals
      2. Journals (cont.)
        1. Data and supporting evidence for journals
        2. Misconduct for journals
        3. Corrections, retractions and removals for journals
        4. Versions and adaptations for journals
        5. Libel, defamation and freedom of expression
        6. Business ethics journals
      3. Books
        1. Publishing ethics guidelines for books
        2. Core editorial policies for books
        3. Authorship and contributorship for books
        4. Affiliations for books
        5. Research ethics for books
        6. Competing interests and funding for books
      4. Books (cont.)
        1. Data and supporting evidence for books
        2. Misconduct for books
        3. Corrections, retractions and removals for books
        4. Versions and adaptations for books
        5. Libel, defamation and freedom of expression
        6. Business ethics books
    9. Publishing partners
      1. Publishing partners
        1. Publishing partnerships
        2. Partner books
        3. eBook publishing partnerships
        4. Journal publishing partnerships
      2. Publishing partners (cont.)
        1. Journals publishing
        2. Customer support
        3. Membership Services
        4. Our Team
  3. Open research
    1. Open access policies
      1. Open access policies
        1. Open research
        2. Open access policies
        3. Cambridge University Press and Plan S
        4. Text and data mining
        5. Preprint policy
        6. Social sharing
      2. Journals
        1. Open access journals
        2. Gold Open Access journals
        3. Transformative journals
        4. Green Open Access policy for journals
        5. Transparent pricing policy for journals
      3. Books and Elements
        1. Open access books
        2. Gold open access books
        3. Green Open Access policy for books
        4. Open access Elements
    2. Open access publishing
      1. About open access
        1. Open research
        2. Open Access Week
        3. What is open access?
        4. Open access glossary
        5. Open access myths
        6. Hybrid Open Access FAQs
        7. Eligibility checker
      2. Open access resources
        1. Open access resources
        2. Benefits of open access
        3. Creative commons licences
        4. Funder policies and mandates
        5. Article type definitions
        6. Convert your article to Open Access
        7. Open access video resources
    3. Open research initiatives
      1. Research transparency
        1. Transparency and openness
        2. Open Practice Badges
        3. OA organisations, initiatives & directories
        4. Registered Reports
        5. Annotation for Transparent Inquiry (ATI)
      2. Journal flips
        1. Open access journal flips
        2. OA Journal Flip FAQs
      3. Flip it Open
        1. Flip it Open
        2. Flip it Open FAQs
    4. Open access funding
      1. Open access funding
        1. Funding open access publication
        2. Cambridge Open Equity Initiative
        3. Completing a RightsLink (open access) transaction
    5. Cambridge Open Engage
      1. Cambridge Open Engage
        1. Cambridge Open Engage
        2. Partner With Us
        3. Branded Hubs
        4. Event Workspaces
        5. Partner Resources
        6. APSA Preprints
        7. APSA Preprints FAQs
  1. Home
  2. Books
  3. Computational Complexity
  • Cited by 243
Publisher:
Cambridge University Press
Online publication date:
June 2012
Print publication year:
2008
Online ISBN:
9780511804106
DOI:
https://doi.org/10.1017/CBO9780511804106
Subjects:
Algorithmics, Complexity, Computer Algebra, Computational Geometry, Computer Science
Information

Book description

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.

Reviews

"This interesting book... is refreshing to read his [Goldreichs'] opinions... The very strong focus on conceptual issues makes the book indispensible as a reference volume for research libraries."
M. Bona, University of Florida, CHOICE

"This book provides very well developed material that should interest advanced students either studying or doing new work on computational complexity. It would also be a valuable text for professionals challenged with solving "hard" computing problems of intending to exploit these types of problems when designing of new types computing systems."
Brian A. Lawler, Software Engineering Notes

"The book offers a conceptual perspective on several sub-areas of complexity theory and is intended to be used as a textbook for students and educators as well as for experts who seek an overview of of several sub-areas."
Gerhard Lischke, Mathematical Reviews

Refine List

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

Contents

Contents

Metrics

Altmetric attention score

Full text views

Total number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...

Book summary page views

Total views: 0 *
Loading metrics...

* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

Usage data cannot currently be displayed.