Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain

Author： Jin-Yi Cai; Xi Chen  

Publisher： Cambridge University Press‎

Publication year： 2017

E-ISBN: 9781108514781

P-ISBN(Paperback): 9781107062375

Subject： TP301.5 Computational complexity theory

Keyword： 自动化技术、计算机技术

Language： ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

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.

Chapter

Cover

Half title

Title

Copyright

Contents

Preface

1 Counting Problems

1.1 Counting Problems and Models of Computation

1.2 Three Classes of Counting Problems

1.3 Reductions

1.4 Further Discussion on Models of Computation

1.5 An Outline of This Book

2 Fibonacci Gates and Holant* Problems

2.1 Fibonacci Gates

2.2 Orthogonal Transformation of Fibonacci Gates

2.3 A Dichotomy Theorem for Holant*(F)

2.4 The Road Ahead

3 Boolean #CSP

3.1 The 0-1 Case and Nonnegative Boolean #CSP

3.2 Affine Functions A and F[sub(1)] U F[sub(2)] U F[sub(3)]

3.3 A Dichotomy for Boolean #CSP

3.4 Tractable Cases

3.5 Hardness

4 Matchgates and Holographic Algorithms

4.1 Pfaffian Orientations and Kasteleyn's Algorithm

4.2 Matchgates

4.3 The Theory of Matchgates

5 2-Spin Systems on Regular Graphs

5.1 3-Regular Graphs

5.2 4-Regular Graphs

6 Holant Problems and #CSP

6.1 A Dichotomy for a Single Ternary Signature

6.2 Reductions Between Holant and #CSP

6.3 Holantc Problems

6.4 A Dichotomy for #CSP[sup(d)]

6.5 Eulerian Orientations and the Tutte Polynomial

6.6 Kirchhoff's Matrix Tree Theorem

7 Holant Dichotomy for Symmetric Constraints

7.1 Vanishing Signatures

7.2 Theorem Statement and Proof of Tractability

7.3 A Sample of Problems

7.4 Outline of Hardness Proof for Theorem 7.19

7.5 Dichotomy for One Signature of Arity 4

7.6 Vanishing Signatures Revisited

7.7 A-transformable and P-transformable Signatures

7.8 Proof of Theorem 7.19

7.9 Decidability of the Dichotomy

8 Planar #CSP for Symmetric Constraints

8.1 Introduction

8.2 Unary Interpolation Revisited

8.3 Planar Pairing

8.4 Domain Pairing

8.5 No-Mixing of Tractable Signatures

8.6 Pinning for Planar Graphs

8.7 Planar #CSP Dichotomy

9 Planar Holant for Symmetric Constraints

9.1 Introduction

9.2 Some Known Results

9.3 A-, P-, and M-transformable Signatures

9.4 Dichotomy for Pl-#CSP[sup(2)]

9.5 Single-Signature Dichotomy

9.6 Mixing P[sub(2)] and M[sub(4)] – Equalities and Matchgates in the Z Basis

9.7 Dichotomy for Planar Holant

10 Dichotomies for Asymmetric Constraints

10.1 Planar #CSP with Asymmetric Constraints

10.2 Holant* Dichotomy

Bibliography

Index

The users who browse this book also browse