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

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the complexity of SAT($\Gamma$) problems for potentially infinitelanguages $\Gamma$ closed under variable negation (sign-symmetric languages).Via an algebraic connection, this reduces to the study of restricted partialpolymorphisms of $\Gamma$ we refer to as \emph{pSDI-operations} (for partial,self-dual and idempotent). First, we study the language classes themselves. Weclassify the structure of the least restrictive pSDI-operations, correspondingto the most powerful languages $\Gamma$, and find that these operations can bedivided into \emph{levels}, corresponding to a rough notion of difficulty; andthat within each level there is a strongest operation (the partial $k$-NUoperation, preserving $(k-1)$-SAT) and a weakest operation (the $k$-universaloperation $u_k$, preserving problems definable via bounded-degree polynomials).We show that every sign-symmetric $\Gamma$ not preserved by $u_k$ implementsall $k$-clauses; thus if $\Gamma$ is not preserved by $u_k$ for any $k$, thenSAT($\Gamma$) is trivially SETH-hard and cannot be solved faster than$O^*(2^n)$ unless SETH fails.  Second, we study upper and lower bounds for SAT($\Gamma$) for such languages.We show that several classes in the hierarchy correspond to problems which canbe solved faster than $2^n$ using previously known algorithmic strategies suchas Subset Sum-style meet-in-the-middle and fast matrix multiplication.Furthermore, if the sunflower conjecture holds for sunflowers with k sets, thenthe partial k-NU language has an improved algorithm via local search.Complementing this, we show that for every class there is a concrete lowerbound $c$ such that SAT($\Gamma$) cannot be solved faster than $O^*(c^n)$ forall problems in the class unless SETH fails. This gives the first known case ofa SAT-problem which simultaneously has non-trivial upper and lower bounds underSETH.

Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?