Complexity-theoretic algebra. II: Boolean algebras (Q915723): Difference between revisions

[For Part I see Rend. Semin. Mat., Torino 1987, Fasc. Spec., 1-10 (1987; Zbl 0664.68052).] The paper studies the complexity of constructions of ideals within a fixed countable atomless Boolean algebra. The following analogies hold: Recursively enumerable ideals correspond to recursively axiomatizable theories, recursive ideals correspond to decidable theories, maximal recursive ideals correspond to recursively axiomatizable complete theories. The results are strongly connected with, or motivated by, the conflicting oracle constructions of P versus NP by \textit{T. Baker}, \textit{J. Gill} and \textit{R. Solovay} [SIAM J. Comput. 4, 431-442 (1975; Zbl 0323.68033)].