Complexity-theoretic algebra. II: Boolean algebras (Q915723)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4152359
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Complexity-theoretic algebra. II: Boolean algebras |
scientific article; zbMATH DE number 4152359 |
Statements
Complexity-theoretic algebra. II: Boolean algebras (English)
0 references
1989
0 references
[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)].
0 references
oracles
0 references
complexity of constructions of ideals
0 references
countable atomless Boolean algebra
0 references
Recursively enumerable ideals
0 references
recursively axiomatizable theories
0 references
recursive ideals
0 references
decidable theories
0 references
maximal recursive ideals
0 references
recursively axiomatizable complete theories
0 references
0 references
0 references
0.8152080178260803
0 references
0.7679515480995178
0 references
