Unweighted Two Satisfiability FLIP (U2SATFLIP)
Input
A Boolean formula $F$ in CNF with two 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 clauses that are satisfied by the assignment; each clause has a weight of one. 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 UMCS. The weighted version of the problem in which each edge is given an integer weight encoded in binary is $\mathsf{PLS}$-complete [1][2]. If the edge 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.5.