Is MIN or MAX-True-2-XOR-SAT NP-hard?
-
30-10-2019 - |
Pergunta
Is there a proof or reference that $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$?
Let:
$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,\\ \forall_{C_i} \left.C_i=(p \oplus q)\right|_{\left(p\in \mathbf x \vee\neg p\in\mathbf x\right),\left(q\in \mathbf x \vee\neg q\in\mathbf x\right)} $$
The $\text{2-XOR-SAT}$ problem is to find a satisfying assignment of $\mathbf x$ that would make $\Phi\left(\mathbf x\right)=T$. This is in $P$, as it can be encoded in a set of linear equations mod $2$.
The $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ problems are to maximize or minimize the number of true values in $\mathbf x$, respectively, subject to the constraint that $\Phi\left(\mathbf x\right)=T$.
Nenhuma solução correta