TU Darmstadt / ULB / TUprints

On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices

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
Article, Secondary publication, Publisher's Version

[img] Text
s00012-021-00760-3.pdf
Copyright Information: CC BY 4.0 International - Creative Commons, Attribution.

Download (584kB)
Item Type: Article
Type of entry: Secondary publication
Title: On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices
Language: English
Date: 3 September 2024
Place of Publication: Darmstadt
Year of primary publication: 31 December 2022
Place of primary 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.26083/tuprints-00023423
Corresponding Links:
Origin: Secondary publication DeepGreen
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
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-234239
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics > Logic
Date Deposited: 03 Sep 2024 13:39
Last Modified: 03 Sep 2024 13:39
SWORD Depositor: Deep Green
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/23423
PPN:
Export:
Actions (login required)
View Item View Item