HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the problem of evaluating a boolean formula on a given assignment P-complete?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthebooleanassignmentcompleteformulagivenevaluating

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#11697, answer score: 8

Revisions (0)

No revisions yet.