[Solved]: Is the problem of evaluating a boolean formula on a given assignment P-complete?

Problem Detail: 

I know that the CIRCUIT VALUE problem is P-complete. In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given circuit on the given input.

I wish to know if the problem of evaluating a Boolean formula on a given assignment is also P-complete. From one hand, it seems that a Boolean circuit and a Boolean formula are very similar objects. Also, the proof of that CIRCUIT VALUE is P-complete results from the Cook-Levin problem, the same theorem that actually shows that SAT is NP-Complete, so I don't see a reason why this problem won't be P-Complete. From the other hand, it seems pretty easy to evaluate a Boolean formula in logarithmic space, so if this problem is indeed P-complete I think it would imply L = P which is unknown.

So I think I'm missing something.. any ideas people?

Asked By : John Smith

Answered By : vzn

this is apparently the same as the "boolean formula value problem" similar to the "boolean sentence value problem" (BSVP) proven to be in ALOGTIME by Buss-Cook-Gupta-Ramachandran. an improved algorithm and refs are given in Algorithms for Boolean Formula Evaluation and for Tree Contraction by Buss.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11697