6
$\begingroup$

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}$ that maps a vector of $n$ boolean values to the truth value of this predicate on those inputs.

Now I have a truth table of pairs $(x_1,y_1), \dots, (x_m,y_m)$, and I want to find a predicate $P$ that is consistent with these pairs and that is as "simple" as possible. In particular, I have two variants of the problem:

Problem 1. Given $(x_1,y_1), \dots, (x_m,y_m)$, find a predicate $P$ such that (1) it agrees with the entire truth table (i.e., for all $i$, $f_P(x_i)=y_i$), and (2) out of all such predicates, the complexity of $P$ is minimized.

Problem 2. Given $(x_1,y_1), \dots, (x_m,y_m)$ and a threshold $t$, find a predicate $P$ such that (1) $P$ agrees with at least a $t/m$ fraction of the truth table (i.e., there are at least $t$ values of $i$ such that $f_P(x_i)=y_i$), and (2) out of all such predicates, the complexity of $P$ is minimized.

Are there any algorithms for solving either of these problems, in a way that is more efficient than enumerating all predicates?

Of course, to make the problem well-posed, we must agree on a definition of the complexity of a predicate. Here I can see any number of realistic complexity metrics. One metric might be that, when we express $P$ as a formula in boolean logic, the length of that formula. Another might be the number of operators in that formula, or the nesting depth of the formula. I am interested in any and all algorithms for any plausible notion of complexity.

This can be viewed as a kind of learning problem, where Occam's razor suggests that low-complexity predicates are a priori more likely than high-complexity predicates.

$\endgroup$
  • 2
    $\begingroup$ Gut feeling: Both problems (their decision variants, to be precise) are NP-complete. Trivial observation: If 1. is NP-complete, 2. is as well, since it is a generalisation of 1. $\endgroup$ – FrankW Feb 28 '14 at 5:50
  • $\begingroup$ Agreed, @FrankW. Both problems feel NP-hard to me too. Nonetheless, I'm curious about pragmatic approaches that might sometimes work well in practice (e.g., in the same way that SAT solvers are often useful even though SAT is NP-complete). Approximation algorithms would be OK too. $\endgroup$ – D.W. Feb 28 '14 at 6:52
  • $\begingroup$ Have a look at Karnaugh Maps; they are used in electronics to optimize logical circuits. The idea to match just a fraction of the target function is absolutely new to me, though. I'm curious what it might be good for, so if you describe your usecase I'd be interested :) Anyway, I'm not sure that the Karnaugh Maps can be adjusted to fit this idea, but it might be possible. $\endgroup$ – Alfe Feb 28 '14 at 9:26
  • $\begingroup$ I assume you want all other truth assignments to not satisfy the formula? Otherwise, tautologies present simple answers. $\endgroup$ – Raphael Jun 19 '15 at 9:13
  • $\begingroup$ @Raphael, actually, no: I don't care what happens to other values. Not seeing what you mean about tautologies. Making $P$ a tautology would only be an answer to Problem 1 if all of the $y_i$'s were true. What am I missing? $\endgroup$ – D.W. Jun 19 '15 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.