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.