Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input?

In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is 1.

For example, evaluation (when also given an input to the boolean formula or circuit, evaluate the output) is easy (in P) in both cases.

On the other hand, guessing the input (when given an output of the formula or circuit) is NP-hard in both cases. For example, 3-SAT is such a problem on formulas that's NP hard.

Do we have examples, preferably "non-contrived", that are easy (in P) on boolean formulas but NP hard on boolean circuits?

Since treewidth is NP hard to compute on general graphs and 1 on trees (/formulas), this might be an example, but I find this "contrived" as now we're treating the input as a graph instead of inherently as something that can compute something: we're basically ignoring the difference in AND and OR gates. In the same way graph problems that are polynomially computable for trees and NP hard for general graphs might be such "contrived" examples.

  • $\begingroup$ Buss showed that formula evaluation is $\mathsf{NC^1}$-complete, see for example this paper. In contrast, circuit evaluation is P-complete. $\endgroup$ Apr 25 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.