Ein kritischer Wert eines Steuerparameters (wie Klauseldichte, Kantenwahrscheinlichkeit oder Zwangsdichte), bei dem eine Familie zufälliger logischer oder kombinatorischer Instanzen ein abruptes Umschlagen im typischen Verhalten zeigt — etwa einen scharfen Wechsel von erfüllbar zu unerfüllbar mit hoher Wahrscheinlichkeit, wenn die Systemgröße gegen unendlich geht.

Prinzip

Phasenübergänge resultieren aus kollektiven kombinatorischen Beschränkungen: Überschreitet ein Steuerparameter eine Schwelle, erfährt der Lösungsraum eine strukturelle Veränderung (Clusterbildung, Kondensation, Verschwinden von Lösungen), die makroskopische Unterschiede in typischen Eigenschaften und algorithmischer Zugänglichkeit bewirkt.

Demonstration

Kanonisches Beispiel: Zufälliges k-SAT weist ein Schwellenverhältnis Klauseln/Variablen r_k auf, sodass Formeln unterhalb von r_k typischerweise erfüllbar und oberhalb typischerweise unerfüllbar sind; empirische und rigorose Resultate identifizieren approximative Werte und zeigen teils scharfe Schwellen in der Grenzbetrachtung vieler Variablen.

Fehlanwendung

Finite Größenschwankungen oder algorithmusabhängige Leistungseinbußen als echte Phasenübergänge zu interpretieren, oder anzunehmen, jedes parametrisierte Ensemble habe einen einzigen scharfen Schwellenwert statt möglicher mehrerer Übergänge oder gradueller Übergänge.

Konsequenz

Die Identifikation von Phasenübergangspunkten leitet durchschnittliche Härteanalysen, sagt algorithmische Regime voraus, in denen Solver versagen oder gelingen, und verbindet kombinatorische Phänomene mit Konzepten der statistischen Physik zur Entwicklung von Heuristiken und Beweisen.

Umkehrung

Statt sich auf den kritischen Parameterwert zu konzentrieren, an dem sich das Verhalten ändert, kann man die subkritischen und superkritischen Regime getrennt untersuchen, um die Geometrie des Lösungsraums und algorithmische Strategien zu klassifizieren statt den einzelnen Übergangspunkt.

Abgrenzung

Phasenübergangspunkte sind relativ zu einem bestimmten Ensemble und einem asymptotischen Regime definiert; sie müssen sich bei kleinen Größen nicht zeigen, können von der Modellspezifikation abhängen und implizieren nicht in jedem logischen Ensemble eine physikähnliche Universalität.

Semantische Spannung

Es besteht Spannung zwischen Analogien aus physikalischen Phasenübergängen (kritische Exponenten, Universaliät) und kombinatorischen Schwellen, die möglicherweise keine kontinuierlichen Parameter oder thermodynamischen Grenzen besitzen; die Begrifflichkeiten überlappen, aber der mathematische Gehalt kann stark abweichen.

Synthese

Ein Phasenübergangspunkt ist der kritische Parameter in einem Ensemble zufälliger logischer Instanzen, bei dem die typische Lösungsstruktur eine qualitative Änderung erfährt; das Verständnis dieses Punktes und der angrenzenden Regime erklärt empirische Härte, lenkt Algorithmendesign und verbindet kombinatorische Phänomene mit der Intuition der statistischen Physik.