LfD Logo

Phasenübergänge in kombinatorischen Optimierungsproblemen

Hintergrund:

Viele industriell relevante Fragestellungen lassen sich als kombinatorische Optimierungsprobleme formulieren, die häufig der Komplexitätsklasse NP angehören. Obwohl diese Probleme im Allgemeinen als schwer lösbar gelten, existieren häufig spezielle Instanzklassen, die effizient gelöst werden können. Ein bekanntes Beispiel ist das randomisierte 3-SAT-Problem, bei dem ein Phasenübergang in Abhängigkeit des Verhältnisses von Klauseln zu Variablen (α ≈ 4,267) beobachtet wird: Instanzen wechseln dabei abrupt von überwiegend erfüllbar zu überwiegend unerfüllbar.

Ziel der Arbeit:

Ziel dieser Arbeit ist die systematische Untersuchung von Phasenübergängen in verschiedenen kombinatorischen Optimierungsproblemen. Dabei soll analysiert werden, ob ähnliche Übergangsphänomene auch in anderen Problemklassen auftreten und welche strukturellen Eigenschaften diese beeinflussen.

Mögliche Fragestellungen:

  • Existieren Phasenübergänge in weiteren Problemen wie SAT-Varianten, Clique, Graphfärbung (z. B. 3- Coloring), Max-Cut, Rucksackproblem oder Traveling Salesman Problem (TSP)?
  • Welche Parameter bestimmen das Auftreten solcher Übergänge?
  • Wie groß sind die Instanzklassen, in denen effiziente Lösbarkeit beobachtet werden kann?
  • Lassen sich diese Klassen systematisch erweitern oder charakterisieren?
  • Welche Auswirkungen haben diese Erkenntnisse auf praktische Anwendungen und heuristische Lösungsverfahren?
  • Welche Rolle spielen Phasenübergänge im Kontext aktueller Forschungsfelder wie dem Quantencomputing?

Methodik:

  • Literaturrecherche zu Phasenübergängen in NP-schweren Problemen
  • Theoretische Analyse ausgewählter Problemklassen
  • Experimentelle Untersuchung mittels Simulation zufällig generierter Instanzen
  • (Optional) Implementierung und Vergleich verschiedener Lösungsalgorithmen

Voraussetzungen:

  • Grundkenntnisse in Algorithmen und Komplexitätstheorie
  • Interesse an kombinatorischer Optimierung und theoretischer Informatik
  • Programmiererfahrung (z. B. Python, C++ oder Java) von Vorteil

Kontakt

OTH Regensburg Ansprechpartner: Lukas Schmidbauer E-Mail: lukas.schmidbauer@oth-regensburg.de

MoQel