Drei Ebenen der Härte

Kernidee [Rahmen]

Härte wird auf drei Ebenen getrennt betrachtet. Es gibt kein intrinsisches „leicht“ — leichte Probleme sind auf Ebene 1 genauso hart, sie besitzen nur eine Abkürzung.

Trennkriterium zwischen 2 und 3: Die Struktur gilt für alle Instanzen der Klasse — oder nur für einen Anteil.

Schärfungen vom 7. Oktober 2026 [Rahmen]

• P vs NP meint „generell“. Gefragt ist nach irgendeinem polynomiellen Verfahren, idiomatisch oder nicht. Für die Klassenfrage zählt deshalb Ebene 2 mit.
• Ort der Entscheidung. Ebene 1 ist immer vorhanden und für 3-SAT teuer; Ebene 3 trägt per Definition nicht die ganze Klasse. Eine Entscheidung zugunsten von P = NP könnte nur über eine Ebene-2-Struktur für 3-SAT laufen. Der Rahmen sagt also, wo der einzig mögliche Treffer säße — er sagt nicht, ob es ihn gibt.
• Asymmetrie der Feststellbarkeit. Ebene 1 ist trivial feststellbar. Ebene 3 ist im Einzelfall verifizierbar, aber praktisch nicht ausschließbar: Der Raum möglicher Funde ist unbegrenzt, und schon das Finden kleiner Backdoors ist im Allgemeinen schwer.
• Enthalten vs. zugänglich. Jede Ebene-2-Invariante beruht auf Information, die schon in der Instanz steckt, denn die Übersetzung in die neue Darstellung ist eine berechenbare Funktion der Instanz. Ausnutzbar ist sie aber nur, wenn diese Übersetzung billig (polynomiell) ist. Die eigentliche Frage lautet daher: Gibt es eine billig berechenbare, klassenweite Invariante? Das entspricht im Kern dem Polymorphismus-Begriff der CSP-Theorie.

1a · Ergänzungen zum Rahmen (M7–M10) [Rahmen]

• Frege gehört auf Ebene 1, nicht auf Ebene 3. Frege ist vollständig: Für jede unerfüllbare Formel existiert ein Frege-Beweis, wie bei Resolution. Ebene 3 ist die Achse „greift auf manchen Instanzen / greift auf anderen gar nicht“ (z. B. Gauß nur bei affinen Lösungsmengen). Frege sitzt auf der Längen-Achse: Es greift immer, offen ist nur, ob kurz. Frege ist damit das stärkste bekannte Ebene-1-Verfahren; seine offene untere Schranke für zufälliges 3-SAT ist die eigentliche Wand.
• Struktur sehen, die da ist — nicht die, die fehlt. Ein stärkeres Beweissystem kann vorhandene Struktur sehen, die ein schwächeres übersieht (Schubfachprinzip: für Resolution exponentiell, für Frege polynomiell). Es kann aber keine Struktur sehen, die nicht existiert. Offene Lücke: die Übertragung „Instanz ist inkompressibel“ → „jeder Beweis ist lang“ für starke Systeme (für Resolution bewiesen, für Frege nicht). [offen]
• Drei Ebene-1-Größen, die getrennt werden müssen (aus M9):
  (1) Verfahrenskosten auf der ganzen Formel — bezahlen auch Redundanz;
  (2) Kernkosten — Aufwand auf einem minimalen unlösbaren Kern, ohne Redundanz;
  (3) Beweislänge — Minimum über alle Beweise; nur sie betrifft die Wand.
  Die bisherigen Ebene-1-Steigungen (§ 3a) messen Größe (1).
• Zwei Instabilitätsbegriffe. Flip-Empfindlichkeit (Ja/Nein kippt bei einem Bit) haben XOR und 3-SAT gleichermaßen; sie zwingt einen Beweis nur, alle Bits zu lesen. Die feinere Größe ist die Bewegung des Lösungsraums pro Formeländerung und deren Komprimierbarkeit (siehe § 3f). Sie trennt XOR von 3-SAT.

1b · Schärfung vom 8. Oktober 2026 [Rahmen]

Die drei Ebenen, geschärft.

• Ebene 1 (idiomatisch, direkt): vollständiges Ausschlussverfahren — Resolution, DP, bis hinauf zu Frege. Frege gehört auf Ebene 1 (vollständig, Längen-Achse); seine offene untere Schranke für zufälliges 3-SAT ist die Wand.
• Ebene 2 (idiomatisch, Abkürzung): muss aus einer idiomatischen Eigenschaft folgen; bei Constraint-Problemen ist das ein Polymorphismus. Ein Polymorphismus gehört zur Sprache, nicht zur einzelnen Formel — Ebene 2 ist damit per Definition eine Sprach-Eigenschaft. Für 3-SAT ist sie leer (keine Polymorphismen außer Projektionen).
• Ebene 3 (problemfremd): eine Eigenschaft, die nur manche Instanzen tragen und die per Definition nicht aus dem Problem kommt. Beispiele: Backdoors in Horn, 2-SAT oder XOR (sie benutzen den Polymorphismus einer anderen Sprache), Inseln (M5), affine Teilstrukturen (M6).
• Folge: Die Frage „Sprache gegen Instanz“ ist keine Lücke, sondern genau die Grenze zwischen Ebene 2 und Ebene 3. Die Brücke von Atserias–Ochremiak (Sprachebene) sitzt damit auf der richtigen Ebene. „Enthalten vs. zugänglich“ lebt auf Ebene 3: Eine Instanz kann eine fremde Struktur enthalten, ohne dass man sie effizient findet.

Wo der PC-Grad steht. Der PC-Grad über GF(2) wird als Ebene-2-Maß geführt: Er misst, ob eine algebraische Abkürzung beschränkten Grades existiert (Grad bleibt beschränkt, egal wie groß die Instanz wird; weil PC vollständig ist, reicht bei jeder Formel irgendein Grad). [Theorem, Atserias–Ochremiak]: PC über GF(2) ist zugleich ein vollständiges Ebene-1-System, in das das Zählen mod 2 eingebaut ist. Die Charakteristik ist genau die Stelle, an der Ebene-2-Algebra in ein Ebene-1-System einzieht. Ein Gradsprung bei 3-SAT ist deshalb ein negativer Ebene-2-Befund, kein Kostenbefund auf Ebene 1.

Ebene 1 gegen Ebene 2 — der Lückensatz. [Theorem, Atserias–Ochremiak ICALP 2017 / TOCL 2019, Satz 1, Kor. 1] Eine endliche Constraint-Sprache hat entweder Resolutionswiderlegungen konstanter Weite (genau dann, wenn sie beschränkte Weite hat) oder weder subexponentielle beschränkte-Tiefe-Frege-Widerlegungen noch PC über ℝ bzw. SOS sublinearen Grades. Gilt für Sprachen (alle Instanzen), nicht für PC über GF(2). Folge: 2-SAT und Horn sind schon auf Ebene 1 leicht. Den Spalt „Ebene 1 schwer, Ebene 2 leicht“ gibt es nur für Sprachen, deren Abkürzung zählt (lineare Gleichungen, XOR). Die einzige Ebene-2-Abkürzung, die Ebene 1 nicht schon sieht, ist das Zählen.

Zwei getrennte Zutaten der Härte (Ergebnis aus M13–M15b) [Messung]

Nur 3-SAT hat beide Zutaten.

Weiterentwicklung der Zufalls-Erhaltungsthese [Hypothese, mit gemessenen Teilen] — präzisiert die Kurzfassung „2-SAT dämpft im Volumen, XOR in der Form, 3-SAT lässt durch“, ersetzt sie nicht:

• Zwei Zufallsebenen („Zufall im Quadrat“): Der erste Zufall steckt in der Formel (Auswahl von Variablen, Vorzeichen, Beziehungen, Länge). Der zweite ist seine Projektion in den Lösungsraum. Bei XOR fängt die Linearität die Projektion auf (affiner Raum, kurze Beschreibung); Gauß komprimiert die Projektion, nicht die Formel. Bei 3-SAT gibt es keine solche Vorgabe; der Formelzufall dringt in den Lösungsraum durch.
• Inkompressibilität der Instanz ist belanglos, weil XOR- und 3-SAT-Instanzen gleichermaßen inkompressibel sind. Entscheidend ist die Projektion.
• Asymmetrie: Eine 3-SAT-Klausel erlaubt 7 von 8 Mustern (lose Kopplung), eine XOR-Bedingung 4 von 8 (enge Kopplung). [Korrektur] Asymmetrie allein erzeugt keine Härte — Horn hat ebenfalls 7:1 und ist leicht (M13/M15). Entscheidend ist Asymmetrie und fehlende Ordnung.
• Gemessene Fassung (M15b): Härte heißt, jede Operation hat pro Klausel einen kleinen, aber von null verschiedenen Defekt ε; die zufällige Lage der Klauseln macht die Defekte unabhängig, sodass sie sich über linear viele Klauseln multiplizieren: Treue T ≈ ∏(1 − ε_c). Ebene 2 ist genau der Fall ε = 0. Bei 3-SAT ist der beste Fall die Mehrheit mit ε ≈ 0,01 pro Klausel (elementarer Anker ohne Korrelationen: 6/343 ≈ 0,0175).
• Dichte-Fassung: Härte entsteht dort, wo lokal konsistente Teilbelegungen am längsten überleben (Kiesel-Spiel / Resolutionsweite). Bei kleinem n fällt das bei konstanter Dichte schon ab etwa doppelter Schwelle ab; asymptotisch ist die Weite für jede konstante Dichte linear (Ben-Sasson–Wigderson), die Überbestimmung tötet die lokalen Zustände erst bei superlinear vielen Klauseln. [Korrektur] (K9) Ab Ω(n^1,4) Klauseln gibt es kurze TC⁰-Frege-Widerlegungen (Müller–Tzameret), ab c·n^1,5 Polynomialzeit-Widerlegung (Feige–Ofek). Die These gilt daher nur für (fast) lineare Dichte; der Satz „beim zufälligen 3-SAT existiert per Zählargument keine Struktur“ ist in dieser Allgemeinheit nicht haltbar.

Wo die Lücke jetzt sitzt [offen]

• Die Instanz- und Projektionsebene ist gemessen; die Sprachebene ist Theorem (keine Polymorphismen).
• Unbewiesen bleibt der obere Stock der Beweisarchitektur: „Jeder schnelle Algorithmus muss eine idiomatische Regel (Operation mit ε = 0) nutzen.“ Für 3-SAT ist das gleichwertig mit P ≠ NP. Die Messungen zeigen quantitativ, dass 3-SAT-Instanzen keine idiomatische Regel tragen; sie zeigen nicht, dass kein anderer schneller Algorithmus existiert.
• Für Resolution ist der Schritt „Instanz ohne Struktur → jeder Beweis lang“ bewiesen, für PC (Grad) ebenfalls, für Frege offen.

Die zentrale Messfrage und ihre zwei Ausgänge [Rahmen]

Ist die Ebene-1-Härte von 3-SAT und XOR-SAT bei gleichem Gerüst (gleicher Hypergraph, gleiche Dichte) gleich?

Beide Ausgänge sind informativ: Das Programm ortet, es testet nicht auf Ja/Nein. Der gemessene Ausgang steht in § 3a.

Messinstrumente und Stand

a) ebene1_dp.py — Ebene 1, Davis-Putnam-Elimination [Messung]

n = 10–20 (dichtes Gerüst: n = 10–18) · 30–40 Instanzen je Zeile · Zeit-Deckel 30 s

Gemessen je Instanz: benötigte Information (need = n − log₂ #Lösungen), Größe der größten Zwischenklauselmenge (log2 cnf), Resolutionsweite (breiteste erzeugte Klausel) — in zwei Reihenfolgen: idx (streng idiomatisch) und minres (wenigste Resolventen zuerst). Instanzen, die den Zeit-Deckel erreichen, zählen als „gekappt“; ihr cnf-Wert ist dann nur eine untere Schranke, alle anderen Kennzahlen bleiben voll gültig.

Steigung von log₂ cnf je Variable, idx / minres:

• Information: 3-SAT an der Schwelle 0,949 Bit/Variable, XOR 0,929 → lineare Information, exponentieller Aufwand.
• XOR dünn, idx: Rohmediane ergeben ≈ 0,63; nur über ungekappte Instanzen 0,501 — bei n = 20 sind 15 von 40 gekappt (Überlebenden-Verzerrung).
• 3-SAT dicht, idx: Rohmediane ≈ 0,75, passend zum Hauptlauf. Die ausgewiesene ungekappte Steigung 0,525–0,626 ist verzerrt, da bei n = 18 24–27 von 30 gekappt sind.
• XOR dicht: bei α = 4,267 immer unerfüllbar; gemessen wird der Aufwand bis zum Widerspruch. Ab n = 14 sind alle Instanzen gekappt → die Werte sind untere Schranken.
• Resolutionsweite (dicht), n = 10 → 18: 3-SAT idx 7 → 12 (≈ 0,5/Variable), minres 6 → 10 (0,45/Variable); XOR idx 7 → ≥ 10, minres 6 → ≥ 11 (≥ 0,6/Variable; gekappte Werte nur bis zum Abbruch gesehen).
• Nullbefund: Die BDD-Größe der Zwischenprojektionen trennt nichts; sie hängt stark an der Lösungszahl.

Vorbehalte

• Gleiches Gerüst ≠ gleiche Information. Auf dem dünnen Gerüst gewinnt 3-SAT nur 0,19 Bit/Variable gegenüber 0,93 bei XOR; XOR bringt je Hyperkante 4 Klauseln mit. Erst der Dreiklang (eigene Schwelle, XOR-Dichte, OR-Dichte) ist belastbar.
• Die DP-Weite ist eine obere Schranke für die minimale Resolutionsweite. Die bekannten Ω(n)-Schranken werden durch die Daten nicht zertifiziert, nur bestätigt.
• Gemessen ist Resolution, das kanonische idiomatische Verfahren — nicht jedes denkbare.
• n ≤ 20.

b) m5_inseln.py — Inselstruktur der Lösungsmenge [Messung]

n = 8–14

• [ausstehend] Umwegfaktor (kürzeste Weglänge in der Insel / Hamming-Abstand), motiviert durch Gopalan, Kolaitis, Maneva, Papadimitriou (2006). Messung unterhalb der Schwelle (α ≈ 3,8–4,1) geplant, da an der Schwelle zu wenige Lösungen existieren.

c) m6_affin.py — affine Route auf der Lösungsmenge [Messung]

n = 10–20 · 60 Instanzen

Kennzahl fit: Anteil der affinen Hülle der Lösungsmenge, der tatsächlich aus Lösungen besteht (fit = 1: Lösungsmenge ist ein affiner Raum, Gauß greift exakt).

• [offen] Ob der Rest von ≈ 2 % asymptotisch gegen 0 geht, ist bei 3 Fällen nicht entscheidbar.
• [ausstehend] Die Spalte „fast affin“ (fit ≥ 0,5) ist noch nicht in trivial/echt zerlegt.

d) gauss_dp.py — affine Route im Ablauf [Messung]

n = 10–18 · 30 Instanzen

Drei Varianten auf denselben Instanzen: reines DP; DP mit direkt vorliegenden Einheiten und Äquivalenzen („lokal“, isoliert den Effekt bloßer Unit-Propagation); DP mit Erkennung vollständiger Paritätsmuster (bis 6 Variablen) und Gauß-Kombination über GF(2). Als echter Gauß-Beitrag zählt nur, was nicht schon im Spann der Einheiten und Äquivalenzen liegt.

• Grenze: Gemessen ist die Werkzeugklasse „vollständige Paritätsmuster erkennen + Gauß“ (im Kern das Vorgehen von CryptoMiniSat), nicht das weit stärkere Beweissystem Res(⊕), das beliebige lineare Formen in Zwischenschritten erlaubt.

f) m7_bewegung.py — Bewegung des Lösungsraums [Messung]

n = 12–20

Definition: d_j = Zahl der Lösungen, die beim Entfernen von Einheit j hinzukommen (Einheit = Klausel bei 3-SAT, ganze Gleichung bei XOR). Exakt per Brute Force, berechnet als Zahl der Belegungen, die nur Einheit j verletzen. Hauptmaß: dist = Zahl verschiedener Werte von d. Design: XOR auf exakt denselben Variablen-Tripeln wie die 3-SAT-Instanz (gepaart, gleicher Hypergraph); die Instanzen sind bitgleich zu ebene1_dp.py.

• XOR: höchstens 2 verschiedene Bewegungswerte in allen Instanzen. Das ist ein Satz, kein Messglück: Eine Gleichung zu streichen verdoppelt den affinen Lösungsraum oder ändert nichts.
• 3-SAT bei α = 0,918: dist (Median) 10, 13, 15, 17, 18 bei 11, 13, 15, 17, 18 Klauseln (n = 12–20) — fast jede Klausel bewegt den Lösungsraum um einen anderen Betrag. Bei α = 4,267: Median 6 → 9, Maximum 11 → 27.
• Gleiche Lösungszahl (nur unerfüllbare Instanzen vergleichbar): 3-SAT 4, XOR 1 (Median).
• Gepaarte Entropie der Bewegung: H(3-SAT) > H(XOR) in 98–100 % der Seeds.
• Ebene-1-Weite (DP) auf demselben Hypergraphen, dicht, n = 12–20: 3-SAT 7/8/8/9/10, XOR 7/8/9/11/11; XOR-DP ab n = 16 praktisch immer gekappt. Die Bewegung trennt, was Weite und Expansion per Konstruktion nicht trennen können: die Relation auf festem Gerüst.
• Expansion (Ben-Sasson–Wigderson-Größe) ist bei n ≤ ~30 nicht messbar: Jede dichte Instanz enthält im Median 6, 5, 4, 3, 3 identische Variablen-Tripel (n = 12–20), passend zur Erwartung ≈ 3α²/n. Zwei Klauseln auf demselben Tripel haben leeren Rand → Expansion 0.

g) m8_nsgrad.py — Nullstellensatz-Grad über GF(2) [Messung]

n = 14–20 · 120 Instanzen

Klausel → Polynom (Produkt der Falsch-Indikatoren), Widerlegung vom Grad d per inkrementeller Gauß-Elimination über GF(2). Gauß „lebt“ in diesem System: Die vier Klauselpolynome einer XOR-Gleichung summieren sich modulo 2 exakt zur linearen Gleichung. Geprüft: erfüllbare Instanzen werden nie widerlegt, unerfüllbare immer, XOR immer in Grad 3.

• XOR: Grad 3 in allen 960 Instanzen.
• 3-SAT, Verteilung (Grad:Anzahl):

• Gepaart (beide unerfüllbar): Grad 3-SAT > Grad XOR in allen 464 Paaren.
• Innerhalb 3-SAT (nur unerfüllbar, Lösungszahl 0): ρ(dist, Grad) in allen 7 definierten Fällen positiv (+0,05 bis +0,47).
• Grenze: NS ist schwächer als Polynomial Calculus. Hoher NS-Grad beweist keinen hohen PC-Grad; kleiner NS-Grad ist dagegen eine echte Widerlegung.

h) m9_kern.py — Beweis gegen Verfahren: DP auf dem minimalen Kern [Messung]

n = 14–20

Je unerfüllbare 3-SAT-Instanz ein minimaler unlösbarer Kern (MUS, Streichverfahren); DP (minres) auf ganzer Formel und auf dem Kern, NS-Grad auf beiden. Werte: Median.

• Redundanz macht die DP teurer, den Beweis billiger: ρ(frac0, DP-Kosten) ist auf der ganzen Formel 7 von 8 positiv, auf dem Kern 7 von 8 negativ. Ohne Redundanz verhält sich die DP wie der NS-Grad. Auf dem Kern stimmen beide Systeme überein: ρ(NS-Grad, Kern-DP) 8 von 8 positiv (+0,12 bis +0,40).
• Aufblähung = log₂ cnf − log₂(Klauselzahl), also wie viele Klauseln die DP über die Startmenge hinaus erzeugt. 3-SAT-Kern, Median (90-%-Quantil) bei Kern-Variablen 13/15/17/19: α = 4,267: 0,00 (0,07), 0,02 (0,67), 0,08 (0,69), 0,63 (1,69); α = 5,0: 0,00 (0,38), 0,07 (0,87), 0,28 (1,10), 0,51 (1,57). Die Aufblähung setzt zwischen 17 und 19 Kern-Variablen ein. Auf der ganzen Formel beträgt sie bei n = 20 rund 5,5 Bit, auf dem Kern rund 0,6 Bit: Der Großteil war Redundanz.
• XOR-Kerne: Bei gleicher Dichte wie 3-SAT (gepaart) bleibt der Gleichungs-Kern ab n = 16 bei 8 Gleichungen auf etwa 11 Variablen stehen. Grund: XOR liegt dort beim 4,6-Fachen seiner Schwelle und enthält immer kleine Widersprüche. Auch knapp über der eigenen Schwelle (α = 1,0 / 1,1, ungepaart) bleiben die Kerne bei 6–8 Gleichungen, 8–12 Variablen, ohne Aufblähung. Der Vergleich mit 3-SAT ist damit nicht möglich → § 3i.
• Fragilität von Ebene 2: Auf dem Gleichungs-Kern hat XOR immer NS-Grad 3, auf dem Klausel-Kern (einzelne der vier Klauseln wegminimiert) 4–6. Fehlt einer Gleichung eine einzige Klausel, ist die Gauß-Abkürzung weg; für Resolution macht das kaum einen Unterschied.
• Grenzen: Die MUS-Größe hängt stark an der Streichreihenfolge (ρ zwischen zwei Reihenfolgen nur 0,14–0,41); krit ist reihenfolgefrei. Werte bei n = 20 schwanken zwischen Läufen leicht, weil gekappte DP-Läufe ausgeschlossen werden.

i) m10_tseitin.py — XOR ohne Redundanz [Messung]

12–36 Variablen · 60 bzw. 20 Formeln je Größe

Tseitin-Formeln auf zufälligen zusammenhängenden 3-regulären Graphen (Expander) und auf Prismengraphen (schmale Baumweite, Positivkontrolle). Die ganze Formel ist der minimale Kern (per Brute Force bis 21 Variablen geprüft: 1,00; einmal 0,98 bei V = 10, erklärbar durch eine Brücke im Graphen).

• Kontrolle: Ab 24 Variablen laufen Expander und Prisma auseinander. Das Prisma bleibt bei etwa 1 Bit, der Expander wächst stetig. Die Aufblähung misst die Graphstruktur (Expansion), nicht die Relation.
• Vergleich mit den 3-SAT-Kernen aus § 3h bei gleicher Variablenzahl, Median (q90) / Weite:

NS-Grad 3 in allen 420 Tseitin-Formeln (3-SAT-Kerne: 6–7). Kein Lauf gekappt.

j) Zusammenschau M7–M10 [Messung]

M7–M9: n ≤ 20 · M10: bis 36 Variablen

• Ebene 1 (Resolution/DP auf dem Kern, Weite): XOR ≥ 3-SAT; gesteuert von der Expansion.
• Ebene 2 (NS über GF(2)): XOR konstant Grad 3, 3-SAT wachsend.
• Die Bewegungsgröße steht auf der Seite von Ebene 2: ein Klassendetektor für die „kurze Regel“, kein Instanzmaß für Beweisaufwand.
• Innerhalb 3-SAT steuert die Kern-Enge (wenig Redundanz, viele kritische Klauseln) NS-Grad und Kern-DP gleichsinnig.
• Redundanz verfälscht Verfahrenskosten: Wer Ebene-1-Härte messen will, muss sie abziehen.

Grenzen: n ≤ 20 (M7–M9), bis 36 Variablen (M10); DP mit fester minres-Heuristik ist kein kürzester Beweis; Steigungen aus wenigen Punkten.

k) m11_pcgrad.py — PC-Grad über GF(2) auf den M9-Kernen [Messung]

n = 14–20 · tdc3

Konvention: multilinear, Multiplikation x·p nur für Grad(p) < d. Prüfungen sauber: Soundness 464/464, XOR-Gleichungskern 960-mal Grad 3, keine Schrankenverletzung (PC ≤ NS, PC ≤ Kernweite), nichts gekappt.

• 3-SAT-Kerne: PC-Grad fast immer 4 (vereinzelt 3), konstant von n = 14 bis 20, beide Dichten. NS-Grad auf denselben Kernen 6 → 7, Kernweite 5–6 → 7. Abstand NS − PC wächst von 2 auf 3.
• Ganze Formel: Anteil in Grad 3 widerlegbar fällt mit n (α = 4,267: 30/39 → 7/40; α = 5,0: 64/72 → 30/91) — kleine Widersprüche aus Redundanz werden seltener.
• XOR-Klauselkern: PC-Grad 3 in 959 von 960 Fällen (NS dort 3–7).
• Lesart damals: Wachstum in M8 ist eine Eigenschaft des schwachen Systems NS. [Korrektur] (K2) Gilt nur im Messbereich n ≤ 20.

l) m12_grosskern.py + m12pc.cpp — großer Kern, erster PC-Gradsprung [Messung]

Kerne 24–55 Variablen · tdnb1

C++-Kern: DPLL-Streich-MUS, PC-Abschluss mit AVX2. Lauf: seed 11, 60 Instanzen, dmax 4, 3 GB, 1180 Aufgaben, 38,8 Min. Prüfungen: MUS-Zeitüberschreitungen 0; PC-Abbrüche 3 (Speicher, nur n = 56); Soundness 367/367; DP-Weite < PC-Grad: 0 (DP-Weite Median 11); Tseitin 3:100; XOR-Klauselkern 3:679, 4:8. „≥ 5“ heißt: Der vollständige Grad-4-Abschluss enthält die 1 nicht — exakt, kein Zeitabbruch.

Hauptkurve nach Kern-Variablenzahl (beide α zusammen), Anteil ≥ 5 (eingeschränkte Regel):

Je α (n | UNSAT von 60 | Kern-Klauseln/Kern-Var | Anteil ≥ 5):

Tseitin (24/30/36/42/48 Variablen): jeweils 3:20.

Grenzen: Grad 4 bis 5 bei n ≤ 55 sagt nichts über die Beweisgröße (d²/n < 1, [Theorem] Impagliazzo–Pudlák–Sgall). Asymptotisch wächst der PC-Grad über GF(2) linear ([Theorem] Alekhnovich–Razborov 2003); M12 zeigt vermutlich den Beginn; Ort des Sprungs und Dichteunabhängigkeit deckt kein Satz.

m) m12b_konvention.py — volle Multiplikationsregel als Gegenprobe [Messung]

tdnb1 · seed 11, 60 Instanzen, ns 36–52, 630 Aufgaben, 119,5 Min.

Frage: Ist der Sprung ein Artefakt der Konvention? eingeschränkt (M11/M12): x·p nur für Grad(p) < d — entspricht dem formalen Standardgrad. voll: x·p auch bei Grad(p) = d, wenn x in jedem Monom höchsten Grades von p vorkommt (multilinear mit Variablenregel); weicht vom formalen Grad höchstens um 1 nach unten ab. (Die semantisch noch stärkere Regel „mal beliebiges Polynom im Quotientenring“ wird nicht verwendet.) Validierung: exakt gleich zu einer unabhängigen Python-Referenz auf 48 kleinen Kernen; 57 erfüllbare Formeln nie widerlegt. Prüfungen: Abbrüche eing/voll 0/4; „voll > eing“ 0; Soundness volle Regel 614/614; XOR-Klauselkern eing 3:379 4:6 → voll 3:382 4:3; Tseitin 3:30 → 3:30.

Gesamt: von 232 Kernen „≥ 5“ bleiben 182 auch voll „≥ 5“ (78 %); die volle Regel hat in 226 dieser Kerne zusätzliche Zeilen erzeugt (Regel greift, reicht aber nicht). Kein Grad-4-Kern fällt auf 3.

n) m13_durchlass.py — BDD-Komprimierbarkeit des Lösungsraums [Messung]

n = 12–28 · tdnb1 · seed 13, 60 Instanzen, 12 960 Aufgaben, 8,8 Min.

Maß: exaktes reduziertes BDD der ganzen Lösungsmenge (Minimum über 6 Variablenordnungen) geteilt durch das BDD einer echt zufälligen Menge gleicher Größe („Quote“; 1 = so ungeordnet wie Zufall). Typen: 3sat (7 von 8 Mustern erlaubt), rel6/rel5/rel4 (6/5/4 erlaubt, verbotene Muster zufällig), xor3 (4 erlaubt, affin), sat2, später horn3 (7 erlaubt, geordnet, gleiche Klauselzahl wie 3sat). Dichten 0,3–0,9 der eigenen Schwelle (rel-Schwellen geschätzt). Selbsttest gegen Vollaufzählung fehlerfrei. Quote bei festem Raumanteil log₂S/n ∈ [0,5; 0,7), Median:

Bei [0,3; 0,5): 3sat 0,419/0,258/0,173/0,109/0,071; xor3 0,412/0,167/0,103/0,051/0,026 (Verhältnis 1,0 → 2,7).

• Ordnung 7 > 6 > 5 > 4 erlaubt streng monoton; Abstand 3-SAT zu allen anderen wächst mit n (3sat/xor3 bei [0,5; 0,7): 1,7 → 15,5).
• [Korrektur] Störgröße: Eine 3-SAT-Klausel schneidet 0,19 Bit, eine rel4/XOR-Bedingung 1 Bit; für gleiches Volumen braucht 3-SAT etwa fünfmal so viele zufällige Klauseln (n = 24: 72 gegen 13).
• [Korrektur] Horn liegt praktisch auf 3-SAT (Abweichung wenige Prozent in jeder Zeile), obwohl Horn trivial lösbar ist. Die BDD-Quote misst Asymmetrie und Klauselzahl, nicht Härte.
• [Korrektur] XOR liegt über rel4: Das BDD sieht Gauß nicht (ein affiner Raum ist für ein BDD oft teuer, für eine Vektorbasis winzig). BDD-Komprimierbarkeit ist eine bestimmte Beschreibungssprache, nicht Komprimierbarkeit überhaupt.
• Auch bei 3-SAT fällt die Quote mit n: Die starke Fassung („Lösungsraum so zufällig wie Zufall“) hält nicht.
• Schluss: Die Komprimierbarkeit, die über leicht/schwer entscheidet, ist nicht die allgemeine Beschreibungslänge, sondern die idiomatische (Abgeschlossenheit unter einer Operation) → § 3p.
• Der DP-Block von M13 (Davis–Putnam auf unlösbaren Instanzen bei Faktor 1,5, n bis 20) lief nur teilweise (viele Zeitabbrüche bei n = 20) und wird nicht berichtet.

o) m14_dichte.py — Dichte-Sweep [Messung]

tdnb1 · seed 14, 60 Instanzen, 17 280 Aufgaben · Kiesel n = 10–16 (kmax 5, ältere Dateiversion); Nachlauf „m14k“: n = 16/20/24, kmax 6

Zwei Maße: DPLL-Knoten (Unit-Propagation, keine Lernklauseln; lösbar und unlösbar) und Kiesel-Zahl k*: kleinstes k, bei dem starke k-Konsistenz die leere Belegung entfernt (Spoiler gewinnt das existenzielle k-Kiesel-Spiel; entspricht nach Atserias–Dalmau der Resolutionsweite). Dichte 0,5–8 der eigenen Schwelle. Selbsttest fehlerfrei. DPLL-Knoten 3-SAT (Median):

XOR: Spitze flacher (n = 50: Faktor 1,15 → 15 Knoten); rel5: Spitze knapp unter der geschätzten Schwelle (n = 50: 20 Knoten bei 0,7–0,85). Kiesel-Zahl k* (unlösbare Instanzen, Median):

• 3-SAT: n ≤ 16: 4 bei Faktor 0,85–1,15, ab 1,3 durchweg 3. Nachlauf: Faktor 1,3 bei n = 16/20/24: 4/4/4; Faktor 1,6: 3/3/4; Faktor 2,0: 3/3/3.
• XOR: 4 von Faktor 1,0 bis 2,0 (n = 16/20/24 durchweg 4), ab 3,0 dann 3.
• rel5: überall 3, auch an der Schwelle. k* > 4 kam nie vor.

Grenzen: k* hat bei n ≤ 24 nur die Stufen 3 und 4; „hohe Dichte“ ist hier hohe Dichte in α, nicht das Regime n^1,4.

p) m15_abschluss.py — Abgeschlossenheit des Lösungsraums [Messung]

n = 12–28 · tdnb1 · seed 15, 60 Instanzen, Faktoren 0,3–0,9, 7200 Aufgaben, 0,6 Min.

Je lösbare Instanz gleichverteilt Lösungen ziehen (exakt aus dem BDD) und bitweise UND, ODER, Mehrheit, Minderheit (x⊕y⊕z) anwenden; Treue = Anteil, mit dem das Ergebnis wieder Lösung ist (nur verschiedene, nicht-triviale Tupel). Basis: Zufallsmenge gleicher Größe (praktisch 0). Selbsttest: Ziehen exakt und gleichverteilt; Polymorphismus-Kontrollen = 1. Anteil Instanzen mit exakt geschlossener Operation:

Beste Treue je Instanz (Median): 3sat 0,710/0,720/0,649/0,604/0,569 (n = 12/16/20/24/28); horn3, sat2, xor3 durchweg 1,000; rel5 0,887 → 0,761; rel4 1,000 → 0,888. 3-SAT bei Raumanteil [0,5; 0,7): UND 0,306 → 0,155, ODER 0,339 → 0,128, Mehrheit 0,648 → 0,516, Minderheit 0,118 → 0,007 (n = 12 → 28).

q) m15b_defekt.py — Defekt pro Klausel [Messung]

n = 12–28 · Sandbox von Claude, 1 Kern · seed 15, 20 Instanzen, Faktoren 0,3–0,9, 4487 Messzeilen · Skript noch nicht abgelegt

Je Instanz und Operation: ε_c = Anteil der Tupel, deren Ergebnis Klausel c verletzt; Vorhersage bei unabhängigen Defekten T_pred = ∏(1 − ε_c). Typen 3sat, rel5, horn3. 3-SAT, Mehrheit:

Kontrollen: horn3 UND: ε = 0 in jeder Klausel, T = 1 für alle n. horn3 Mehrheit: ε ≈ 0,0033 konstant, T 0,915 → 0,800, T/Vorhersage 1,01. rel5 Mehrheit: ε ≈ 0,006, T/Vorhersage 1,00. Bei UND/ODER/Minderheit auf 3-SAT liegt T/Vorhersage bei 1,2–2,1 (Defekte häufen sich auf denselben Tupeln).

• Für die Mehrheit gilt das Produktmodell fast exakt: Die Defekte sind unabhängig.
• ε ist ab n = 16 konstant ≈ 0,01; mit m ≈ α·n folgt T ≈ e^−0,01·m, an der Schwelle Halbierung etwa alle 16 Variablen. [Extrapolation, nicht gemessen] Bei n = 100 etwa 1 %.
• Elementarer Anker: Wären die drei Lösungen an einer Klausel unabhängig gleichverteilt über die 7 erlaubten Muster, verletzt die Mehrheit sie mit Wahrscheinlichkeit 6/343 ≈ 0,0175 (genau dann, wenn die drei Eingaben die drei Muster mit je einem wahren Literal sind). Gemessen 0,010–0,015, weil echte Lösungen korreliert sind.
• Nicht klein-oder-groß entscheidet, sondern ob irgendeine Operation ε = 0 hat (Horn hat unter Mehrheit ebenfalls ε > 0, unter UND aber 0).
• Grenze: Zeigt quantitativ, dass 3-SAT-Instanzen keine idiomatische Regel tragen; zeigt nicht, dass kein anderer schneller Algorithmus existiert (§ 1b).

r) Zusammenschau M11–M15b [Messung]

Zusammenschau der affinen Route [Messung]

n ≤ 20

Einordnung in die Literatur

Die Dreiteilung als zusammenhängende Einordnung ist in dieser Form nicht als bekannt belegt; jede Ebene hat aber ein etabliertes Forschungsgebiet.

Die Prüfstufen [V]/[A]/[S]/[N] und der Volltext zum Literaturstand (beweisgeruest.md, beweisgeruest.bib, luecken.md) liegen noch nicht im Repo; die Unterseite „Beweisgerüst / Literaturstand“ ist deshalb [ausstehend]. Die Quellen oben stammen aus dem Auftrag vom 8. Oktober und sind hier nicht einzeln geprüft.

Nach Schaefer besitzt 3-SAT als Sprache keine der Abschlusseigenschaften, die eine Ebene-2-Abkürzung im algebraischen Sinn liefern. Offen ist allein, ob es jenseits davon eine klassenweite Abkürzung gibt — das ist P vs NP selbst. [offen]

Offene Punkte

• [ausstehend] Umwegfaktor als M5-Spalte, unterhalb der Schwelle (α ≈ 3,8–4,1) gemessen.
• [ausstehend] Zerlegung von „fast affin“ (fit ≥ 0,5) in triviale und echte Fälle.
• [ausstehend] indep für XOR pro Gleichung statt pro Klausel zählen — eine saubere Synergie-Kennzahl.
• [ausstehend] Größere Stichproben (M6 mit 200 Instanzen) und längerer Zeit-Deckel (60 s) für n = 18–20.
• [ausstehend] Weitere algebraische Routen neben der affinen.
• [offen] Rest von ≈ 2 % echt affiner 3-SAT-Instanzen: Grenzwert 0 oder positiv?
• [ausstehend] Kopplung Bewegung ↔ DP-Kosten bei erfüllbaren Instanzen erklären (§ 3f).
• [ausstehend] Kern-Enge reihenfolgefrei messen (krit statt MUS-Größe) und gegen NS-Grad prüfen.
• [ausstehend] Polynomial-Calculus-Grad statt NS-Grad; Literaturstand zu PC-Gradschranken für zufälliges 3-CNF prüfen, bevor darüber etwas behauptet wird.
• [ausstehend] 3-SAT-Kerne mit mehr als 21 Variablen (braucht MUS-Extraktion ohne Brute Force), um den Tseitin-Vergleich bis 36 Variablen fortzusetzen.
• [ausstehend] DP-Vergleich zusätzlich in idx-Reihenfolge (streng idiomatisch).
• [offen] Übertragung „Instanz ist inkompressibel“ → „jeder Beweis ist lang“ auf starke Systeme (Frege), siehe § 1a.
• [offen] Ausgang „gleich“ in § 3a: Ob 3-SAT eine Abkürzung jenseits der gemessenen Routen hat, bleibt davon unberührt.
• [offen] Der obere Stock: „schnell erzwingt idiomatisch“ (§ 1b) — gleichwertig mit P ≠ NP für 3-SAT.
• [offen] Frege, beschränkte-Tiefe-Frege, DAG-Res(⊕) auf zufälligem 3-CNF linearer Dichte.
• [ausstehend] M15b auf dem Server mit 60 Instanzen und n bis 36; ε direkt aus dem Lösungsraum gegen 6/343 und gegen die Korrelation der Lösungen erklären.
• [ausstehend] Kiesel-Zahl bei n = 28/32 (erwartet: k* = 5 zuerst an der Schwelle).
• [ausstehend] PC-Grad 5 exakt auf großen Kernen (--dmax 5, wenige Jobs, großes --mem); Laufzeit getrennt nach 4 vs. ≥ 5; Lage der XOR-Vierer nach n.
• [ausstehend] Erneuter M12-Lauf mit aktuellem m12_grosskern.py (Expansionsblock: Expansion gegen 4/≥ 5).
• [ausstehend] M13-DP-Block mit längerem Zeitdeckel oder ohne n = 20.
• [ausstehend] Unterseite „Beweisgerüst / Literaturstand“ und Downloads m15b_defekt.py, ref_voll.py: Dateien liegen nicht im Repo, nachliefern.
• Erledigt durch M11: „Polynomial-Calculus-Grad statt NS-Grad“ (Punkt oben). Die älteren Punkte bleiben gültig.

Korrekturen [Korrektur]

Frühere Fassungen werden nicht still überschrieben. Was sich gegenüber dem Stand vom 6. Oktober 2026 geändert hat: