<p><strong>Theorem 1.</strong> <em>The problem in the post is NP-complete.</em></p>
<p><em>Proof.</em>
MIN DNF is the following special case of the problem in the post:</p>
<blockquote>
<p><em>Given a truth table <span class="math-container">$T$</span> and integer <span class="math-container">$k$</span>, is there a DNF of size at most <span class="math-container">$k$</span> whose truth table is <span class="math-container">$T$</span>?</em></p>
</blockquote>
<p>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.</p>
<p>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. <span class="math-container">$~~~\Box$</span></p>
<p>[1] Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., &amp; Saks, M. (2008). Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table. SIAM Journal on Computing, 38(1), 63-84.  <a href="https://doi.org/10.1137/060664537" rel="nofollow noreferrer">https://doi.org/10.1137/060664537</a></p>

CC BY-SA 4.0
2021-09-22T16:15:06.963Z
2021-09-22T16:15:06.963Z
Neal Young
<p>I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization.</p>
<p>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?</p>
<p>For example, the onset and missing value with three variables:</p>
<pre><code>A B C X
0 0 0 1
0 0 1 1
0 1 0 1
1 0 0 ?
1 1 1 1
</code></pre>
<p>Is it still NP-hard to find the minimal term consistent with the onset that fills in the <code>?</code> value?</p>
<p>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.</p>
<p>I basically want to double check the above reasoning and make sure I did not miss anything.</p>

CC BY-SA 4.0
2021-09-21T01:39:13.030Z
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"?
Neal Young
CC BY-SA 4.0
2021-09-21T02:26:20.117Z
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.
yters
CC BY-SA 4.0
2021-09-21T15:16:50.037Z
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?
Neal Young
CC BY-SA 4.0
2021-09-21T15:49:34.170Z
@NealYoung yes, unlisted assignments are all offsets, i.e. false/0.  Assignments that have a ? can either be true or false.  Minimal number of literals means counting all the instances of literals in the formula, meaning some variables will be counted twice.  For example, in the formula (A AND B) OR (A AND C) there are four literals and the variable A is counted twice.  In the example in my question, one valid solutions is (NOT A AND NOT B AND NOT C) OR (NOT A AND NOT B AND C) OR (NOT A AND B AND NOT C) OR  (A AND B AND C), and this solution would set the ? entry value to false/0.
yters
CC BY-SA 4.0
2021-09-21T15:51:03.660Z
However, that long solution is probably not the smallest solution.  Logic minimization attempts to find the shortest formula that can reproduce the onset table.  The common approaches for doing this are Karnaugh maps, the Quine McCluskey algorithm and the Espresso algorithm.
yters
CC BY-SA 4.0
2021-09-21T16:02:48.787Z
And without if don't-cares (?) are not allowed, Set Cover reduces to the problem?  Do you have a reference (or proof sketch) for that?  And the problem is NP-hard even without don't-cares, surely it is NP-hard when you allow don't-cares?
Neal Young
CC BY-SA 4.0
2021-09-21T16:44:59.047Z
The standard optimal algorithm, Quine McCluskey, proceeds in two stages, where first all the implicants are found by repeatedly using the identity (X AND Y) OR X = X.  Each implicant covers a portion of the onset, and so in the second stage we try to find the minimal set of implicants that covers the entire onset, which straightforwardly maps to the set cover problem.  And yes, both with don't cares and without the problem remains NP-hard.  My question is if we are just trying to solve for a single don't care, is the problem still NP-hard, and I think it is based on the argument I propose.
yters
CC BY-SA 4.0
2021-09-21T19:06:59.500Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/129861/discussion-between-neal-young-and-yters).
Neal Young
CC BY-SA 4.0
2021-09-21T20:06:23.713Z
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.
D.W.
CC BY-SA 4.0
2021-09-21T20:10:37.613Z
See our [help/on-topic], especially: "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others.  [...] Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, [...]"
D.W.
CC BY-SA 4.0
2021-09-21T20:25:40.213Z
@D.W. I'll improve the question itself with the comments.  Does the question appear to be not one I am seriously thinking about?  If so, what can I add that would indicate I am seriously thinking about the question?
yters
CC BY-SA 4.0
2021-09-21T21:23:20.720Z
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.
D.W.
CC BY-SA 4.0
2021-09-21T21:29:12.017Z
Will do, and also based on discussion with Neal Young I need to back up a step anyways, since it is the standard algorithm that requires solving an NP-hard problem, the problem is not necessarily NP-hard itself.
yters
<cc.complexity-theory><np-hardness><circuit-complexity><minimization>
Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?
yters
# Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

(Asked by: username_0 on 2021-09-21)

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.

**Tags:** cc.complexity-theory, np-hardness, circuit-complexity, minimization
> **Comments:**
> **username_1**: 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"?  
> **username_0**: 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.  
> **username_1**: 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?  
> **username_0**: @NealYoung yes, unlisted assignments are all offsets, i.e. false/0.  Assignments that have a ? can either be true or false.  Minimal number of literals means counting all the instances of literals in the formula, meaning some variables will be counted twice.  For example, in the formula (A AND B) OR (A AND C) there are four literals and the variable A is counted twice.  In the example in my question, one valid solutions is (NOT A AND NOT B AND NOT C) OR (NOT A AND NOT B AND C) OR (NOT A AND B AND NOT C) OR  (A AND B AND C), and this solution would set the ? entry value to false/0.  
> **username_0**: However, that long solution is probably not the smallest solution.  Logic minimization attempts to find the shortest formula that can reproduce the onset table.  The common approaches for doing this are Karnaugh maps, the Quine McCluskey algorithm and the Espresso algorithm.  
> **username_1**: And without if don't-cares (?) are not allowed, Set Cover reduces to the problem?  Do you have a reference (or proof sketch) for that?  And the problem is NP-hard even without don't-cares, surely it is NP-hard when you allow don't-cares?  
> **username_0**: The standard optimal algorithm, Quine McCluskey, proceeds in two stages, where first all the implicants are found by repeatedly using the identity (X AND Y) OR X = X.  Each implicant covers a portion of the onset, and so in the second stage we try to find the minimal set of implicants that covers the entire onset, which straightforwardly maps to the set cover problem.  And yes, both with don't cares and without the problem remains NP-hard.  My question is if we are just trying to solve for a single don't care, is the problem still NP-hard, and I think it is based on the argument I propose.  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/129861/discussion-between-neal-young-and-yters).  
> **username_2**: 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.  
> **username_2**: See our [help/on-topic], especially: "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others.  [...] Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, [...]"  
> **username_0**: @D.W. I'll improve the question itself with the comments.  Does the question appear to be not one I am seriously thinking about?  If so, what can I add that would indicate I am seriously thinking about the question?  
> **username_2**: 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.  
> **username_0**: Will do, and also based on discussion with Neal Young I need to back up a step anyways, since it is the standard algorithm that requires solving an NP-hard problem, the problem is not necessarily NP-hard itself.  

---

## 1 answers

### Answer by username_1 on 2021-09-22. Score: 4 | Accepted answer

**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>


---

