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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The promise constraint satisfaction problem (PCSP) is a recently introducedvast generalisation of the constraint satisfaction problem (CSP) that capturesapproximability of satisfiable instances. A PCSP instance comes with two formsof each constraint: a strict one and a weak one. Given the promise that asolution exists using the strict constraints, the task is to find a solutionusing the weak constraints. While there are by now several dichotomy resultsfor fragments of PCSPs, they all consider (in some way) symmetric PCSPs.  1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric(non-promise) CSPs. While both problems are NP-hard, Brakensiek and Guruswamishowed [SICOMP'21] that given a satisfiable instance of 1-in-3-SAT one can finda solution to the corresponding instance of (weaker) Not-All-Equal-3-SAT. Inother words, the PCSP template (1-in-3,NAE) is tractable.  We focus on non-symmetric PCSPs. In particular, we study PCSP templatesobtained from the Boolean template (t-in-k,NAE) by either adding tuples tot-in-k or removing tuples from NAE. For the former, we classify all templatesas either tractable or not solvable by the currently strongest known algorithmfor PCSPs, the combined basic LP and affine IP relaxation of Brakensiek,Guruswami, Wrochna, and \v{Z}ivn\'y [SICOMP'20]. For the latter, we classifyall templates as either tractable or NP-hard.

Beyond PCSP (1-in-3,NAE)