Pro malé objevitele
Představ si spoustu vypínačů. Každý může být zapnutý nebo vypnutý. Některé jejich kombinace splňují pravidla hry.
Když vypínačů přibývá, počet kombinací roste ohromně rychle. Vědci předpokládali, že určité těžké hry nejde spočítat dostatečně rychle.
AI našla matematický postup, který u této skupiny her spočítá přesně všechny správné možnosti rychleji, než tato hypotéza dovolovala.
To neznamená, že teď počítač během chvilky zvládne každou těžkou hádanku. Nový postup může být v praxi stále velmi pomalý.
Novinka z 27. října: podobný nápad zveřejnil také jiný tým, Anthropic, jehož AI Claude použila odlišnou matematickou cestu. Dva nezávisle vzniklé nápady jsou zajímavé, ale ještě to neznamená, že je nezávislí vědci oba úplně prověřili.
Jako kdybys místo zkoušení každého klíče objevil matematický způsob, jak spočítat všechny správné klíče bez jednotlivého vyzkoušení každého z nich.
Co přesně se zjistilo?
- Pro každý pevný počet k podmínek v jedné klauzuli algoritmus přesně počítá splňující přiřazení k-CNF formule.
- Hlavní zveřejněný časový odhad je polynomiální faktor krát 2 umocněno O(n log log n / √log n). Pro pevné k je růst subexponenciální.
- Výsledek podle rukopisu vyvrací také #ETH, SETH a některé další související hypotézy.
- Neřeší otázku P versus NP a neimplikuje subexponenciální algoritmus pro všechny problémy třídy NP.
- Dne 27. října 2026 Anthropic zveřejnil samostatný AI vytvořený algoritmus pro 3-SAT i přesné počítání #3-SAT s časem 2^{O(n log log n / √log n)} pro 3-SAT; jde o asymptotický odhad, nikoli o rychlost pro běžné vstupy.
- Anthropic uvádí, že klíčový algoritmus Claude nalezl 16. října 2026 přibližně za 14 milionů výstupních tokenů bez lidských zásahů do hledání jádra řešení; lidé následně pomáhali s prezentací.
- Anthropic zveřejnil Lean 4 formalizaci a samostatně popsaný hlavní výrok ETHIsFalse; projekt uvádí ověřování standardním Lean kernelem a nezávislým kontrolním kernelem nanoda. To není totéž jako nezávislá kontrola významu všech definic a souladu s článkem.
Jak k tomu AI došla?
Logická pravidla se zakódují polynomy, jejichž součet a součin vyjadřují přesný počet řešení.
Pomocné transformace dovolují odděleně vyhodnotit skupiny proměnných při znalosti několika společných měření.
Z výsledků pomocných výpočtů se přes interpolaci rekonstruuje původní počet řešení.
Pro obecné úlohy se používá také rozdělení řídkých formulí, paritní testy a efektivní výpočty s polynomy.
Anthropicova práce využívá kontrakci tenzorových sítí, rozklady operátorů SWAP a odhady hodností; jde o odlišnou konstrukci od polynomiálních a interpolačních metod popsaných v rukopisu OpenAI.
V Anthropicově MainResults.lean jsou cílové výroky formulovány pro Turingovy stroje ve formalizaci Mathlib. Převod na obvyklý model algoritmu a některé standardní úpravy vstupu nejsou součástí strojově ověřených vět, jak dokumentace výslovně uvádí.
Pomáhá to už v praxi?
Nemáme doloženo, že by samotný výsledek již přinesl nové praktické řešení.
Teorie může nasměrovat hledání rychlejších metod pro kombinatorické úlohy.
Z důkazu už matematicky plynou postupy pro přesné počítání určitých obarvení a párování grafů.
Zatím není prokázáno, že by nový algoritmus zrychlil konkrétní podnikový rozvrh či logistiku.
Je objev opravdu ověřený?
Strojově ověřený důkaz, odborná diskuse pokračuje
Aktualizace 28. října 2026: OpenAI oznámila objev 26. října (AI výstup 16. října, Lean 17. října). Dne 27. října Anthropic zveřejnil další, podle autorů nezávisle nalezený algoritmus, rovněž datovaný objevem 16. října. Anthropic poskytl rukopis, README, hlavní Lean tvrzení a formální důkaz; dokumentace uvádí i druhý kontrolní kernel nanoda. Dvě oddělené AI práce posilují důvod k důkladnému zkoumání, nejsou však nezávislým vědeckým potvrzením. Ani jeden výsledek zatím není doložen jako definitivně nezávisle odborně přezkoumaný; navíc je třeba ověřit soulad formalizace se zamýšlenou větou. Impagliazzo, Paturi a Williams výslovně uvedli, že jejich účast na posouzení není certifikací tvrzení. Pro praxi žádné zrychlení zatím prokázáno nebylo.
Co ještě nevíme?
- Potvrdí nezávislí odborníci plný rozsah tvrzení?
- Povede myšlenka k algoritmům, které jsou rychlé i na reálných datech?
- Které další předpokládané výpočetní hranice se budou muset přehodnotit?
- Znamenají dvě odlišné konstrukce skutečně dvě platná vyvrácení ETH, nebo odborná kontrola odhalí omezení či chybu?
- Jsou všechny kroky převodu formálních výroků na běžné algoritmy a jejich asymptotické odhady správné?
Původní zdroje a důkazy
Na tyto veřejné zdroje odkazují důležitá tvrzení v článku. Můžeš si vše přečíst a posoudit sám.