Sciencemag.cz
Doporučujeme
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ší
