<p>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$).</p>

<p>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$?</p>

<p>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?</p>

<p>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$)?</p>

<p>My motivation: curiousity.  This was prompted by <a href="https://cstheory.stackexchange.com/q/18627/5038">Complexity of a linear algebra problem</a>.  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.</p>

CC BY-SA 3.0
2013-08-14T21:50:07.350Z
See [CSP](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem) and [Schaefer's dichotomy theorem](http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem)
Kaveh
CC BY-SA 3.0
2013-08-14T21:57:19.590Z
Note that Schaefer's dichotomy theorem is for any set of constraints, including constraints that are not symmetric.
Tyson Williams
<sat><np-complete>
Generalization of SAT, where we replace OR with another symmetric function
D.W.
# Generalization of SAT, where we replace OR with another symmetric function

(Asked by: username_0 on 2013-08-14)

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](https://cstheory.stackexchange.com/q/18627/5038). 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.

**Tags:** sat, np-complete
> **Comments:**
> **username_1**: See [CSP](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem) and [Schaefer's dichotomy theorem](http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem)  
> **username_2**: Note that Schaefer's dichotomy theorem is for any set of constraints, including constraints that are not symmetric.  

---

## 0 answers

