View in EDS PDF Full Text

Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain

Saved in:
Bibliographic Details
Title: Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
Description: Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed and gradually increasing the generality and abstraction of the theory. This volume presents the theory on the Boolean domain, and includes a thorough presentation of holographic algorithms, culminating in classifications of computational problems studied in exactly solvable models from statistical mechanics.
Authors: Jin-Yi Cai, Xi Chen
Resource Type: eBook.
Subjects: Homomorphisms (Mathematics), Combinatorial enumeration problems, Algebra, Boolean, Computational complexity
Categories: COMPUTERS / General
Database: eBook Collection (EBSCOhost)
FullText Links:
  – Type: ebook-pdf
Text:
  Availability: 0
Header DbId: nlebk
DbLabel: eBook Collection (EBSCOhost)
An: 1578684
RelevancyScore: 1077
AccessLevel: 6
PubType: eBook
PubTypeId: ebook
PreciseRelevancyScore: 1077.00524902344
IllustrationInfo
ImageInfo – Size: thumb
  Target: https://rps2images.ebscohost.com/rpsweb/othumb?id=NL$1578684$PDF&s=r
– Size: medium
  Target: https://rps2images.ebscohost.com/rpsweb/othumb?id=NL$1578684$PDF&s=d
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
– Name: Abstract
  Label: Description
  Group: Ab
  Data: Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed and gradually increasing the generality and abstraction of the theory. This volume presents the theory on the Boolean domain, and includes a thorough presentation of holographic algorithms, culminating in classifications of computational problems studied in exactly solvable models from statistical mechanics.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Jin-Yi+Cai%22">Jin-Yi Cai</searchLink><br /><searchLink fieldCode="AR" term="%22Xi+Chen%22">Xi Chen</searchLink>
– Name: TypePub
  Label: Resource Type
  Group: TypPub
  Data: eBook.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Homomorphisms+%28Mathematics%29%22">Homomorphisms (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+enumeration+problems%22">Combinatorial enumeration problems</searchLink><br /><searchLink fieldCode="DE" term="%22Algebra%2C+Boolean%22">Algebra, Boolean</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink>
– Name: SubjectBISAC
  Label: Categories
  Group: Su
  Data: <searchLink fieldCode="ZK" term="%22COMPUTERS+%2F+General%22">COMPUTERS / General</searchLink>
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=1578684
RecordInfo BibRecord:
  BibEntity:
    Classifications:
      – Code: 511.352
        Scheme: ddc
        Type: prePub
    Languages:
      – Code: eng
        Text: English
    Subjects:
      – SubjectFull: Homomorphisms (Mathematics)
        Type: general
      – SubjectFull: Combinatorial enumeration problems
        Type: general
      – SubjectFull: Algebra, Boolean
        Type: general
      – SubjectFull: Computational complexity
        Type: general
    Titles:
      – TitleFull: Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Jin-Yi Cai
      – PersonEntity:
          Name:
            NameFull: Xi Chen
      – PersonEntity:
          Name:
            NameFull: Jin-Yi Cai
      – PersonEntity:
          Name:
            NameFull: Xi Chen
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Type: published
              Y: 2017
            – D: 25
              M: 10
              Type: profile
              Y: 2017
          Identifiers:
            – Type: isbn-print
              Value: 9781107062375
            – Type: isbn-electronic
              Value: 9781108523721
          Numbering:
            – Type: volume
              Value: 00001
          Titles:
            – TitleFull: Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
              Type: main
ResultId 1