-1
$\begingroup$

I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization.

If instead we are given a partial truth table, and we just want to determine the minimal terms that fill in the missing values in the truth table, is this still NP-hard?

For example, the onset and missing value with three variables:

A B C X
0 0 0 1
0 0 1 1
0 1 0 1
1 0 0 ?
1 1 1 1

Is it still NP-hard to find the minimal term consistent with the onset that fills in the ? value?

I suspect it is still NP-hard, because if it were not NP-Hard to find the minimal term for one missing value, and we could find the minimal term in polynomial time with the number of items in the onset, then we could apply this algorithm to each item in the onset in polynomial time, and then combine all the terms to get the minimal expression, also in polynomial time.

I basically want to double check the above reasoning and make sure I did not miss anything.

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ For those of us with a general understanding of logic minimization, but not familiar with the specific definitions and terms you have in mind, could you clarify your terminology? E.g. what is "the onset", what is the input for "the logic minimization problem"? What is the output supposed to be? What is a "minimal term"? $\endgroup$
    – Neal Young
    Sep 21, 2021 at 1:39
  • $\begingroup$ Sorry, I was trying to use what I thought was the standard terminology. "onset" means the variable assignments that result in a true/1 value, which is the reciprocal of the "offset" which are assignments that result in false/0. The input is the variable assignments that result in true/1 values, along with assignments that have unknown values, such as in my example. The output to a logic minimization problem is a disjunctive normal form logic formula with the minimal number of literals necessary to generate the initial input. Let me know if there is a better way I can clarify the question. $\endgroup$
    – yters
    Sep 21, 2021 at 2:26
  • $\begingroup$ In your input, do the assignments that are not specified have to be "offsets"? So the offsets are implicitly defined in that way? And in your comment, regarding the output, what do you mean by a "minimal number of literals"? Isn't a literal just a variable or its negation, in which case most correct formulas will contain all possible literals? $\endgroup$
    – Neal Young
    Sep 21, 2021 at 15:16
  • 2
    $\begingroup$ Please don't add clarifications in the comments. Instead, edit the question so it is self-contained and contains all needed background, context, and definitions for someone here to understand it. $\endgroup$
    – D.W.
    Sep 21, 2021 at 20:06
  • 1
    $\begingroup$ Great, thank you. You posted that you suspect it is NP-hard and listed some reasons for your suspicion. One way to show you're seriously thinking about the problem would be to try to turn those suspicions into a proof of NP-hardness and either show the proof you've got or identify the gap or difficulty you have in proving it. For instance, you say you suspect "we could apply this algorithm ..."; a good step for you would be to write out the details and see if you can prove whether that works. $\endgroup$
    – D.W.
    Sep 21, 2021 at 21:23

1 Answer 1

Reset to default
4
$\begingroup$

Theorem 1. The problem in the post is NP-complete.

Proof. MIN DNF is the following special case of the problem in the post:

Given a truth table $T$ and integer $k$, is there a DNF of size at most $k$ whose truth table is $T$?

MIN DNF is known to be NP-complete (see [1] and works cited by it). Since the problem in the post generalizes MIN DNF, the problem in the post is also NP-hard.

To see that it is also NP-complete, observe that it is in NP because, given a DNF, one can verify that the DNF is consistent with the input by checking that (i) for every clause in the DNF, the number of assignments satisfying the clause is at most the number of rows in the given partial table, and each such assignment is one of those rows, and (ii) each row with value 1 is covered in this way by some clause in the DNF. $~~~\Box$

[1] Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., & Saks, M. (2008). Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table. SIAM Journal on Computing, 38(1), 63-84. https://doi.org/10.1137/060664537

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.