Ťažké úlohy a problém tisícročia P=NP

RNDr. Jozef Studenovský, CSc.

Ťažké úlohy a problém tisícročia P=NP

Prečo niektoré úlohy sú ťažké, ukážeme na známej úlohe farbenie grafu. Táto úloha má jednoduchú formuláciu. Ľahko nájdeme niekoľko krátkych algoritmov, ktoré ju riešia.

Žiaľ tieto algoritmy sú exponenciálne, t.j. čas výpočtu je exponenciálna funkcia premennej n, kde n je počet vrcholov grafu. Exponenciálne algoritmy sú prakticky nepoužiteľné, lebo čas výpočtu je niekoľko desiatok rokov aj na najrýchlejšom super počítači.

Otázka znie nasledovne: Existuje prakticky použiteľný algoritmus pre úlohu farbenie grafu? Ukážeme, že táto otázka je ekvivalentná jednému problému milénia známemu pod skratkou P = NP.

2.5.2012 o 15:20

poslucháreň P/08
Jesenná 5, Košice



Dátum pridaniaStreda, 21. Marec, 2012 @11:53
Kategórie,
Nálepky,
Prečítané5 496x
Opiner Friends Digg del.icio.us Live Google Technorati Spurl Vybrali.sme.sk Mojelinky.sk Vytlačiť túto stránku Odoslať emailom