Die Komplexität von Constraint-Satisfaction Problemen

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2004 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5432723

• Erstellungsjahr: 2009

Zusammenfassung der Projektergebnisse

Es ist uns meines Erachtens gelungen, zu den wesentlichen im Projektantrag genannten Fragestellungen substantielle Fortschritte zu erzielen. Als die Hauptresultate des Projekts sehe ich die erzielten Ergebnisse zu fraktionalen Kantenüberdeckungszahlen und strukturellen Kriterien für die effiziente Lösbarkeit von CSP und den bewiesenen Klassifikationssatz für die Komplexität von Partitionsfunktionen ZA an.

Projektbezogene Publikationen (Auswahl)

• Derandomization of PPSZ for Unique-SAT. In: F. Bacchus and T. Walsh, editors. Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing, volume 3569 of Lecture Notes in Computer Science, pages 216-225. Springer-Verlag, 2005
  D. Rolf
  
• Constraint satisfaction, with succinctly specified relations
  H. Chen and M. Grohe
  
• Constraint solving via fractional edge covers. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 289-298, 2006
  M. Grohe and D. Marx
  
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT. Journal on Satisfiability, Boolean Modeling and Computation, 1:111-122,2006
  D. Rolf
  
• sharpSAT - counting models with advanced component caching and implicit BCP. In: A. Biere and C.P. Gomes, editors. Theory and Applications of Satisfiability Testing - SAT2006, 9th International Conference, Seattle, WA, USA, August 12-15, 2006, Proceedings, volume 4121 of Lecture Notes in Computer Science, pages 424-429. Springer-Verlag, 2006
  M. Thurley
  
• The structure of tractable constraint satisfaction problems. In: R. Královic and P. Urzyczyn, editors, Proceedings of the 31st Symposium on Mathematical Foundations of Computer Science, Volume 4162 of Lecture, Notes in Computer Science, pages 58-72. Springer-Verlag, 2006
  M. Grohe
  
• Can you beat treewidth? In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 169-119,2007
  D. Marx
  
• Hypertree-width and related hypergraph invariants. European Journal of Combinatorics, 28:2167-2181, 2007
  I. Adler, G. Goulob, and M. Grohe
  
• The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54, 2007
  M. Grohe
  
• Non-dichotomies in constraint satisfaction complexity. In: L. Aceto, I. Damgaard, L.A. Goldberg, M.M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II, volume 5126 of Lecture Notes in Computer Science, pages 184-196. Springer-Verlag, 2008
  M. Bodirsky and M. Grohe
  
• Size bounds and query plans for relational joins. In: Proceedings ofthe 49th Annual IEEE Symposium on Foundations of Computer Science, pages 739-748,2008
  A. Atserias, M. Grohe, and D. Marx
  
• A complexity dichotomy for partition functions with mixed signs. In: S. Albers and J.-Y. Marion, editors, Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science, pages 493-504, 2009
  L.A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley
  
• Enumerating homomorphisms. In: S. Albers and J.-Y. Marion, editors, Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer-Science, psiges 231-242, 2009
  A. Bulatov, V. Dalmau, M. Grohe, and D. Marx
  
• The complexity of datalog on linear orders. Logical Methods in Computer Science, 5, 2009
  M. Grohe and G. Schwandtner
  
• Tradable structures for constraint satisfaction with tmth tables. In: S. Albers and J.-Y. Marion; editors, Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science, pages 649-660,2009
  D. Marx