English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Constraint satisfaction problems (or CSPs) have been extensively studied in,for instance, artificial intelligence, database theory, graph theory, andstatistical physics. From a practical viewpoint, it is beneficial toapproximately solve those CSPs. When one tries to approximate the total numberof truth assignments that satisfy all Boolean-valued constraints for(unweighted) Boolean CSPs, there is a known trichotomy theorem by which allsuch counting problems are neatly classified into exactly three categoriesunder polynomial-time (randomized) approximation-preserving reductions. Incontrast, we obtain a dichotomy theorem of approximate counting forcomplex-weighted Boolean CSPs, provided that all complex-valued unaryconstraints are freely available to use. It is the expressive power of freeunary constraints that enables us to prove such a stronger, completeclassification theorem. This discovery makes a step forward in the quest forthe approximation-complexity classification of all counting CSPs. To deal withcomplex weights, we employ proof techniques of factorization and arityreduction along the line of solving Holant problems. Moreover, we introduce anovel notion of T-constructibility that naturally inducesapproximation-preserving reducibility. Our result also gives an approximationanalogue of the dichotomy theorem on the complexity of exact counting forcomplex-weighted Boolean CSPs.

Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems