Computational and approximation complexities of MINNAESAT variants
Sangram K. Jena, K. Subramani · Discrete Mathematics Algorithms and Applications · 2025
In this paper, we explore the computational and approximation complexities of selected variants of the MINNAESAT problem. The MINNAESAT problem is an optimization variant of the NAESAT problem. NAESAT is a classical NP-complete problem and is one of the earliest variants of the satisfiability problem. In the NAESAT problem, we are given a Boolean formula [Formula: see text] in CNF, with each clause containing at least two literals. The goal is to find an assignment for [Formula: see text], such that (a) every clause is satisfied, and (b) at least one literal in each clause is set to false. Such an assignment is called a not-all-equal (NAE)-satisfying assignment. The objective of the MINNAESAT problem is to find an assignment for [Formula: see text], which minimizes the number of NAE-satisfied clauses. This paper focuses on two types of variants of MINNAESAT, viz, width limiting and repetition limiting. Our research into MINNAESAT variants parallels existing research for MINSAT variants. We first consider a MINNAESAT variant with restricted clause width and prove that the satisfiability problem in this variant is NP-complete. We also establish that the optimization version of this variant is APX-complete. We then show that the MINNAESAT problem is NP-complete, even when the repetition factor of each variable is bounded by three. For this variant, we design a constant factor approximation algorithm. Finally, we detail an inapproximability bound for the MINNAESAT variant with restricted clause width.