5 Search Results for "Schnoor, Henning"

Document
DOI: 10.4230/LIPIcs.TQC.2025.6
Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes

Authors: Ricardo Rivera Cardoso, Alex Meiburg, and Daniel Nagaj

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
Previously, all known variants of the Quantum Satisfiability (QSAT) problem - consisting of determining whether a k-local (k-body) Hamiltonian is frustration-free - could be classified as being either in 𝖯; or complete for NP, MA, or QMA₁. Here, we present new qubit variants of this problem that are complete for BQP₁, coRP, QCMA, PI(coRP,NP), PI(BQP₁,NP), PI(BQP₁,MA), SoPU(coRP,NP), SoPU(BQP₁,NP), and SoPU(BQP₁,MA). Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer’s dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial BQP₁-complete problem. We first construct QSAT problems on qudits that are complete for BQP₁, coRP, and QCMA. These are made by restricting the finite set of Hamiltonians to consist of elements similar to H_{init}, H_{prop}, and H_{out}, seen in the circuit-to-Hamiltonian transformation. Usually, these are used to demonstrate hardness of QSAT and Local Hamiltonian problems, and so our proofs of hardness are simple. The difficulty lies in ensuring that all Hamiltonians generated with these three elements can be decided in their respective classes. For this, we build our Hamiltonian terms with high-dimensional data and clock qudits, ternary logic, and either monogamy of entanglement or specific clock encodings. We then show how to express these problems in terms of qubits, by proving that any QCSP can be reduced to a qubit problem while maintaining the same complexity - something not believed possible classically. The remaining six problems are obtained by considering "sums" and "products" of some of the QSAT problems mentioned here. Before this work, the QSAT problems generated in this way resulted in complete problems for PI and SoPU classes that were trivially equal to NP, MA, or QMA₁. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for coRP, BQP₁, and QCMA, we note that those constructions are flawed. Here, we rework them, provide correct proofs, and obtain improvements on the required qudit dimensionality.
Cite as

Ricardo Rivera Cardoso, Alex Meiburg, and Daniel Nagaj. Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{riveracardoso_et_al:LIPIcs.TQC.2025.6,
  author =	{Rivera Cardoso, Ricardo and Meiburg, Alex and Nagaj, Daniel},
  title =	{{Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.6},
  URN =		{urn:nbn:de:0030-drops-240557},
  doi =		{10.4230/LIPIcs.TQC.2025.6},
  annote =	{Keywords: Quantum complexity theory, quantum satisfiability, circuit-to-Hamiltonian, pairwise union of classes, pairwise intersection of classes}
}
Document
DOI: 10.4230/LIPIcs.CSL.2015.277
A Van Benthem Theorem for Modal Team Semantics

Authors: Juha Kontinen, Julian-Steffen Müller, Henning Schnoor, and Heribert Vollmer

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract
The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework of modal dependence logic (MDL) and team semantics. We show that Modal Team Logic (MTL) extending MDL by classical negation captures exactly the FO-definable bisimulation invariant properties of Kripke structures and teams. We also compare the expressive power of MTL to most of the variants and extensions of MDL recently studied in the area.
Cite as

Juha Kontinen, Julian-Steffen Müller, Henning Schnoor, and Heribert Vollmer. A Van Benthem Theorem for Modal Team Semantics. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 277-291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kontinen_et_al:LIPIcs.CSL.2015.277,
  author =	{Kontinen, Juha and M\"{u}ller, Julian-Steffen and Schnoor, Henning and Vollmer, Heribert},
  title =	{{A Van Benthem Theorem for Modal Team Semantics}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{277--291},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.277},
  URN =		{urn:nbn:de:0030-drops-54206},
  doi =		{10.4230/LIPIcs.CSL.2015.277},
  annote =	{Keywords: modal logic, dependence logic, team semantics, expressivity, bisimulation, independence, inclusion, generalized dependence atom}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1356
On the Complexity of Elementary Modal Logics

Authors: Edith Hemaspaandra and Henning Schnoor

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a very general classification for a wide class of relevant logics: Many important subclasses of modal logics can be obtained by restricting the allowed models with first-order Horn formulas. We show that the satisfiability problem for each of these logics is either NP-complete or PSPACE-hard, and exhibit a simple classification criterion. Further, we prove matching PSPACE upper bounds for many of the PSPACE-hard logics.
Cite as

Edith Hemaspaandra and Henning Schnoor. On the Complexity of Elementary Modal Logics. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 349-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hemaspaandra_et_al:LIPIcs.STACS.2008.1356,
  author =	{Hemaspaandra, Edith and Schnoor, Henning},
  title =	{{On the Complexity of Elementary Modal Logics}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{349--360},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1356},
  URN =		{urn:nbn:de:0030-drops-13561},
  doi =		{10.4230/LIPIcs.STACS.2008.1356},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.06401.6
Enumerating all Solutions for Constraint Satisfaction Problems

Authors: Henning Schnoor and Ilka Schnoor

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract
We contribute to the study of efficient enumeration algorithms for all solutions of constraint satisfaction problems. The only algorithm known so far, presented by Creignou and Hébrard and generalized by Cohen, reduces the enumeration problem for a constraint language $Gamma$ to the decision problem for a slightly enlarged constraint language $Gamma^+,$ i.e., it yields an efficient enumeration algorithm for the case where $mathrm{CSP}(Gamma^+)$ is tractable. We develop a new class of algorithms, yielding efficient enumeration algorithms for a broad class of constraint languages. For the three-element domain, we achieve a first step towards a dichotomy theorem for the enumeration problem.
Cite as

Henning Schnoor and Ilka Schnoor. Enumerating all Solutions for Constraint Satisfaction Problems. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schnoor_et_al:DagSemProc.06401.6,
  author =	{Schnoor, Henning and Schnoor, Ilka},
  title =	{{Enumerating all Solutions for Constraint Satisfaction Problems}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.6},
  URN =		{urn:nbn:de:0030-drops-8040},
  doi =		{10.4230/DagSemProc.06401.6},
  annote =	{Keywords: Complexity, constraint satisfaction, enumeration}
}
Document
DOI: 10.4230/DagSemProc.06401.7
New Algebraic Tools for Constraint Satisfaction

Authors: Henning Schnoor and Ilka Schnoor

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract
The Galois correspondence involving polymorphisms and co-clones has received a lot of attention in regard to constraint satisfaction problems. However, it fails if we are interested in a reduction giving equivalence instead of only satisfiability-equivalence. We show how a similar Galois connection involving weaker closure operators can be applied for these problems. As an example of the usefulness of our construction, we show how to obtain very short proofs of complexity classifications in this context.
Cite as

Henning Schnoor and Ilka Schnoor. New Algebraic Tools for Constraint Satisfaction. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schnoor_et_al:DagSemProc.06401.7,
  author =	{Schnoor, Henning and Schnoor, Ilka},
  title =	{{New Algebraic Tools for Constraint Satisfaction}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.7},
  URN =		{urn:nbn:de:0030-drops-8057},
  doi =		{10.4230/DagSemProc.06401.7},
  annote =	{Keywords: Constraints, Partial Clones, Galois Correspondence}
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2015
  • 1 2008
  • 2 2006

  • Refine by Author
  • 4 Schnoor, Henning
  • 2 Schnoor, Ilka
  • 1 Hemaspaandra, Edith
  • 1 Kontinen, Juha
  • 1 Meiburg, Alex
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Complexity
  • 1 Constraints
  • 1 Galois Correspondence
  • 1 Partial Clones
  • 1 Quantum complexity theory
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact