Sciencemag.cz
Doporučujeme
90 let starý problém z oblasti geometrie padl díky speciálnímu nasazení algoritmu, který převedl matematickou otázku na problém splnitelnosti.
Kellerova domněnka spadá do kategorie populárních problémů dláždění. Otázka zní, zda rovinu můžeme pokrýt jedním typem dlaždic, aniž by se překrývaly jejich hrany (viz obrázek pro čtverce; jindy se problém formuluje pouze pro čtverce, respektive „hyperkrychle“). Ve 3D se ptáme, zda můžeme prostor vyskládat krychlemi bez toho, aby byly někdy identické jejich stěny. Ve 2D to celkem očividně nelze (i když spoléhejte v matematice na očividnost…), ve 3D také ne. A co ve více dimenzích, tedy s hyperkrychlemi v eukleidovských (nezakřivených) prostorech?
Univerzálně kupodivu domněnka neplatí a prostor vyskládat lze bez překrývání („povrchů“ v n-1 rozměrech). Hádanka je stará 90 let, v roce 1940 byla dokázána pro dimenze až po 6, v roce 1990 bylo naopak překvapivě dokázáno, že pro 10 a více dimenzí neplatí a tyto prostory vyskládat lze. John Mackey z Havajské univerzity v roce 2002 dokázal, že Kellerova domněnka neplatí ani pro dimenze 8 a 9. Zůstával pouze problém se 7 rozměry.
Na řešení problému se nyní soustředil Marijn Heule (University of Texas, Carnegie Mellon University) a podařilo se mu mu uspět pomocí algoritmu, který převádí matematické problémy na problém splnitelnosti (satisfiability, SAT). To je celkem známý informatický problém, nejčastěji se ilustruje na příkladu večírku, kde návštěvníci mají různé libůstky: A nechce sedět vedle B, C musí být mezi D a E, F přijde pouze pokud budou A a B na jednu stranu od něj atd. Řeší se pak úloha z výrokové logiky, někdy se to označuje za problém splnitelnosti logické formule atd.
Problém je ovšem mj. v tom, že i pokud dokážeme matematický problém převést na problém splnitelnosti, lze do provést mnoha způsoby. Splnitelnost je přitom z hlediska výpočetní složitosti NP úplný problém, kde doba potřebná k řešení roste se složitostí vstupu exponenciálně (tedy – to je zase otázka P vs. NP; každopádně neznáme rychlejší než exponenciálně rostoucí algoritmus). Může se proto stát, že odpovídající problém splnitelnosti stejně prostě nedokážeme spočítat hrubou silou. Heule se zabývá právě optimalizací tohoto „překladu“ na problém splnitelnosti a jeho cílem je tento proces i automatizovat. Každopádně ale i s jeho návrhy byl nakonec problém splnitelnosti odpovídající Kellerově domněnce v 7D ještě pořádně složitý. Bylo potřeba prověřit počet kombinací s 324 ciframi. Po dalších optimalizacích (symetrie, zahazování na sobě závisejících kombinací apod.) se ale podařilo problém redukovat na asi miliardu možných konfigurací a na clusteru 40 počítačů pak řešení trvalo jen 30 minut – ovšem jen závěrečné ladění programu pro změnu 4 měsíce.
Závěr zní: v 7 dimenzích Kellerova domněnka platí, prostor za uvedených omezujících podmínek vykládat nelze.
Poprvé byl tento typ důkazu, tj. rozklad problému na určitý počet variant a jejich počítačové ověření, použit zřejmě při řešení problému 4 barev. Mnohé matematiky tento přístup samozřejmě neuspokojuje.
Nyní je ovšem řešení problému plně počítačové. Mnohdy se oba přístupy kombinují, lidsky lze sledovat alespoň část postupu (např. přípravu pro důkaz hrubou silou). Zde to ale nejde, i příslušné symetrie (redukce počtu kombinací) jsou navrženy/řešeny počítačově.
Jak uvádí tisková zpráva Carnegie Mellon University, Marijn Heule již svůj přístup použil i k řešení některých dalších problémů včetně Schurovy věty (věty, nikoliv domněnky, tj. jde o počítačový důkaz problému již vyřešeného jinak). Nyní chce zkusit takto vyřešit Collatzovu domněnku („3n+1 problém“). Ta zní následujícím způsobem: Vezměme libovolné číslo. Pokud je liché, vynásobíme ho 3 a přičteme 1. Pokud je sudé, vydělíme ho 2. Opakujeme. Lothar Collatz r. 1937 navrhl, že nakonec se vždy dostaneme k číslu 1, bez ohledu na to, že v průběhu může průběžná hodnota i z původně malého vstupního čísla vystřelit dost vysoko. Hrubou silou se daří tuto domněnku dokázat pouze po určitou mez (ale dala by se vyvrátit, kdybychom našli cyklus).
Bylo oznámeno několik důkazů Collatzovy domněnky, i v poslední době, ale uznány nebyly, problém je otevřený. Počítá se spíš tím, že domněnka platí. (Zajímavé jsou i související problémy 5n+1, 7n+1 apod. Ale to už jen opravdu na okraj.)
Zdroj: Carnegie Mellon University/Phys.org a další
