• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    The Complexity of Modular Counting in Constraint Satisfaction Problems. 
    •   QMRO Home
    • Queen Mary University of London Theses
    • Theses
    • The Complexity of Modular Counting in Constraint Satisfaction Problems.
    •   QMRO Home
    • Queen Mary University of London Theses
    • Theses
    • The Complexity of Modular Counting in Constraint Satisfaction Problems.
    ‌
    ‌

    Browse

    All of QMROCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    ‌
    ‌

    Administrators only

    Login
    ‌
    ‌

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    The Complexity of Modular Counting in Constraint Satisfaction Problems.

    View/Open
    Faben_J_PhD_final.pdf (510.9Kb)
    Publisher
    Queen Mary University of London
    Metadata
    Show full item record
    Abstract
    Constraint Satisfaction Problems are a broad class of combinatorial problems, including several classical decision problems such as graph colouring and SAT, and a range of problems from other areas, including statistical physics, DNA sequencing and scheduling problems. There are a variety of dichotomy theorems for various subclasses of CSP in various complexity classes, one of the most noteable is Bulatov's proof that a dichotomy holds for #CSP [Bul08], that is, all #CSP problems are either #P-complete or in FP. In this thesis, we look at the complexity of modular counting in some re- stricted classes of CSP, answering questions of the sort \What is the number of solutions to this CSP modulo k?" for various k. In particular, we discuss CSP restricted to relations on the domain of size 2, Boolean CSP or Generalised Sat- is ability, and CSP restricted to a single, symmetric, binary relation, or Graph Homomorphism. In [CH96], Creignou and Hermann proved a dichotomy the- orem for counting solutions to Boolean CSP problems, and characterised the easy cases. We provide a proof of a dichotomy theorem for #kBoolean CSP for all k, characterising the easy cases. In [DG00], Dyer and Greenhill proved a dichotomy theorem for counting the 3 4 number of homomorphisms into a xed graph H, or H-colouring, and provided a characterisation of the types of H for which the problem is tractable. We give some results on L H-colouring. We give a conjectured dichotomy for the general L H-colouring problem, based on a condition related to the automor- phism group of H. We show that this dichotomy holds for the case in which H is restricted to be a tree, and give some results about the complexity of deter- mining, given an arbitrary H, whether the associated H-colouring problem is tractable assuming the dichotomy holds.
    Authors
    Faben, John
    URI
    http://qmro.qmul.ac.uk/xmlui/handle/123456789/8488
    Collections
    • Theses [3600]
    Copyright statements
    The copyright of this thesis rests with the author and no quotation from it or information derived from it may be published without the prior written consent of the author
    Twitter iconFollow QMUL on Twitter
    Twitter iconFollow QM Research
    Online on twitter
    Facebook iconLike us on Facebook
    • Site Map
    • Privacy and cookies
    • Disclaimer
    • Accessibility
    • Contacts
    • Intranet
    • Current students

    Modern Slavery Statement

    Queen Mary University of London
    Mile End Road
    London E1 4NS
    Tel: +44 (0)20 7882 5555

    © Queen Mary University of London.