Vuonna 1900 matemaatikko David Hilbert julkaisi listan, joka sisälsi 23 avointa matematiikan ongelmaa. Hilbertin ongelmilla on ollut tärkeä vaikutus matematiikan kehitykseen.
Seuraavassa on vastaava lista Putkapostin avoimista ongelmista. Osassa tehtävistä nykyistä ennätystä voisi selvästi parantaa. Osassa tehtävistä nykyinen ennätys saattaa olla jo paras mahdollinen, mutta kukaan ei ole todistanut tätä.
Joululoma voisi olla hyvä hetki tarttua näihin avoimiin ongelmiin. Kerrottehan myös, jos jokin tehtävä puuttuu listasta tai ei kuuluisi siihen.
Tehtävän vaikea osuus on sanaketjun muodostaminen. VilleP:n pitkään säilynyt ennätys 7948 odottaa ylittäjäänsä.
Kukaan ei ole saanut parempaa tulosta kuin 29, mutta kukaan ei ole tiettävästi todistanut, että tulos on paras mahdollinen.
Lyhimmän säännöllisen lausekkeen etsiminen on laskennallisesti vaikea ongelma. Nykyistä ennätystä 139 voi luultavimmin parantaa.
Tällä hetkellä ennätys on 121, joka vastaa 11x11-ruudukkoa. Voisiko lukujen neliöt ahtaa vielä pienempään ruudukkoon?
Kukaan ei ole saanut parempaa tulosta kuin 18, mutta kukaan ei ole tiettävästi todistanut, että tulos on paras mahdollinen.
Mahdollisuuksia kaulaketjun muodostamiseen on valtava määrä. Nykyistä ennätystä 72 voi luultavimmin parantaa.
Tässä tehtävässä riittää vielä todella paljon työmaata. Nykyinen ennätys on 12, vaikka tulos voisi olla jopa 32.
39b: ei ainakaan pitäisi olla mahdollista saada 32, koska md5 takaisinkelauskaan ei tunne salasanaa, joka tuottaisi hashin 31415926535897932384626433832795
Jokotai kirjoitti:
md5 takaisinkelauskaan
... mikä?
Jos jossain yleisesti saatavilla olevassa tietokannassa olisivat kaikki MD5-hashit vastaavine salasanoineen, tuo tehtävä olisi varmaan jo ratkaistu optimaalisesti. Vaan eipä taida sellaista tietokantaa olla?
Eikös MD5 tee tiivisteen annetusta merkkijonosta, joka usein tulostetaan heksadesimaalimuodossa. Ei ilmeisesti ole mitään teknistä rajoitetta, jolla juuri tuo tiiviste rajataan pois joukosta. Tarkemmin on olemassa äärettömän monta merkkijonoa, jotka tuottavat juuri tuon merkkijonon.
Tämä on helppo todistaa. On olemassa aakkosto a, jossa on k kirjainta. Tästä saadaan muodostaa äärettömän pitkiä merkkijonoja. Kirjain saa esiintyä merkkijonossa äärettömän monta kertaa. Tästä seuraa edellinen ehto merkkijono pituudesta. Toisaalta on aakosto b, jossa on j kirjainta tästä muodostetaan tasan 32-merkkinen merkkijono. Sama merkki saa olla siis korkeintaa 32-kertaa. Tämän vuoksi niin sanottu törmäys on mahdollinen.
Oliko oikein todistettu?
Teuro kirjoitti:
Oliko oikein todistettu?
En ymmärtänyt yhtään, mutta sanoisin että ei. Mikään ei suoranaisesti estä, että jokainen (minkä pituinen tahansa) merkkijono kuvautuisi johonkin niistä 2128-1 vähemmän piinkovasta vaihtoehdosta. Vaatisi luultavasti jotain varsin tarkkaa analyysiä MD5:n toiminnasta todistaa, että sillä voidaan tuottaa mikä tahansa 32 heksan merkkijono.
Aihe on jo aika vanha, joten et voi enää vastata siihen.