NDLI: Computational Complexity of Quantum Satisfiability

Content Provider	ACM Digital Library
Author	Herrmann, Christian Ziegler, Martin
Copyright Year	2016
Abstract	We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices. Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables: in the 1D case it coincides with Boolean propositional logic but, starting with dimension two, violates the distributive law. We introduce the weak and strong satisfiability problem for quantum logic propositional formulae. It turns out that in dimension two, both are also $\textit{NP}--complete.$ For higher-dimensional spaces $ℝ^{d}$ and $ℂ^{d}$ with $\textit{d}$ ≥ 3 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale (BSS) model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and extends the (still relatively scarce) list of problems established $NP_{ℝ}--complete$ with one, perhaps, closest in spirit to the classical Cook-Levin Theorem. More precisely, strong satisfiability of ∧ ∨ ∧ --terms is complete, while that of ∧ ∨--terms (i.e., those in conjunctive form) can be decided in polynomial time in dimensions $\textit{d}≥$ 2. The decidability of the infinite-dimensional case being still open, we proceed to investigate the case of indefinite finite dimensions. Here, weak satisfiability still belongs to $NP_{R}$ and strong satisfiability is still hard; the latter, in fact, turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations over matrix rings.
Starting Page	1
Ending Page	31
Page Count	31
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2869073
Journal	Journal of the ACM (JACM)
Volume Number	63
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-05-04
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Blum-Shub-Smale model Quantum logic Computational complexity Existential theory of the reals Satisfiability
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Computational Power of Infinite Time Blum–Shub–Smale Machines

Existential second-order logic over strings

VPSPACE and a Transfer Theorem over the Reals

VPSPACE and a Transfer Theorem over the Reals

Fixpoint logics, relational machines, and computational complexity

Time-space lower bounds for satisfiability

Computational complexity of geometric quantum logic ∗.

An Overview of the Theory of Computational Complexity

Guarded Negation

Computational Complexity of Quantum Satisfiability

Similar Documents

The Computational Power of Infinite Time Blum–Shub–Smale Machines

Existential second-order logic over strings

VPSPACE and a Transfer Theorem over the Reals

VPSPACE and a Transfer Theorem over the Reals

Fixpoint logics, relational machines, and computational complexity

Time-space lower bounds for satisfiability

Computational complexity of geometric quantum logic ∗.

An Overview of the Theory of Computational Complexity

Guarded Negation

Computational Complexity of Quantum Satisfiability