Constraint-Satisfaction-Probleme: algebraische Struktur und komplexitätstheoretische Klassifikationen
Final Report Abstract
Programmiersprachen aus dem Gebiet der künstlichen Intelligenz oder Anfragesprachen aus dem Gebiet der Datenbanken sind oft so aufgebaut, dass eine Reihe von Einschränkungen (Constraints) an Variablen formuliert wird und die Ausführung des Programms nichts anderes ist als die Suche nach einer Lösung (etwa einem Datenbank-Eintrag), die alle Einschränkungen erfüllt. Die Frage, ob eine Lösung eines solchen sog. Constraint-Satisfaction- Problems (CSPs) existiert, ist im Allgemeinen NP-vollständig, also nach derzeitigem Wissensstand nicht mit vertretbarem Zeitaufwand durch einen Rechner lösbar. Im Projekt wurden dieses Problem der Erfüllbarkeit sowie weitere Berechnungsprobleme aus komplexitätstheoretischer Sicht untersucht und nach ihrer Berechnungsschwierigkeit klassifiziert. Dabei wurden sowohl reine als auch sog. quantifizierte CSPs betrachtet. Das Ziel war es jeweils, Einschränkungen an die Mengen der erlaubten Constraints zu finden, für die die Berechnungsprobleme effiziente Lösungen erlauben, bzw. Eigenschaften der verwendeten Constraints zu identifizieren, die eine effiziente Lösung verhindern. Im Einzelnen wurden folgende algorithmische Fragestellungen untersucht: Hat ein CSP oder ein quantifiziertes CSP eine Lösung? Sind zwei gegebene CSPs äquivalent (d.h. haben die gleichen Lösungen) oder isomorph (d.h. haben nach Umbenennung der Variablen die gleichen Lösungen)? Wie viele Lösungen hat ein CSP oder quantifiziertes CSP? Erstelle eine Liste (ohne Wiederholungen) aller Lösungen eines gegebenen (quantifizierten) CSPs. Hat eine Formel der Reiter'schen Default-Logik eine Lösung? Für den Spezialfall eines zweielementigen Grundbereichs konnten alle Probleme vollständig klassifiziert werden, d.h. es konnten alle Teilklassen von CSPs und quantifizierten CSPs identifiziert werden, für die effiziente Lösungsalgorithmen existieren; für den allgemeineren Fall eines beliebigen endlichen Universums wurden weitreichende komplexitätstheoretische Teilresultate erzielt. Für die angesprochene Fragestellung der Isomorphie ergibt sich ein recht interessantes Ergebnis; Es treten Fälle von Constraints auf, für die das Problem NP-vollständig ist, und es treten Fälle von Constraints auf, für die das Problem effizient lösbar ist. Für alle weiteren Fälle konnte gezeigt werden, dass das Isomorphieproblem für Constraints genauso schwierig wie das Problem der Graphenisomorphie ist, dem prominentesten Problem aus der Klasse NP, von dem weder bekannt ist, ob es NP-vollständig noch ob es effizient lösbar ist. Methodisch wurde im Projekt primär auf Strukturuntersuchungen von Constraints mit Hilfsmitteln aus der universellen Algebra zurückgegriffen. Die bestehenden Beziehungen aus Galois- und Clone-Theorie wurden dazu zunächst zum Teil erheblich erweitert.
Publications
- E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. The complexity of satisfiability problems: Refining Schaefer's theorem. In Proceedings Mathematical Foundations of Computer Science, volume 3618 of Lecture Notes in Computer Science, pages 71-82. Springer-Verlag, 2005.
- E. Böhler, E. Hemaspaandra, S. Reith, and H. Vollmer. The complexity of Boolean constraint isomorphism. In Proceedings 21st Symposium on Theoretical Aspects of Computer Science, volume 2296 of Lecture Notes in Computer Science, pages 164-175, Berlin Heidelberg, 2004. Springer Verlag.
- E. Böhler, N. Creignou, S. Reith, and H. Vollmer. Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. ACM-SIGACT Newsletter, 34(4):38-52, 2003
- E. Böhler, N. Creignou, S. Reith, and H. Vollmer. Playing with Boolean blocks, part II: Constraint satisfaction problems. ACM-SIGACT Newsletter, 35(1}:22-35, 2004.
- E. Böhler, S. Reith, H. Schnoor, and H. Vollmer. Bases for Boolean co-clones. Information Processing Letters, 96:59-66, 2005.
- H. Schnoor, I. Schnoor. Enumerating all solutions for constraint satisfaction problems. In Proceedings 24th Symposium on Theoretical Aspects of Computer Science, volume 4393 of Lecture Notesin Computer Science, pages 694-705, Berlin Heidelberg, 2007. Springer Verlag.
- H. Schnoor. Algebraic Techniques for Satisfiability Problems. Dissertation, Leibniz Universität Hannover, Fakultät für Elektrotechnik und Informatik, 2007.
- H. Vollmer. Computational complexity of constraint satisfaction. In Proceedings 3rd Computability in Europe, volume 4497 of Lecture Notes in Computer Science, pages 748-757, Berlin Heidelberg, 2007. Springer Verlag.
- H. Vollmer. The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis. Theory of Computing Systems, 2008.
- I. Schnoor. The Weak Base Method for Constraint Satisfaction Problems. Dissertation, Leibniz Universität Hannover, Fakultät für Elektrotechnik und Informatik, 2007.
- M. Bauland and E. Hemaspaandra. Isomorphic implication. In Proceedings Mathematical Foundations of Computer Science, volume 3618 of Lecture Notes in Computer Science, pages 119-130, Berlin Heidelberg, 2005. Springer-Verlag.
- M. Bauland, R Chapdelaine, N. Creignou, M. Hermann, and H. Vollmer. An algebraic approach to the complexity of generalized conjunctive queries. In Proceedings 7th International Conference on Theory and Applications of Satisfiability Testing, Revised Selected Papers, volume 3542 of Lecture Notes in Computer Science, pages 30-45. Springer Verlag, 2005.
- M. Bauland. Complexity Results for Boolean Constraint Satisfaction Problems. Dissertation, Leibniz Universität Hannover, Fakultät für Elektrotechnik und Informatik, 2007.
- R Chapdelaine, M. Hermann, I. Schnoor. Complexity of default logic on generalized conjunctive queries. In Proceedings 9th Logic Programming and Nonmonotonic Reasoning, volume 4483 of Lecture Notes in Computer Science, pages 58-70, Berlin Heidelberg, 2007. Springer Verlag.
