 The Boolean Formula Value Problem (or Boolean Formula Evaluation Problem) is the special case of the problem when the circuit is a tree.The Boolean Formula Value Problem is complete for NC.The problem is closely related to the Boolean Satisfiability Problem which is complete for NP and its complement, the Propositional Tautology Problem, which is complete for co-NP.