2018/11/19 by Christian Herrmann, Herrmann, Christian
Computer Science · #03D78 #06C15 #06C20 #16R10 #68Q17 #81P10 #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO) #Rough Sets and Fuzzy Logic #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1811.07846
openalex publication_date 2018/11/19 · openalex created_date 2018/11/29 · openalex updated_date 2026/07/28
We study the computational complexity of satisfiability problems for classes of simple finite height (ortho)complemented modular lattices L. For single finite L, these problems are shown tobe \mcNP-complete; for L of height at least 3, equivalent to a feasibility problem for the division ring associated with L. Moreover, it is shown that the equational theory of the class of subspace ortholattices as well as endomorphism *-rings (with pseudo-inversion) of finite dimensional Hilbert spaces is complete for the complement of the Boolean part of the nondeterministic Blum-Shub-Smale model of real computation without constants. This results extends to the category of finite dimensional Hilbert spaces, enriched by pseudo-inversion.