P vs NP: laické vysvětlení problému tisíciletí

Poslední 2 dny se horečně mluví o tom, že byl vyřešen problém tisíciletí: P vs NP. Nejen, že je na jeho řešení vypsána odměna milion dolarů, ale jedná se o nejvýznamnější otevřený problém informatiky, jehož řešení může významně ovlivnit naše životy. V tomto videu stručně a jednoduše nastíním, o čem ten problém je a proč je tak zajímavý. Video je vhodné prakticky pro každého.
PS: Aby nedošlo ke zmatení, tak tu raději upřesním jednu věc. Většina algoritmů, které se momentálně používají v kryptografii, není NP-úplná. To znamená, že i kdyby se dokázalo, že P != NP, tak je stále možné, že většina kryptografických algoritmů je efektivně prolomitelná. Nicméně pokud se P = NP, tak jsou všechny kryptografické algoritmy snadno prolomitelné. Ve videu o tom nemluvím explicitně, ale trochu to znělo, jako by tam byla ekvivalence, což není.
PPS: Ve článku Norberta Bluma byla nalezena chyba. Stále se tedy neví, zda se P = NP.

[@jindrichdospiva7459]

Stručné, pochopitelné a hezké.

[@miroslavcizmar9989]

Poručíme vētru, dešti.

[@quosswimblik4489]

If the Sudoku is really hard try cross referencing the possibilities from 2 cells it's a lot more efficient than with 1 or 3 cells.

[@madvorakCZ]

It doesn't improve the worst-case time complexity.