Wer eine zufällige Instanz erzeugen soll, unterliegt mit dem Format immer einer Limitation. Regeln können Zufall nie anreichern, nur eingrenzen. Die Frage ist, wie viel Freiheit danach übrig bleibt — und ob sich in dem, was übrig bleibt, die Härte versteckt.
Ein naiver Generator zieht für jede Instanz eine bestimmte Zahl Bits. Ein grosser Teil davon erzeugt keine gültige Instanz — das Format wirft ihn weg. Ein zweiter Teil erzeugt zwar gültige, aber ununterscheidbare Instanzen: blosse Umbenennung von Variablen und Vorzeichen. Was danach bleibt, ist der Raum, in dem sich der Zufall tatsächlich bewegt.
| Klasse | Rohbits | gültig | Symmetrie | echt frei | Verwurf |
|---|
Der Verwurf liegt bei allen vier Klassen zwischen 44 und 58 Prozent. Rund die Hälfte des Zufallszugs ist keine Freiheit, sondern Formatzwang. Das ist die Limitation, und sie ist eine messbare Grösse.
Gesucht war ein Mass, das zwischen zufällig erzeugten Problemklassen unterscheidet und die Härte trägt. Jeder Kandidat wurde gegen eine Kontrolle gestellt, die ihn kippen kann.
Die beiden Klassen wurden bei verschiedenem m verglichen — 3-SAT bei 256 Klauseln, XORSAT bei 55. Bei gleichem m verschwindet der Kontrast: 11.3 gegen 13.7 Prozent. Der Symmetrieanteil misst die Constraint-Dichte, nicht die Klasse.
Über 13 Klassen gerechnet. Der Gap trennt polynomiell Lösbares nicht von NP-hartem: 3-XORSAT liegt bei 1.089 und damit mitten zwischen 4-SAT und NAE-3-SAT. 4-XORSAT liegt bei 1.024, unter 5-SAT. Das Mass beschreibt Verklumpung, nicht Berechenbarkeit.
Das Mass ist auf |S| und auf die Selektivität des Constraints normiert und braucht keinen Clustering-Algorithmus — es liest die Struktur allein aus der Verträglichkeitsgeometrie ab.
Eichpunkt. NAE-3-SAT hat eine exakte Komplementsymmetrie: mit x ist immer auch ¬x Lösung, und beide töten dieselben Constraints. Die Vorhersage ist deshalb ρ = 0.500 exakt. Gemessen: 0.500.
Reproduzierbar ist sie. Eigenständig nicht: β ist zu 90 Prozent durch die Selektivität eines einzelnen Constraints erklärt (R² = 0.904). Das Mass ist weitgehend eine andere Schreibweise für p_kill.
Und es trennt nicht: 1-in-3-SAT ist NP-hart und liegt bei 0.794, über 2-SAT (polynomiell, 0.740). Dieselbe Klasse hat zuvor schon drei andere Trennungen gekippt.
Sieben Datenpunkte, und die Form des Fits war nachträglich gewählt. Also vorher registriert und an einem sauber gematchten Paar geprüft: Horn-3-SAT hat dieselbe Arität und dieselbe Selektivität wie 3-SAT, ist aber polynomiell lösbar. Wenn das Residuum Traktabilität trägt, muss β(Horn) > β(3-SAT) sein.
Die Vorhersage ist nicht knapp gescheitert, sondern invertiert. Die Residuen-Trennung war ein 1-aus-35-Zufall.
Nahe der Schwelle ist die Lösungsmenge klein genug, dass ein DPLL sie vollständig als disjunkte Teilwürfel ausgeben kann. Daraus lässt sich exakt gleichverteilt ziehen — kein Solver, keine Verzerrung. Gegen Brute Force verifiziert, χ²/df = 1.11.
Was man dann sehen kann: die echten Cluster, definiert als Zusammenhangskomponenten unter Ein-Bit-Sprüngen innerhalb der Lösungsmenge. Unten die beiden Räume, vollständig aufgezählt, auf drei Hauptkomponenten projiziert.
Erklärt ist er trotzdem. Ein Modell, das nur drei Punkte um ein gemeinsames Zentrum streut — auf die gemessene Hamming-Distanz, ohne jede Lösungseigenschaft — trifft die Rate. In zwei von sechs Zeilen exakt, sonst überschätzt es sie sogar. Echte Lösungsmengen sind eher weniger mehrheitsabgeschlossen als unkorrelierte Punkte gleicher Streuung.
Geometrisch sieht das so aus: drei gleichverteilt gezogene Lösungen und ihr Mehrheitspunkt, in der Ebene der ersten beiden Hauptkomponenten.
Der Vergleich war ungleich — exakter Backbone über alle Lösungen gegen probSAT über zwölf. Bei zwölf Stichproben wirkt jede Variable mit schiefer Marginalverteilung eingefroren, unabhängig vom Sampler. Bei gleicher Stichprobenzahl überschätzt gleichverteiltes Ziehen in allen fünf Zeilen stärker als probSAT.
Was von der widerlegten Behauptung übrig bleibt, ist eine Kalibrierung. Der Frozen-Schätzer ist bei kleiner Stichprobe massiv verzerrt, und wie stark, hängt fast vollständig davon ab, wie gross der Backbone tatsächlich ist.
Ein gemessener Frozen-Wert von 0.2 aus zwölf Lösungen ist mit einem wahren Backbone von 0.04 genauso vereinbar wie mit 0.15. In dem Bereich ist der Schätzer fast informationsfrei.
Rund die Hälfte der gezogenen Bits ist Formatzwang, nicht Freiheit. Über vier Klassen zwischen 44 und 58 Prozent. Der Raum, in dem sich der Zufall bewegen darf, ist präzise beziffert.
Die effektive Zahl unabhängiger Lösungen fällt direkt aus der Verträglichkeitsgeometrie, ohne dass man den Lösungsraum durchsuchen müsste. Am bekannten Fall NAE-3-SAT auf drei Stellen geeicht. Das ist ein Instrument, unabhängig davon, dass die Hypothese darüber gescheitert ist.
Mersenne Twister, Kongruenzgenerator und SHA-Stream liefern identische Ensemble-Kennzahlen. Was gemessen wird, gehört dem Format, nicht der Zufallsquelle.
DPLL-Würfelzerlegung, exakt gegen Brute Force geprüft, χ²/df = 1.11. Läuft bis n ≈ 100 nahe der Schwelle und liefert die vollständige Lösungsmenge samt echter Cluster — ohne Solver, ohne Verzerrung. Das ist ein Instrument, unabhängig davon, dass zwei Hypothesen daran gestorben sind.
Bei wahren 0.042 überschätzt man mit acht Lösungen um das Neunfache und liegt selbst mit 1024 noch 20 % daneben. Der Fehler ist ein Stichprobeneffekt und trifft jeden Sampler, nicht nur lokale Suche.
Vier Kandidaten, vier Mal keine Trennung zwischen polynomiell und NP-hart. Was das Encoding erzwingt, ist Selektivität — wie viele Belegungen ein einzelnes Constraint tötet. Berechenbarkeit steckt nicht darin.
Der einzige überlebende Faden vom Vortag: bei unverändertem α deutlich härter, 0 von 12 im Budget. Der Schwellen-Confound ist ungeprüft — dieselbe Kontrolle, die die Vorzeichen-Titration gekippt hat, steht dort noch aus.