Schaltkreiskomplexität, Parametrische Komplexität und logische Definierbarkeit

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 186219630

• Final Report Year: 2014

Final Report Abstract

Die zentralen Ergebnisse sind starke untere Schranken für Constraint Propagation und verwandte Heuristiken wie Resolution und Colour Refinement. Zwei besonders bemerkenswerte Aspekte dieser unteren Schranken sind erstens, dass sie zum Teil unkonditional sind, also auf keinen unbewiesenen komplexitätstheoretischen Annahmen beruhen, und zweitens, dass hier rein algorithmische bzw. komplexitätstheoretische Aussagen, die zunächst nichts mit Logik zu tun haben, mit Hilfe von Techniken aus der Logik (Ehrenfeuch-Fraïssé Spiele für verschiedene k-Variablen Logiken) bewiesen wurden. Wir sind insgesamt allerdings deutlich von den im Antrag aufgeworfenen Fragen abgewichen. Ich habe versucht, zu erläutern, wie dies kam. Tatsächlich bin ich der Meinung, dass die im Projekt beantworteten Fragen zum Teil interessanter waren als die im Antrag gestellten. Die wichtigsten im Antrag gestellten Fragen sind nach wie vor offen, aber wohl auch sehr schwierig - etwa die nach einer Verallgemeinerung von Rossman’s unterer Schranke für das k-Cliquen-Problem auf größere Schaltkreisklassen.

Publications

• Pebble games and linear equations. In P. Cégielski and A. Durand, editors, Proceedings of the 26th International Workshop on Computer Science Logic, volume 16 of Leibniz International Proceedings in Informatics (LIPIcs), pages 289–304, 2011
  M. Grohe and M. Otto
  
• On the complexity of finding narrow proofs. In Foundations of Computer Science, IEEE Annual Symposium on, pages 351–360, 2012
  Christoph Berkholz
  
• Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. In Computer Science Logic 2013 (CSL 2013), volume 23 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61–80, 2013
  Christoph Berkholz, Andreas Krebs, and Oleg Verbitsky
  
• Lower bounds for existential pebble games and kconsistency tests. Logical Methods in Computer Science, 9(4), 2013
  Christoph Berkholz
  
• On the speed of constraint propagation and the time complexity of arc consistency testing. In Mathematical Foundations of Computer Science 2013, volume 8087 of Lecture Notes in Computer Science, pages 159–170, 2013
  Christoph Berkholz and Oleg Verbitsky
  
• Tight lower and upper bounds for the complexity of canonical colour refinement. In Algorithms – ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 145–156, 2013
  Christoph Berkholz, Paul Bonsma, and Martin Grohe