scientific article; zbMATH DE number 1421070
It is known that every computable Boolean algebra is computably isomorphic to a polynomial-time Boolean algebra. The present paper studies the validity of this result in the case where the universe of the polynomial-time Boolean algebra is required to be in one of the following two forms: \(\text{Bin}(\omega)\), the set of natural numbers in binary representation, and \(\text{Tal}(\omega)\), the set of natural numbers in tally representation. The main results establish some conditions under which the computably isomorphim holds. For example, it is proved that if \(B\) is a countably infinite computable Boolean algebra such that both the set of atoms of \(B\) and the ideal generated by the atoms of \(B\) are computable, then \(B\) is computably isomorphic to a polynomial-time Boolean algebra with universe \(\text{Bin}(\omega)\) and to a polynomial-time Boolean algebra with universe \(\text{Tal}(\omega)\). For the entire collection see [Zbl 0923.00014].
- Computable Boolean algebras
- scientific article; zbMATH DE number 2203952
- Atomless Boolean algebras computable in polynomial time
- Computational bound on complexity of polynomial representations of Boolean functions
- Complexity-theoretic algebra. II: Boolean algebras
- Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials
- Boolean complexity classes vs. their arithmetic analogs
- scientific article; zbMATH DE number 1534579
- Publication:3487327
- scientific article; zbMATH DE number 2193711
- The algebraic structure of the isomorphic types of tally, polynomial time computable sets
- Categoricity for primitive recursive and polynomial Boolean algebras
- Eliminating unbounded search in computable algebra
- Punctual dimension of algebraic structures in certain classes
- Punctual copies of algebraic structures
- Graphs are not universal for online computability
- The back-and-forth method and computability without delay
- Atomless Boolean algebras computable in polynomial time
- Is there a logic for polynomial time?
- P ≠ NP for all infinite Boolean algebras
- Boolean complexity classes vs. their arithmetic analogs
- A structure of punctual dimension two
- AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
- Algebraic structures computable without delay
- Computable isomorphisms of Boolean algebras with operators
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4946095)