Our systems are now restored following recent technical disruption, and we’re working hard to catch up on publishing. We apologise for the inconvenience caused. Find out more

Item added to bagSorry, there was a problem getting your bag informationItem cannot be purchased with the existing contents of your bagItem unavailable online
✕

was added to your bag.

Please try again.

Sorry, this item cannot be purchased in the same transaction as the existing items in your bag.

Please complete the purchase of the items currently in your bag and then add this item in a separate transaction or visit Shopping Help.

Sorry, this product is not currently available to buy online. Please visit Shopping Help.

View bag and checkout
Remove item
✕

Are you sure you want to remove from your bag?

Recommended product

Popular links

Popular links

Complexity of Infinite-Domain Constraint Satisfaction

All titles
Complexity of Infinite-Domain Constraint Satisfaction

Complexity of Infinite-Domain Constraint Satisfaction

Manuel Bodirsky, Technische Universität Dresden
August 2021
This ISBN is for an eBook version which is distributed on our behalf by a third party.
Adobe eBook Reader
9781009158633
$162.99
USD
Adobe eBook Reader
USD
Hardback
✕

You are now leaving the Cambridge University Press & Assessment website. Your ebook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of print and copy limits of our ebook.

Continue
    Description

    Constraint Satisfaction Problems (CSPs) are natural computational problems that appear in many areas of theoretical computer science. Exploring which CSPs are solvable in polynomial time and which are NP-hard reveals a surprising link with central questions in universal algebra. This monograph presents a self-contained introduction to the universal-algebraic approach to complexity classification, treating both finite and infinite-domain CSPs. It includes the required background from logic and combinatorics, particularly model theory and Ramsey theory, and explains the recently discovered link between Ramsey theory and topological dynamics and its implications for CSPs. The book will be of interest to graduate students and researchers in theoretical computer science and to mathematicians in logic, combinatorics, and dynamics who wish to learn about the applications of their work in complexity theory.

    • The first monograph on complexity classification of constraint satisfaction problems
    • More than 150 examples illustrate the abstract results in concrete applications in mathematics and computer science
    • Self-contained and accessible to graduate students in theoretical computer science and mathematics

    Reviews & endorsements

    ‘… this book is essential reading for anyone with the vaguest interest in computational complexity, as well as for those curious about potential applications of model theory and universal algebra. It brings together decades of intense research by different research communities in a uniform format.’ Victor Lagerkvist, MathSciNet

    See more reviews

    Product details

    August 2021
    Adobe eBook Reader
    9781009158633
    0 pages
    This ISBN is for an eBook version which is distributed on our behalf by a third party.

    Often bought together

    Turing's Legacy
    Turing's Legacy

    : Hardback

    Developments from Turing's Ideas in Logic

    Introduction to Higher-Order Categorical Logic
    Introduction to Higher-Order Categorical Logic

    : Paperback

    Notes on Logic and Set Theory
    Notes on Logic and Set Theory

    : Paperback

    Abstract Recursion and Intrinsic Complexity
    Abstract Recursion and Intrinsic Complexity

    : Hardback

    Often bought together

    This title is available for institutional purchase via Cambridge Core

    Learn more
    cambridge core banner

    Related Journals

    Combinatorics, Probability and Computing
    Combinatorics, Probability and Computing

    : Journal

    Published bimonthly, Combinatorics, Probability & Computing is devoted to the three areas of combinatorics, probability theory and theoretical computer science. Topics covered include classical and algebraic graph theory, extremal set theory, matroid theory, probabilistic methods and random combinatorial structures; combinatorial probability and limit theorems for random combinatorial structures; the theory of algorithms (including complexity theory), randomised algorithms, probabilistic analysis of algorithms, computational learning theory and optimisation.

    The Review of Symbolic Logic
    The Review of Symbolic Logic

    : Journal

    The Review of Symbolic Logic is designed to cultivate research on theborders of logic, philosophy, and the sciences, and to supportsubstantive interactions between these disciplines. The journalwelcomes submissions in any of the following areas, broadly construed: - The general study of logical systems and their semantics,including non-classical logics and algebraic logic; - Philosophical logic and formal epistemology, including interactions with decision theory and game theory; - The history, philosophy, and methodology of logic and mathematics, including the history of philosophy of logic and mathematics; - Applications of logic to the sciences, such as computer science, cognitive science, and linguistics; and logical results addressing foundational issues in the sciences. The Review welcomes submissions in all these areas. (For informationon how to submit papers, see Guidelines below.) The Review beganpublication in June 2008.

    Mathematical Structures in Computer Science
    Mathematical Structures in Computer Science

    : Journal

    Mathematical Structures in Computer Science is a journal of theoretical computer science which focuses on the application of ideas from the structural side of mathematics and mathematical logic to computer science. The journal aims to bridge the gap between theoretical contributions and software design, publishing original papers of a high standard and broad surveys with original perspectives in all areas of computing, provided that ideas or results from logic, algebra, geometry, category theory or other areas of logic and mathematics form a basis for the work. The journal welcomes applications to computing based on the use of specific mathematical structures (e.g. topological and order-theoretic structures) as well as on proof-theoretic notions or results. The journal will also accept contributions in new interdisciplinary fields bridging computer science, quantum physics, mathematics and information theory. In particular, papers on quantum information processing and communication, as well as on the related issues in quantum language design will be considered. The journal is also interested in papers on computational modelling of epigenetics phenomena, protein-protein interaction, stochasticity in molecular cascades. Mathematical approches to System Biology will be welcomed, within the broad frame of post-genomic views of embryogenesis and evolution.

    Related Journals

    Also by this Author

    Contents

    Table of Contents

    • 1. Introduction to constraint satisfaction problems
    • 2. Model theory
    • 3. Primitive positive interpretations
    • 4. Countably categorical structures
    • 5. Examples
    • 6. Universal algebra
    • 7. Equality constraint satisfaction problems
    • 8. Datalog
    • 9. Topology
    • 10. Oligomorphic clones
    • 11. Ramsey theory
    • 12. Temporal constraint satisfaction problems
    • 13. Non-dichotomies
    • 14. Conclusion and outlook
    • References
    • Index.
      • Show more
    Courses
    Resources
    Additional Information
    About the authors
      Author
    • Manuel Bodirsky , Technische Universität Dresden

      Manuel Bodirsky is Professor at the Institute for Algebra in the Faculty of Mathematics at TU Dresden.

    Browse by related subject

     
    ✕

    Sorry, this item cannot be purchased in the same transaction as the existing items in your cart.

    Please complete the purchase of the items currently in your cart and then add this item in a separate transaction or contact

    Customer Services