About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Complexity of Boolean algebras
Abstract
We show that the elementary theory of Boolean algebras is ≤log-complete for the Berman complexity class {n-ary union}c<ω STA(, 2cn, n), the class of sets accepted by alternating Turing machines running in time 2cn for some constant c and making at most n alternations on inputs of length n; thus the theory is computationally equivalent to the theory of real addition with order. We extend the completeness results to various subclasses of Boolean algebras, including the finite, free, atomic, atomless, and complete Boolean algebras. Finally we show that the theory of any finite collection of finite Boolean algebras is complete for PSPACE, while the theory of any other collection is ≤log-hard for {n-ary union}c<ω STA(, 2cn, n). © 1980.