CNF Satisfiability in a Subspace and Related Problems
V. Arvind, Venkatesan Guruswami · Algorithmica · 2022
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 $${\mathbb {F}}_2$$ each of which is a product of affine forms. We focus on the case of k-CNF formulas (the $${k}-\textsc {Sub}-\textsc {Sat}$$ problem). Clearly, $${k}-\textsc {Sub}-\textsc {Sat}$$ is no easier than k-SAT, and might be harder. Indeed, via simple reductions we show that $${2}-\textsc {Sub}-\textsc {Sat}$$ is NP-hard, and $${\small \mathrm {W}}[1]$$ -hard when parameterized by the co-dimension of the subspace. We also prove that the optimization version Max- $${2}-\textsc {Sub}-\textsc {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 running time $$O^*(1.5)^r$$ for $${2}-\textsc {Sub}-\textsc {Sat}$$ , where r is the subspace dimension, as well as an $$O^*(1.4312)^n$$ time algorithm where n is the number of variables. Turning to $${k}-\textsc {Sub}-\textsc {Sat}$$ for $$k \geqslant 3$$ , while known algorithms for solving a system of degree k polynomial equations already imply a solution with running time $$\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 running time $$\approx {n\atopwithdelims (){\leqslant 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 running time 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}-\textsc {Sub}-\textsc {Sat}$$ with running time $$\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 $${\mathbb {F}}_2$$ , 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.