autor Continentaleurope, zdroj: Wikipedia, licence obrázku GFDL
autor Continentaleurope, zdroj: Wikipedia, licence obrázku GFDL

Nejdelší matematický důkaz – v podobě 200 TB dat

Booleanský problém pythagorejských trojic se obvykle vysvětluje pomocí „obarvení“. Vezmeme N přirozených čísel. Otázka zní, zda můžeme tuto množinu čísel nějak rozdělit na dvě skupiny („červená“ a „modrá“), a to tak, aby žádná z pythagorejských trojic A na 2 + B na 2 = C na 2 neobsahovala stejně zbarvená čísla.

Pro názornost: Je-li N=5, existuje jediná pythagorejská trojice (3, 4, 5), takže prostě stačí nedat všechna tři tato čísla do stejné skupiny. Zdálo by se, že pro všechna přirozená čísla bude trojic tolik, že je rozřadit prostě nepůjde. Nicméně oněch trojic zase nepřibývá tak rychle…
Problém definoval v 80. letech matematik Ronald Graham a za jeho řešení tehdy nabídl 100 dolarů. Marijn Heule z University of Texas, Oliver Kullmann z Swansea University a Victor Marek z University of Kentucky nyní na preprintovém serveru Arxiv publikovali řešení problému v podobě 20 TB dat textového výstupu, a to už po redukci příslušné datové sady. K řešení byl využit superpočítač a algoritmy speciálně vyvinuté právě pro problém splnitelnosti (satisfiability, SAT) a určité optimalizace speciálně pro tento případ. Splnitelnost logické formule je NP úplný problém, kde náročnost známých algoritmů řešení roste s velikostí vstupu exponenciálně, ale superpočítač chroustal a 800procesorový systém se za 2 dny dopočítal k výsledku.
Výsledek: čísla lze rozdělit na dvě hromady až po 7 824, dále již ne. Bylo třeba i po optimalizacích projít prý asi bilion jednotlivých možných rozdělení.
Samozřejmě otázka zní, můžeme-li takový výsledek považovat za důkaz, nebo alespoň za smysluplný/zajímavý důkaz. O tom, proč je hranice zrovna zde, se z toho nedozvíme nic, co je na čísle 7 825 tak speciálního? Co když je navíc v programu chyba? Na to autoři odpovídají tím, že své výsledky/korektnost původního programu ověřili jiným programem.
Tento typ důkazu hrubou silou („důkazu“?) se používá už od řešení známého problému čtyř barev a samozřejmě vzbuzuje rozpaky, protože samotný člověk ho neověří. To ovšem dnes platí i pro mnohé lidmi generované důkazy, k nimiž dlouho nedokážou zaujmout stanovisko ani ostatní matematici (především v důsledku velké specializace i v rámci oboru)…
Je-li důkaz hrubou silou, neznamená no, že by nemělo smysl hledat důkaz „lidský“. Někteří kritici pak také tvrdí, že problém řešitelný pouze hrubou silou není prostě zajímavý matematický problém.

Zdroj: Phys.org a další

Stěhování ježčích národů – jak se ježek dostal na Krétu

Dnešní evropská fauna a flóra byla výrazně formována dobami ledovými a meziledovými, které se střídaly …

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close