Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
We analyse the complexity of approximate counting constraint satisfactions problems #CSP(F), where F is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known if F contains arbitrary unary functions. We strengthen this result by fixing any permissive...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2019
|
| _version_ | 1797093855116394496 |
|---|---|
| author | Backens, M Bulatov, A Goldberg, LA McQuillan, C Živný, S |
| author_facet | Backens, M Bulatov, A Goldberg, LA McQuillan, C Živný, S |
| author_sort | Backens, M |
| collection | OXFORD |
| description | We analyse the complexity of approximate counting constraint satisfactions problems #CSP(F), where F is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known if F contains arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and requiring only those to be in F. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. Furthermore, we also consider what happens if only the pinning functions are assumed to be in F. We show that any set of functions for which pinning is not sufficient to recover the two kinds of permissive unaries must either have a very simple range, or must satisfy a certain monotonicity condition. We exhibit a non-trivial example of a set of functions satisfying the monotonicity condition. |
| first_indexed | 2024-03-07T04:06:11Z |
| format | Journal article |
| id | oxford-uuid:c63dffdf-b353-453a-850f-bd635baf2827 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:06:11Z |
| publishDate | 2019 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:c63dffdf-b353-453a-850f-bd635baf28272022-03-27T06:36:47ZBoolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spinJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c63dffdf-b353-453a-850f-bd635baf2827EnglishSymplectic Elements at OxfordElsevier2019Backens, MBulatov, AGoldberg, LAMcQuillan, CŽivný, SWe analyse the complexity of approximate counting constraint satisfactions problems #CSP(F), where F is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known if F contains arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and requiring only those to be in F. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. Furthermore, we also consider what happens if only the pinning functions are assumed to be in F. We show that any set of functions for which pinning is not sufficient to recover the two kinds of permissive unaries must either have a very simple range, or must satisfy a certain monotonicity condition. We exhibit a non-trivial example of a set of functions satisfying the monotonicity condition. |
| spellingShingle | Backens, M Bulatov, A Goldberg, LA McQuillan, C Živný, S Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin |
| title | Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin |
| title_full | Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin |
| title_fullStr | Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin |
| title_full_unstemmed | Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin |
| title_short | Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin |
| title_sort | boolean approximate counting csps with weak conservativity and implications for ferromagnetic two spin |
| work_keys_str_mv | AT backensm booleanapproximatecountingcspswithweakconservativityandimplicationsforferromagnetictwospin AT bulatova booleanapproximatecountingcspswithweakconservativityandimplicationsforferromagnetictwospin AT goldbergla booleanapproximatecountingcspswithweakconservativityandimplicationsforferromagnetictwospin AT mcquillanc booleanapproximatecountingcspswithweakconservativityandimplicationsforferromagnetictwospin AT zivnys booleanapproximatecountingcspswithweakconservativityandimplicationsforferromagnetictwospin |