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?
How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples
turing machines;nondeterminism