Dagstuhl Seminar 24421
SAT and Interactions
( Oct 13 – Oct 18, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24421
Organizers
- Olaf Beyersdorff (Friedrich-Schiller-Universität Jena, DE)
- Laura Kovács (TU Wien, AT)
- Meena Mahajan (The Institute of Mathematical Sciences - Chennai, IN)
- Martina Seidl (Johannes Kepler Universität Linz, AT)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
The problem of deciding whether a propositional formula is satisfiable (SAT) is one of the most fundamental problems in computer science. Its theoretical significance derives from the Cook-Levin Theorem, identifying SAT as the first NP-complete problem. Since then SAT has become a reference for an enormous variety of complexity statements, among them the celebrated P vs NP problem.
There are many generalisations of SAT to logics such as quantified Boolean formulas (QBF), modal and first-order (FO) logics. Often these logics present harder satisfiability problems (e.g. PSPACE-complete for QBF), but can express many practically relevant problems more succinctly, thus applying to more real-world problems.
Due to its practical implications, intensive research has been performed to solve SAT problems in an automated fashion. The last decades have seen the development of practically efficient algorithms for SAT, QBF, and further logics, and their implementation as solvers, which successfully solve huge industrial instances.
As the fourth in its series, the Dagstuhl Seminar took a broad perspective on the theory of SAT, encompassing propositional logic, QBF, and first-order theorem proving. Its main aim was to bring together researchers from different areas of activity in SAT and first-order logic, including computational complexity, proof complexity, proof theory, theorem proving, and solving, so that they can communicate state-of-the-art advances and embark on a systematic interdisciplinary interaction.
The Dagstuhl Seminar placed particular emphasis on the three following fields: propositional logic (complexity, proof complexity, solving), QBF (proof complexity and solving), and FO theorem proving. A particularly novel feature was the interaction of the communities active in proof complexity and solving of SAT/QBF (the propositional logics) with the first-order theorem proving community. There appeared to be overall consensus among the participants that this interchange of ideas between SAT solving techniques and first-order theorem proving was very stimulating and might particularly prove useful towards further efficient implementations of first-order proof rules.
To facilitate interactions between participants from the different fields, the seminar included a number of survey talks to introduce neighbouring communities to the main notions, results, and challenges of the represented areas. The following survey talks were given towards the beginning of the seminar:
- Marc Vinyals: SAT Solving and Proof Complexity;
- Friedrich Slivovsky: QBF Solving and Proof Complexity;
- Cesare Tinelli: An introduction to Satisfiability Modulo Theories;
- Stephan Schulz: First-order Theorem Proving.
Each of these surveys was accompanied by one or more sessions with contributed talks dedicated to recent specific results of the field.
The seminar also included an open problem session where participants discussed open research directions and specific problems. The following topics were discussed:
- Stephan Schulz: Can we achieve good engineering and long-term
viability of systems?
Software projects often get abandoned over time, especially if the original authors leave. We are looking for technical and organisational solutions to mitigate this. - Sophie Tourret: Beyond critical.
There are established techniques to compare the hardness of propositional formulas. Can we find analogous techniques for first-order logic and SMT? Particularly interesting are cases outside the decidable fragments of these theories. - Neil Thapen: Where is symmetry breaking in TFNP?
Symmetry breaking techniques can be understood as the optimisation problem of finding a lexically minimal assignment, which is in TFNP. We know it is in PLS, it might be in CLS, but can we at least show that it is not in FP? This has implications on the strength of Extended Frege. - Adrian Rebola-Pardo: How should we design future proof
formats?
There is a variety of practical proof formats that need to be suitable for verification and querying. Is it possible to design good universal proof formats? Important considerations include binary encodings, non-clausal representations, specific addition and deletion rules, the needs of incremental SAT solvers, and parallel proof checking. - Florent Capelli: Properties of a hypergraph measure. The β-hyperorderwidth is a purely graph-theoretic measure on hypergraphs. How does it compare to established hypergraph measures? For example, there is a hypergraph that has β-hyperorderwidth 1, but its incidence graph has treewidth n. Is this possible the other way around? Can we generalize the definition of β-hyperorderwidth?
The seminar included ample time for discussions and informal interactions, a feature that appeared to be largely welcomed and productively used. On Wednesday afternoon we organised a traditional well-attended hike. On Thursday evening, we had a joyful music night with contributions from Sophie Tourret, Ilario Bonacina, Dominik Scheder, Florent Capelli, and Kaspar Kasche. They played music by Marin Marais, Georg Philipp Telemann, Wolfgang Amadeus Mozart, Francis Poulenc, and George Gershwin.
The organisers believe that the seminar fulfilled their original high goals: the talks were well received and triggered many discussions. Many participants reported about the inspiring seminar atmosphere, fruitful interactions, and a generally positive experience. The organisers and participants wish to thank the staff and the management of Schloss Dagstuhl for their assistance and excellent support in the arrangement of a very successful and productive event.
Creative Commons BY 4.0
Olaf Beyersdorff, Laura Kovács, Meena Mahajan, and Martina Seidl
The problem of deciding whether a propositional formula is satisfiable (SAT) is one of the most fundamental problems in computer science, both theoretically and practically. Due to its practical implications, intensive research has been performed on how to solve SAT problems in an automated fashion, and SAT solving is now a ubiquitous tool to solve many hard problems, both from industry and mathematics.
There are many generalizations of the SAT problem to further logics, including quantified Boolean formulas (QBFs), modal logics, and temporal logics. These logics present even harder satisfiability problems as they are associated with complexity classes such as PSPACE, which encompasses NP. Nevertheless, the last decade has seen the development of practically efficient algorithms for QBFs, SAT modulo theories (SMT), and further logics and their implementation as solvers, which successfully solve huge industrial instances. Since QBFs, SMT, modal logics, and temporal logics can express many practically relevant problems far more succinctly, they apply to even more real-world problems from artificial intelligence, bioinformatics, verification, and planning.
SAT is also increasingly being applied in logics that are not decidable, particularly in the context of first-order theorem proving. Here, fast SAT solvers are used for reasoning sub-tasks and for guiding the theorem provers.
The main aim of this Dagstuhl Seminar is to bring together researchers from different areas of activity on SAT and researchers that work in the field of first-order theorem proving so that they can communicate state-of-the-art advances and embark on a systematic interaction that will enhance the synergy between the different areas.
Olaf Beyersdorff, Laura Kovács, Meena Mahajan, and Martina Seidl
Please log in to DOOR to see more details.
- Albert Atserias (UPC Barcelona Tech, ES) [dblp]
- Olaf Beyersdorff (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Ilario Bonacina (UPC Barcelona Tech, ES) [dblp]
- Florent Capelli (University of Artois/CNRS - Lens, FR) [dblp]
- Leroy Nicholas Chew (TU Wien, AT) [dblp]
- Anupam Das (University of Birmingham, GB) [dblp]
- Susanna de Rezende (Lund University, SE) [dblp]
- Katalin Fazekas (TU Wien, AT) [dblp]
- Mathias Fleury (Universität Freiburg, DE) [dblp]
- Pascal Fontaine (University of Liège, BE) [dblp]
- Marlene Gründel (Friedrich-Schiller-Universität Jena, DE)
- Clemens Hofstadler (Universität Kassel, DE) [dblp]
- Kaspar Kasche (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
- Wietze Koops (Lund University, SE & University of Copenhagen, DK)
- Konstantin Korovin (University of Manchester, GB) [dblp]
- Laura Kovács (TU Wien, AT) [dblp]
- Massimo Lauria (Sapienza University of Rome, IT) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Barnaby Martin (Durham University, GB) [dblp]
- Stefan Mengel (CNRS, CRIL - Lens, FR) [dblp]
- Claudia Nalon (University of Brasília, BR) [dblp]
- Jakob Nordström (University of Copenhagen, DK & Lund University, SE) [dblp]
- Tomáš Peitl (TU Wien, AT) [dblp]
- Florian Pollitt (Universität Freiburg, DE)
- Michael Rawson (TU Wien, AT) [dblp]
- Adrian Rebola-Pardo (TU Wien, AT & Johannes Kepler Universität Linz, AT) [dblp]
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Dominik Alban Scheder (TU Chemnitz, DE) [dblp]
- Tanja Schindler (Universität Basel, CH) [dblp]
- Stephan Schulz (Duale Hochschule Baden-Württemberg - Stuttgart, DE) [dblp]
- Martina Seidl (Johannes Kepler Universität Linz, AT) [dblp]
- Friedrich Slivovsky (University of Liverpool, GB) [dblp]
- Luc Spachmann (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Martin Suda (Czech Technical University - Prague, CZ) [dblp]
- Stefan Szeider (TU Wien, AT) [dblp]
- Neil Thapen (The Czech Academy of Sciences - Prague, CZ) [dblp]
- Cesare Tinelli (University of Iowa - Iowa City, US) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Sophie Tourret (INRIA Nancy - Grand Est, FR) [dblp]
- Marc Vinyals (University of Auckland, NZ) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Andrei Voronkov (University of Manchester, GB) [dblp]
Related Seminars
Classification
- Artificial Intelligence
- Computational Complexity
- Logic in Computer Science
Keywords
- satisfiability problems
- computational and proof complexity
- combinatorics
- first-order logic
- solvers for satisfiability problems
- non-classical logics
