Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-112 | 30th July 2021 05:10

#### CNF Satisfiability in a Subspace and Related Problems

TR21-112
Authors: Vikraman Arvind, Venkatesan Guruswami
Publication: 30th July 2021 05:11
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint