Let $\sigma(y_1,\dots,y_k)$ denote some boolean symmetric function on $k$ boolean inputs, $\sigma:\{0,1\}^k\to\{0,1\}$. In $k$-SAT, an instance is a conjunction of clauses, where each clause is the logical-or of $k$ literals. Consider replacing logical-or with $\sigma$, so that each clause contains $\sigma$ applies to $k$ literals. In other words, $\varphi=\land_i \sigma(\ell_{i,1},\dots,\ell_{i,k})$ and each $\ell_{i,j}$ is a literal (some $x_i$ or $\neg x_i$).

For which functions $\sigma$ is this NP-complete, and for which functions is this solvable in polynomial time? Can we classify the hardness of this problem for each possible value of $\sigma$?

Of course for $\sigma(y_1,\dots,y_k)=y_1\lor \dots \lor y_k$, we know this is hard: it is exactly $k$-SAT. What about other functions $\sigma$? For which $\sigma$ is it hard? If it helps, we can characterize the function $\sigma$ by a set $S\subseteq\{0,1,2,\dots,k\}$, where $\sigma(y_1,\dots,y_k)$ is 1 if and only if $y_1+\dots+y_k\in S$; so we can ask, for which $S$ is this hard?

The variant that's probably more interesting to me: for which $\sigma$ is this hard, if we restrict all variables to appear in positive form (there are no negations in any of the literals)? I recently learned that NAE-3SAT remains hard even with this positivity restriction, so for $S=\{1,2\}$ (i.e., $\sigma(y_1,\dots,y_k)=(\neg y_1 \land \dots \land \neg y_k)\lor (y_1\land \dots \land y_k)$) the problem is hard. What about other choices of $\sigma$ (i.e., of $S$)?

My motivation: curiousity. This was prompted by Complexity of a linear algebra problem. There's some relationship to some variant of that problem, which arises if for some $k$, $f(x)=1$ for $x\in S$ and $f(x)=-1$ for $x\in\{0,1,2,\dots,k\}\setminus S$. But mostly, I'm just curious.

  • 8
    $\begingroup$ See CSP and Schaefer's dichotomy theorem $\endgroup$ – Kaveh Aug 14 '13 at 21:50
  • $\begingroup$ Note that Schaefer's dichotomy theorem is for any set of constraints, including constraints that are not symmetric. $\endgroup$ – Tyson Williams Aug 14 '13 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.