<p>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?</p>

CC BY-SA 3.0
2013-10-13T01:45:28.100Z
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?
c.lorenz
CC BY-SA 3.0
2013-10-13T02:09:24.103Z
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.
Kaveh
CC BY-SA 3.0
2013-10-13T02:10:36.733Z
Please see [about] and [help/on-topic]. This question seems more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2013-10-13T02:24:07.097Z
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$.
Austin Buchanan
CC BY-SA 3.0
2013-10-13T13:45:18.270Z
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.
user375334
CC BY-SA 3.0
2013-10-13T16:46:34.187Z
@user375334 with luck
Austin Buchanan
<turing-machines><nondeterminism>
How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples
user375334
# How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples

(Asked by: username_0 on 2013-10-13)

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?

**Tags:** turing-machines, nondeterminism
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_2**: Please see [about] and [help/on-topic]. This question seems more suitable for [cs.se].  
> **username_3**: 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$.  
> **username_0**: 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.  
> **username_3**: @user375334 with luck  

---

## 0 answers

