Digresija: Dedekindovi brojevi

Na koliko načina možemo svakom broju iz skupa S = {1, 2, …, N} pridružiti 0 ili 1? Drugim riječima, koliko ima funkcija iz S u {0, 1}?

Well, that’s easy – dvije mogućnosti za 1, puta dvije mogućnosti za 2, puta dvije mogućnosti za 3, i tako dalje, ukupno $2^N$ .

Idemo dalje: na koliko načina možemo svakom podskupu od S pridružiti 0 ili 1? Drugim riječima, koliko ima funkcija iz skupa svih podskupova – partitivnog skupa P(S) u {0, 1}?

Analogno prethodnome, to je $2^K$ gdje je K broj podskupova, jer za svaki podskup biramo 0 ili 1. A koliki je K? Podskup kreiramo tako da svaki broj u njega stavimo ili ne stavimo (dvije mogućnosti), dakle $K = 2^N$ . Traženih je funkcija, dakle, $2^{2^N}$ .

Idemo dalje…

Na koliko načina možemo svakom podskupu od S pridružiti vrijednost 0 ili 1, ali tako da dodavanjem elemenata u podskup njegova vrijednost može samo porasti? Drugim riječima, koliko ima monotonih funkcija $f : P(S) \to \{0, 1\}$ , što znači da je $f(A)\le f(B)$ za sve $A\subset B$ ?

Nemamo pojma, ali na prvi pogled možemo brutati, tj. napisati program koji ovo prebraja za dovoljno mali N. Što mislite, koliko mali?

Riječ je o N-tom Dedekindovom broju, a ono što je fascinantno je da već za N = 9 nitko nije uspio izračunati taj broj. Postoji formula, ali ona nije zatvorena, tj. sadrži sumaciju pa u suštini i nije formula nego spori pseudokod.

Osmi Dedekindov broj izračunat je još 1991. godine i to uz pomoć pametnih trikova za smanjenje složenosti. Osim u izvornom članku, taj algoritam možete pronaći i ovdje. Iako su se od tada računala ubrzala stotinu i više puta, deveti Dedekindov broj još uvijek je nedohvatljiv. A ima 40ak znamenaka, prava sitnica. Evo vam prilike da se upišete u povijest matematike.

Čini mi se da trenutačno znanje o Dedekindovom problemu nije dovoljno da bi se osmislio dovoljno efikasan algoritam za N = 9, ma koliko ga pametno optimizirali. Potrebna je nova spoznaja o samom problemu, neki novi teorem koji će omogućiti pojednostavljenje formule.

Ok, so what? Ima mnogo neriješenih problema u matematici; zašto sam baš o ovome pisao? Zato što izgleda rješiv (naglasak je na izgleda, a ne na rješiv :)) i zato što, čini mi se, trenutačno ne zanima ozbiljne matematičare pa konkurencija nije jaka. Ako nas dvadeset navali na problem, dovoljno je da svatko izračuna samo dvije ili najviše tri znamenke. Računala će se još ubrzati, a iskustvo nas uči da zadatak s ograničenjem N ≤ 10 ne može biti težak.