Why is Boolean complexity theory difficult! (English) Zbl 0769.68050

Valiant, Leslie G.

Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990, Lond. Math. Lect. Note Ser. 169, 84-94 (1992).

[For the entire collection see Zbl 0754.00019.]
In this note we first argue that if \(P \neq NP\) then any circuit-theoretic proof of this would have to be preceded by analogous results for the more constrained arithmetic model. This is because, as we shall observe, there are proven implications showing that if, for example, the Hamiltonian cycle problem (HC) requires exponential circuit size, then so does the analogous problem on arithmetic circuits. Since the set of valid algebraic identities in the latter model form a proper subset of those in the former, a lower bound proof for it should be strictly easier.
In spite of the above relationship the algebraic model is often regarded as an alternative, rather than a restriction of the Boolean model. One reason for this is that specific computations are usually understandable in one of these models, and not in both. In particular, the main power of the algebraic model derives from the possibility of cancellations, and it is usually difficult to express explicitly how these help in computing combinatorial problems.
Our second aim in this note is to give an example of an algorithm, namely the Samuelson-Berkowitz method for computing the determinant, where the intermediate terms that are computed but ultimately cancelled by the arithmetically circuit can be exhibited explicitly in combinatorial terms. The ease of computing the determinant can be attributed to the existence of such an auxiliary set of monomials with certain computational properties. A proof of an exponential lower bound on the complexity of a polynomial that is believed to be hard, such as the permanent or the Hamiltonian circuit polynomial, would involve establishing the nonexistence of such an auxiliary set. It is difficult to imagine how such a proof might go.
Finally, we observe that in low-level complexity, the arguments giving precedence to studying the algebraic model no longer hold. A major open problem area is that of proving for some explicit problem that it cannot be computed by unrestricted Boolean circuits simultaneously in size \(O(n)\) and depth \(O(\log n)\). We describe, via some conjectures, one candidate approach towards proving such a lower bound for problems such as sorting. Analogous conjectures exist for the algebraic model, but resolution of those would not imply the same for the Boolean case.

MSC:

68Q25	Analysis of algorithms and problem complexity
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Keywords:

arithmetic model; circuit size; arithmetic circuits; Boolean model; Samuelson-Berkowitz method for computing the determinant; low-level complexity; Boolean circuits

Citations:

Zbl 0754.00019