- #1
mathmari
Gold Member
MHB
- 5,049
- 7
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...
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...