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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

An important tool in the study of the complexity of Constraint SatisfactionProblems (CSPs) is the notion of a relational clone, which is the set of allrelations expressible using primitive positive formulas over a particular setof base relations. Post's lattice gives a complete classification of allBoolean relational clones, and this has been used to classify the computationaldifficulty of CSPs. Motivated by a desire to understand the computationalcomplexity of (weighted) counting CSPs, we develop an analogous notion offunctional clones and study the landscape of these clones. One of these clonesis the collection of log-supermodular (lsm) functions, which turns out to playa significant role in classifying counting CSPs. In the conservative case(where all nonnegative unary functions are available), we show that there areno functional clones lying strictly between the clone of lsm functions and thetotal clone (containing all functions). Thus, any counting CSP that contains asingle nontrivial non-lsm function is computationally as hard to approximate asany problem in #P. Furthermore, we show that any non-trivial functional clone(in a sense that will be made precise) contains the binary function "implies".As a consequence, in the conservative case, all non-trivial counting CSPs areas hard as #BIS, the problem of counting independent sets in a bipartite graph.Given the complexity-theoretic results, it is natural to ask whether the"implies" clone is equivalent to the clone of lsm functions. We use the Mobiustransform and the Fourier transform to show that these clones coincideprecisely up to arity 3. It is an intriguing open question whether the lsmclone is finitely generated. Finally, we investigate functional clones in whichonly restricted classes of unary functions are available.

The expressibility of functions on the Boolean domain, with applications to Counting CSPs