Berkholz, ChristophHölldobler, Steffen2020-08-212020-08-212015978-3-88579-419-6https://dl.gi.de/handle/20.500.12116/33853Dieser Beitrag ist eine deutschsprachige Zusammenfassung der Dissertation des Autors. In der Dissertation werden drei verwandte heuristische Verfahren zum Lösen schwerer Probleme untersucht: der k-Konsistenztest für das Constraint-Satisfaction-Problem, Resolution beschränkter Weite für 3-SAT und der Knotenpartitionierungsalgorithmus für das Graphisomorphieproblem. Die Hauptergebnisse der Dissertation sind untere Schranken an die Zeitkomplexität der Verfahren. In diesem Beitrag werden die untersuchten Verfahren eingeführt und die erzielten unteren Schranken vorgestellt.de1617-5468