MHB Is the Complexity of Satisfiable Boolean Expressions in NP?

[mathmari]

Hey!

The Boolean expression $(p_1+p_2)*p_3$ can be represented by the string $(1+2)3$, where integer $i$ represents variable $p_i$.

Consider the language $L$ consisting of all strings representing satisiable Boolean expressions (those for which some assignment of $0$'s and $1$;1 to the variables gives the expression the value 1).

We claim that $L$ is in $\mathcal{NP}$.

A nondeterministic algorithm to accept $L$ begins by "guessing" a satisfying assignment of $0$'s and $1$'s to the propositional variables in an input string, if such an assignment exists.
Then, the value ($0$ or $1$) of each variable is substituted for the variable wherever it occurs in the input string.
Some shifting of the string will be needed to close up gaps when the single symbol $0$ or $1$ is substituted for a decimal representationm of a propositional variable.
Then the resulting expression is evaluated to verify that it has the value $1$.
The evaluation can be done in time proportional to its length by a number of parsing algorithms.
Even without using an efficient parsing algorithm, the reader should have a little trouble evaluating a proposition in $O(n^2)$ steps.
Hence there is a nondeterministic Turing machine of polynomial time complexity to accept satisfiable Boolean expressions, and thus the problem of determining whether a Boolean expression is satisfiable is in $\mathcal{NP}$.Could you explain me how we have shown that there is a nondeterministic Turing machine of polynomial time complexity to accept satisfiable Boolean expressions?? (Wondering)

I haven't understood it...

 

[Evgeny.Makarov]

The details are a bit messy, but the idea is the following.

(1) Nondeterministically choose a sequence of $n$ zeros and ones where $n$ is the number of variables in the expression.

(2) Substitute chosen values for variables. The result is an expression containing 0, 1 and operations.

(3) Evaluate the resulting expression.

(4) Accept if the result is 1.

With some handwaving one can show that this requires polynomial time. I recommend understanding this first if you write this algorithm using not a Turing machine, but your favorite programming languages with all data structures (such as trees) and standard functions available.