Lower Bounds for Heuristic Algorithms

Berkholz, Christoph; Grohe, Martin; Otto, Martin

doi:34662

Lower Bounds for Heuristic Algorithms = Untere Schranken für heuristische Algorithmen

Berkholz, Christoph

2014 & 2015

Verantwortlichkeitsangabevorgelegt von Christoph Berkholz

ImpressumAachen : Publikationsserver der RWTH Aachen University 2014

Umfang169 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2014

Prüfungsjahr: 2014. - Publikationsjahr: 2015

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor) ; Otto, Martin (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-12-04

Online
URN: urn:nbn:de:hbz:82-rwth-2015-004945
URL: https://publications.rwth-aachen.de/record/462250/files/462250.pdf
URL: https://publications.rwth-aachen.de/record/462250/files/462250.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Für das Constraint-Satisfaction-Problem (CSP), das Erfüllbarkeitsproblem der Aussagenlogik und das Graphisomorphieproblem sind keine effizienten Algorithmen bekannt.Um sie zu lösen werden deshalb heuristische Algorithmen mit polynomieller Laufzeit eingesetzt. In der vorliegenden Dissertation werden drei klassische Heuristiken für die genannten Entscheidungsprobleme dahingehend untersucht, ob sie mit schnelleren als den bekannten Algorithmen implementiert werden können.Die k-Konsistenz-Heuristik für das CSP versucht durch sukzessives Ableiten neuer Bedingungen lokal konsistente Instanzen zu erzeugen und kann mit einer Laufzeit von O(n^{2k}) implementiert werden.Wir zeigen, dass der Anstieg der Laufzeit mit wachsendem Parameter k unvermeidbar ist. Dazu beweisen wir für eine absolute Konstante c>0, dass es nicht möglich ist in Zeit O(n^{ck}) zu entscheiden, ob lokale Konsistenz auf einer binären CSP-Instanz erreicht werden kann.Weiterhin untersuchen wir den Ableitungsprozess, der k-Konsistenz-Algorithmen zugrunde liegt, und beweisen eine optimale untere Schranke an die Anzahl der sequentiell abhängigen Ableitungsschritte. Eine Heuristik für das aussagenlogische Erfüllbarkeitsproblem ist das Suchen nach einer Resolutionswiderlegung, in der jede Klausel höchstens k Literale enthält. Eine solche Resolutionswiderlegung der Weite k kann von einem einfachen Suchalgorithmus in Zeit O(n^(k+1)) gefunden werden.Wir zeigen für eine absolute Konstante c>0, dass es unmöglich ist in Zeit O(n^(ck)) zu entscheiden, ob eine Resolutionswiderlegung der Weite k existiert.Die beiden unteren Schranken an die Laufzeit für lokale Konsistenz und Resolution beschränkter Weite kommen ohne komplexitätstheoretische Annahmen aus und verdeutlichen eine der wenigen Anwendung des Zeithierarchiesatzes auf natürliche Entscheidungsprobleme.Der naive Klassifizierungsalgorithmus für das Graphisomorphieproblem berechnet eine stabile Färbung der Knotenmenge eines Graphen durch iteratives Verfeinern der Farbklassen.Durch geschickte Auswahl der zu verfeinernden Farbklassen kann das Verfahren auf zusammenhängenden Graphen mit n Knoten und m Kanten mit einer Laufzeit von O(m log(n)) implementiert werden. Wir zeigen, dass dieses Vorgehen optimal ist und konstruieren dazu eine Familie von Graphen auf der jede Sequenz von Verfeinerungen m log(n) Berechnungsschritte benötigt.

The constraint satisfaction problem, the Boolean satisfiability problem and the graph isomorphism problem do not have efficient algorithms.In order to solve these problems, one utilizes heuristic algorithms of polynomial running time.The present thesis studies three classical heuristics for the above-mentioned decision problems and answers the question whether they can be implemented more efficient than with the fastest known algorithms.The k-consistency heuristic for the constraint satisfaction problem tries to establish local consistency by iteratively propagating new constraints and can be implemented time O(n^(2k)).We show that the degree of the polynomial that bounds the running time has to increase linear in k. To achieve this, we prove for a fixed constant c>0 that there is no algorithm of running time O(n^(ck)) that decides whether k-consistency can be established.Furthermore, we analyze the propagation process of k-consistency algorithms and prove optimal lower bounds on the number of nested propagation steps.One heuristic for the Boolean satisfiability problem is to find resolution refutations in which every clause contains at most k literals. Such refutations of width k can be found in time O(n^(k+1)) by a simple search procedure.We show for a fixed constant c>0, that it cannot be decided in time O(n^(ck)) whether a given formula has a resolution refutation of width k.The lower bounds on the time complexity for k-consistency and bounded width resolution do not rely on complexity theoretic assumptions and demonstrate one of the rare examples where the deterministic time hierarchy theorem can be applied to natural decision problems. The color refinement heuristic for the graph isomorphism problem computes a stable coloring of the vertices of a graph by iteratively refining the color classes.By refining the color classes in a clever order, the color refinement procedure can be implemented in time O(m log(n)) on connected graphs with n vertices and m edges.We show that this refining strategy is optimal.To prove this, we construct graphs where every possible order of refining operations needs at least m log(n) computation steps.

OpenAccess:
PDF PDF (PDFA)
(additional files)