Traditionally, the boolean satisfiability problem is framed as, given a boolean formula, is there an assignment that satisfies the formula. I'm trying to look at this differently - from the perspective of a Non-Deterministic Turing machine that, given a set of examples, will returns a formula that satisfies all of them. I'm familiar with non-determinism to seek out a single solution, but in this case, there is another dimension - specifically not whether there is any expression in the Universe of expressions that will satisfy each example, but instead what is the 1 expression that is satisfied by all the example assignments. Does anyone have a recommendation on how picture this?

  • $\begingroup$ To check that I understood the question: given the assignments $(x_1, x_2, x_3) \in \{ (1, 0, 1), (1, 1, 0) \}$, one solution would be "$x_1 \land (x_2 \lor \lnot x_3) \land (\lnot x_2 \lor x_3)$" while the formula "$(x_2 \lor \lnot x_3) \land (\lnot x_2 \lor x_3)$" is not a solution? $\endgroup$ – c.lorenz Oct 13 '13 at 1:45
  • 1
    $\begingroup$ I am not sure what is the relations of nondeterminism to the question. You should first define the problem you want to solve. It seems that your problem is: given a list of assignments, find a formula that is satisfied by all of them. The obvious answer is $\top$: it is satisfied by all assignments. If you want to find a formula that only satisfies those assignments then take the canonical CNF. $\endgroup$ – Kaveh Oct 13 '13 at 2:09
  • $\begingroup$ Please see tour and help center. This question seems more suitable for Computer Science. $\endgroup$ – Kaveh Oct 13 '13 at 2:10
  • 1
    $\begingroup$ This sounds like an inverse problem. Like @Kaveh mentions this problem has trivial answers. Perhaps there is a way to modify the problem to make it interesting. For example, given satisfying assignments $I$ and unsatisfying assignments $J$, find a smallest boolean formula $\Phi$ such that $\Phi (i) = 1~\forall i \in I$ and $\Phi (j) = 0,~\forall j \in J$. $\endgroup$ – Austin Buchanan Oct 13 '13 at 2:24
  • $\begingroup$ Austin, you are correct and that was a part I was missing from the problem. Some of the examples return T and some return F. Given that there is a target Boolean expression that is consistent with all the examples and there outcome, how could a non-deterministic Turing machine find such an expression. $\endgroup$ – user375334 Oct 13 '13 at 13:45

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.