Ako ťažké je príliš ťažké? Úvod do teórie zložitosti
Ako ťažké je príliš ťažké? Teória zložitosti študuje náročnosť problémov – od usadenia hostí až po kryptografiu. Alan Turing dokázal existenciu nepreukázateľných problémov a otázka P versus NP ponúka milión dolárov za riešenie.
Predstavte si, že organizujete večeru pre sto hostí a musíte ich posadiť tak, aby sa nikto nehádal. Znie to jednoducho, však? Ale čo ak má každý hosť svoje preferencie a nie s každým sa chce baviť? Táto situácia je skvelou ilustráciou teórie zložitosti – oblasti matematiky a informatiky, ktorá sa zaoberá tým, ako ťažké sú rôzne problémy na riešenie. V tomto článku si prejdeme základné koncepty, ktoré Colva Roney-Dougal vysvetľuje v zaujímavej prednáške z Gresham College.
