Describe a polynomial-time algorithm to compute the function expressed by the boolean formula

Question

Let $\varphi$ be a boolean formula of $n$ variables and $(t_1, t_2,\ldots,t_n) \in \{0, 1\}$ be an assignment.

How to describe a polynomial-time algorithm to compute $\varphi(t_1,t_2,\dots, t_n)$?

Answer 1

There is a simple linear time algorithm to do this, provided you already have the assignment. First let's assume you have just a single clause, say $(x_1 \lor \overline{x_2} \lor x_3)$. Starting at the left, first substitute $t_1$ from the assignment for $x_1$, giving $(t_1 \lor \overline{x_2} \lor x_3)$. Now, substitute the next literal, giving $(t_1 \lor \overline{t_2} \lor x_3)$. Now that there are two literals with known values, you can simplify $t_1 \lor \overline{t_2}$ to a single value T or F by just looking up their values, so you are left with $(T \lor x_3)$ or $(F \lor x_3)$. Then just continue this process from left to right. If the clause consists of ORs you can stop as soon as you have a single T, and if it instead consists of ANDs stop as soon as you have a single F.

This approach will work just as well for multiple clauses. If the formula has nested clauses, then when you come across a nested clause in your left to right pass, just pause what you are doing and compute the value of the inner clause first, then continue on.