Call a DNF formula $\varphi = \bigvee_{i=1}^n C_i$ unambiguous if for every $i\neq j$, $C_i \land C_j$ is unsatisfiable. In other words, the disjunct $C_i$ contains some literal $l$ and $C_j$ contains the negation of $l$.

Consider the following problem.

INPUT: An unambiguous DNF formula over variables $\overline{X} = X_1,\ldots,X_n$, and natural numbers $\overline{w} = w_1,\ldots,w_n$ given in binary.

OUTPUT: The maximum weight of an assignment $\tau: \overline{X} \to \{0,1\}$ that does not satisfy $\varphi$, where the weight of $\tau$ is defined by $\mathrm{weight}_{\overline{w}}(\tau) = \sum_{i=1}^n w_i \tau(x_i)$. Let us write this quantity $\max_{\tau \not\models \varphi} \mathrm{weight}_{\overline{w}}(\tau)$. (With the convention that the max over an empty set is $-\infty$, in case $\varphi$ is a tautology.)

If you prefer, you can make this a decision problem by adding an integer $t$ as part of the input and asking whether $\max_{\tau \not\models \varphi} \mathrm{weight}_{\overline{w}}(\tau)$ is bigger than $t$.

Question: What is the complexity of this problem? I am hoping that it is hard; ideally I would like a proof of NP-hardness, but at this point I would also be happy with weaker evidence such as assuming SETH, or even NSETH [a].

Some observations:

  • The (decision version) is in NP: simply guess a valuation $\tau$ and check that it is not satisfying and that its weight is bigger than $t$.
  • The problem is NP-complete if you remove the restriction that DNF formulas be unambiguous (trivial reduction from DNF falsifiability).
  • If instead of $\max_{\tau \not\models \varphi} \mathrm{weight}_{\overline{w}}(\tau)$ you want to compute $\max_{\tau \models \varphi} \mathrm{weight}_{\overline{w}}(\tau)$ (i.e., the max is over the satisfying assignments), then the problem is PTIME, even over arbitrary DNFs. Indeed you can simply compute the max for each disjunct, and then take the max of these.
  • If the weights in $\overline{w}$ are given in unary then the problem is PTIME, i.e., the problem is in pseudo polynomial time. Indeed, for every value $A$ between $0$ and $\sum_i w_i$, we can compute in PTIME by dynamic programming the number of satisfying assignments of weight $A$, hence deduce if there is a non-satisfying assignment having weight $A$.

Note that this is a simpler version of this previous question about the same problem but for unambiguous finite automata instead of DNF formulas, in the sense that there is a PTIME reduction from the problem of the current post to the one about automata.

[a] Carmosino, Marco L.; Gao, Jiawei; Impagliazzo, Russell; Mihajlin, Ivan; Paturi, Ramamohan; Schneider, Stefan, Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility, Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS’16, Cambridge, MA, USA, January 14–16, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4057-1). 261-270 (2016). ZBL1334.68079.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.