Herrmann, Christian (2022)
On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices.
In: Algebra universalis, 83 (1)
doi: 10.1007/s00012-021-00760-3
Article, Bibliographie
This is the latest version of this item.
Abstract
We study the computational complexity of the satisfiability problem and the complement of the equivalence problem for complemented (orthocomplemented) modular lattices L and classes thereof. Concerning a simple L of finite height, NP-hardness is shown for both problems. Moreover, both problems are shown to be polynomial-time equivalent to the same feasibility problem over the division ring D whenever L is the subspace lattice of a D-vector space of finite dimension at least 3. Considering the class of all finite dimensional Hilbert spaces, the equivalence problem for the class of subspace ortholattices is shown to be polynomial-time equivalent to that for the class of endomorphism ∗-rings with pseudo-inversion; moreover, we derive completeness for the complement of the Boolean part of the nondeterministic Blum-Shub-Smale model of real computation without constants. This result extends to the additive category of finite dimensional Hilbert spaces, enriched by adjunction and pseudo-inversion.
| Item Type: | Article |
|---|---|
| Erschienen: | 2022 |
| Creators: | Herrmann, Christian |
| Type of entry: | Bibliographie |
| Title: | On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices |
| Language: | English |
| Date: | 31 December 2022 |
| Place of Publication: | Basel |
| Publisher: | Springer International Publishing |
| Journal or Publication Title: | Algebra universalis |
| Volume of the journal: | 83 |
| Issue Number: | 1 |
| Collation: | 28 Seiten |
| DOI: | 10.1007/s00012-021-00760-3 |
| Corresponding Links: | |
| Abstract: | We study the computational complexity of the satisfiability problem and the complement of the equivalence problem for complemented (orthocomplemented) modular lattices L and classes thereof. Concerning a simple L of finite height, NP-hardness is shown for both problems. Moreover, both problems are shown to be polynomial-time equivalent to the same feasibility problem over the division ring D whenever L is the subspace lattice of a D-vector space of finite dimension at least 3. Considering the class of all finite dimensional Hilbert spaces, the equivalence problem for the class of subspace ortholattices is shown to be polynomial-time equivalent to that for the class of endomorphism ∗-rings with pseudo-inversion; moreover, we derive completeness for the complement of the Boolean part of the nondeterministic Blum-Shub-Smale model of real computation without constants. This result extends to the additive category of finite dimensional Hilbert spaces, enriched by adjunction and pseudo-inversion. |
| Uncontrolled Keywords: | Ortholattice of subspaces, Matrix*-ring, Complemented modular lattice, Satisfiability problems, Complexity, Hilbert category |
| Identification Number: | Artikel-ID: 5 |
| Classification DDC: | 500 Science and mathematics > 510 Mathematics |
| Divisions: | 04 Department of Mathematics 04 Department of Mathematics > Logic |
| Date Deposited: | 05 Sep 2024 07:14 |
| Last Modified: | 05 Sep 2024 11:44 |
| PPN: | 521125219 |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
Available Versions of this Item
-
On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices. (deposited 03 Sep 2024 13:39)
- On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices. (deposited 05 Sep 2024 07:14) [Currently Displayed]
 |
Send an inquiry |
Options (only for editors)
 |
Show editorial Details |
Drucken
Impressum