Unweighted, Not-all-equal Clauses, 3SAT FLIP (UNAE3SAT)
Input
A Boolean formula $F$ in CNF with three positive literals per clause.
Problem
Find a locally optimal assignment for $F$.
Definitions
An assignment is locally optimal if it has maximum cost among its neighbors. The cost of the assignment is the number of not-all-equals clauses that are satisfied by the assignment; each clause has a weight of one. A truth assignment satisfies a clause $C$ under the not-all-equals criterion if it is such that $C$ has at least one true and one false literal. The neighbors of an assignment $s$ are assignments that can be obtained from $s$ by flipping the value of one variable.
Status
$\P$-hard (Papadimitriou, Schäffer, and Yannakakis [1], Schäffer and Yannakakis [2]).
Remarks
The reduction to show hardness is from NORCVP.
The weighted version of the problem in which each clause is given an integer weight coded in binary is $\mathsf{PLS}$-complete [1][2]. If the weights are encoded in unary, the problem is $\mathsf{FP}$-complete.
References
- C. H. Papadimitriou, A. A. Schäffer, and M. Yannakakis (1990). On the complexity of local search.
- A. A. Sch¨affer and M. Yannakakis (1991). Simple local search problems that are hard to solve.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.5.3.