We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of polynomials over the field of two elements each of which is a product of affine forms.
We focus on the case of $k$-CNF formulas (the $k$-SUB-SAT problem). Clearly, $k$-SUB-SAT is no easier than $k$-SAT, and might be harder. Indeed, via simple reductions we show that 2-SUB-SAT is NP-hard, and W[1]-hard when parameterized by the co-dimension of the subspace. We also prove that the optimization version Max-2-SUB-SAT is NP-hard to approximate better than the trivial $3/4$ ratio even on satisfiable instances.
On the algorithmic front, we investigate fast exponential algorithms which give non-trivial savings over brute-force algorithms. We give a simple branching algorithm with runtime $(1.5)^r$ for 2-SUB-SAT, where $r$ is the subspace dimension, as well as a $(1.4312)^n$ time algorithm where $n$ is the number of variables.
Turning to $k$-SUB-SAT for $k \ge 3$, while known algorithms for solving a system of degree $k$ polynomial equations already imply a solution with runtime $\approx 2^{r(1-1/2k)}$, we explore a more combinatorial approach. Based on an analysis of critical variables (a key notion underlying the randomized $k$-SAT algorithm of Paturi, Pudlak, and Zane), we give an algorithm with runtime $\approx {n\choose {\le t}} 2^{n-n/k}$ where $n$ is the number of variables and $t$ is the co-dimension of the subspace. This improves upon the runtime of the polynomial equations approach for small co-dimension. Our combinatorial approach also achieves polynomial space in contrast to the algebraic approach that uses exponential space. We also give a PPZ-style algorithm for $k$-SUB-SAT with runtime $\approx 2^{n-n/2k}$. This algorithm is in fact oblivious to the structure of the subspace, and extends when the subspace-membership constraint is replaced by any constraint for which partial satisfying assignments can be efficiently completed to a full satisfying assignment. Finally, for systems of $O(n)$ polynomial equations in $n$ variables over the field of two elements, we give a fast exponential algorithm when each polynomial has bounded degree irreducible factors (but can otherwise have large degree) using a degree reduction trick.
