MAXFLIP Verification (MAXFLIPV)

Input

An encoding $\overline{\alpha}$ of a Boolean circuit constructed of AND, OR, and NOT gates, plus inputs $x = x_1, \ldots, x_n$. The circuit’s $m$ output values $y = y_1, \ldots, y_m$.

Problem

Is the circuit’s output a local maximum among the neighbors of $x$ when $y$ is viewed as a binary number?

Definitions

The neighbors of $x$ are Boolean vectors of length $n$ whose Hamming distance differs from $x$ by one. That is, they can be obtained from $x$ by flipping one bit.

Status

$\P$-complete (Johnson, Papadimitriou, and Yannakakis [1]).

Remarks

The reduction to show hardness is from MCVP. The complementary problem, called the FLIP Verification Problem, in which the output is minimized, is also $\P$-complete [1]. The general problems MAXFLIP and FLIP are $\mathsf{PLS}$-complete [1]. $\mathsf{PLS}$ stands for polynomially local search. We note for most problems that are $\mathsf{PLS}$-complete the problem of verifying local optimality turned out to be $\P$-complete. However, Krentel shows that this is not always the case [2].