patternMinor
Is the problem of evaluating a boolean formula on a given assignment P-complete?
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?
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.