Trotz erheblicher Fortschritte bei der Charakterisierung der hochgradig nichtkonvexen Landschaften von Constraint-Satisfaction-Problemen bleibt die gute Leistung bestimmter Algorithmen bei der Lösung schwieriger kombinatorischer Optimierungsaufgaben schlecht verstanden. Diese Wissenslücke rührt größtenteils von einem Mangel an theoretischen Werkzeugen zur Analyse ihrer nicht im Gleichgewicht befindlichen Dynamik her. Um diese Herausforderung anzugehen, entwickeln wir ein System approximativer Mastergleichungen, das das Verhalten von lokalen Suchalgorithmen in Constraint-Satisfaction-Problemen erfasst. Unser Rahmenwerk zeigt eine ausgezeichnete qualitative Übereinstimmung mit den Phasendiagrammen zweier paradigmatischer Algorithmen: Fokussierte Metropolis-Suche (FMS) und greedy-WalkSAT (G-WalkSAT) für zufälliges 3-SAT. Die Gleichungen bestätigen nicht nur die numerische Beobachtung, dass der algorithmische Schwellenwert von G-WalkSAT nahezu parameterunabhängig ist, sondern sagen auch den Schwellenwert von FMS jenseits des Clusterübergangs erfolgreich vorher. Wir nutzen diese Gleichungen auch in einem Dekimationsschema und zeigen, dass die berechneten Marginalen wertvolle Informationen über die lokale Struktur des vom stochastischen Algorithmen erkundeten Lösungsraums kodieren. Bemerkenswerterweise erreicht unser Dekimationsansatz einen Schwellenwert, der den Clusterübergang übertrifft und konventionelle Methoden wie die durch Belief Propagation geleitete Dekimation übertrifft. Diese Ergebnisse stellen die vorherrschende Annahme in Frage, dass Langstrecken-Korrelationen immer notwendig sind, um effiziente lokale Suchdynamiken zu beschreiben, und öffnen einen Weg zur Entwicklung effizienter Algorithmen zur Lösung kombinatorischer Optimierungsprobleme.
David Machado (Fr,) hat diese Frage untersucht.