5
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

In his 1987 paper "The Boolean formula value problem is in ALOGTIME", Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ so does it mean that Boolean formula evaluation is not P-complete? $\endgroup$
    – John Smith
    Commented May 1, 2013 at 17:23
  • 3
    $\begingroup$ We don't know that for sure, but that's probably correct. $\endgroup$
    – Yuval Filmus
    Commented May 1, 2013 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.