Herrmann, Christian (2024)
On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices.
In: Algebra universalis, 2022, 83 (1)
doi: 10.26083/tuprints-00023423
Artikel, Zweitveröffentlichung, Verlagsversion
 | Es ist eine neuere Version dieses Eintrags verfügbar. |
Kurzbeschreibung (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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2024 |
| Autor(en): | Herrmann, Christian |
| Art des Eintrags: | Zweitveröffentlichung |
| Titel: | On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices |
| Sprache: | Englisch |
| Publikationsjahr: | 3 September 2024 |
| Ort: | Darmstadt |
| Publikationsdatum der Erstveröffentlichung: | 31 Dezember 2022 |
| Ort der Erstveröffentlichung: | Basel |
| Verlag: | Springer International Publishing |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Algebra universalis |
| Jahrgang/Volume einer Zeitschrift: | 83 |
| (Heft-)Nummer: | 1 |
| Kollation: | 28 Seiten |
| DOI: | 10.26083/tuprints-00023423 |
| URL / URN: | https://tuprints.ulb.tu-darmstadt.de/23423 |
| Zugehörige Links: | |
| Herkunft: | Zweitveröffentlichung DeepGreen |
| Kurzbeschreibung (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. |
| Freie Schlagworte: | Ortholattice of subspaces, Matrix*-ring, Complemented modular lattice, Satisfiability problems, Complexity, Hilbert category |
| ID-Nummer: | Artikel-ID: 5 |
| Status: | Verlagsversion |
| URN: | urn:nbn:de:tuda-tuprints-234239 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Fachbereich(e)/-gebiet(e): | 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Logik |
| Hinterlegungsdatum: | 03 Sep 2024 13:39 |
| Letzte Änderung: | 05 Sep 2024 07:06 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
Verfügbare Versionen dieses Eintrags
- On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices. (deposited 03 Sep 2024 13:39) [Gegenwärtig angezeigt]
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum