Podaří se letos průlom v otázce P vs. NP?
Vinay Deolalikar, výzkumník z laboratoří firmy HP v kalifornském Palo Altu, přišel loni s tím, že vyřešil problém P vs. NP, tedy jeden ze šesti nejvýznamnějších matematických problémů současnosti. Je za něj vypsána odměna 1 milion dolarů, má vztah ke kryptografii, spadá do oblasti výpočetní složitosti a hlavně – na rozdíl od ostatních úloh ze […]
Sdílet
Vinay Deolalikar, výzkumník z laboratoří firmy HP v kalifornském Palo Altu, přišel loni s tím, že vyřešil problém P vs. NP, tedy jeden ze šesti nejvýznamnějších matematických problémů současnosti. Je za něj vypsána odměna 1 milion dolarů, má vztah ke kryptografii, spadá do oblasti výpočetní složitosti a hlavně – na rozdíl od ostatních úloh ze šestice dokážeme my laici chápat alespoň to, v čem problém spočívá.
Výsledek dle Deolalikara odpovídá většinovým předpokladům, že oba typy úloh jsou různě výpočetně náročné, P se nerovná NP. Deolalikarovu práci se ovšem loni nepodařilo zkontrolovat, minimálně se ovšem pochybuje o tom, že by byla úplná. Letos bychom v tom mohli mít jasněji.
Komentátoři upozorňují, že v souvislosti s Deolalikarovou prací se utvořila celá komunita nejen profesionálních matematiků a došlo k velké aktivitě na blozích a Wikipedii; skoro jako bychom před sebou měli nový způsob fungování matematiky. Dojde letost opravdu k průlomu?
Podrobnosti Computerworld.cz.
Poznámka: Úloh bylo původně 7, Poincarého domněnka byla ale mezitím dokázána, viz např. článek Podivínský matematik Perelman opět odmítl cenu za důkaz Poincarého domněnky.
Další články z rubriky
Související články
Tagy
nedeterministicky polynomiální · polynomiální
Linkuj
| Jagg
| Delicious
| Facebook
| vybrali.sme.sk
Komentáře
13.01.2011, 22:52 czenek
Nerozhodnutelnost
Vezměme si třeba Lambda kalkulus, je to v podstatě naprosto odlišná koncepce matematiky, naprosto nahrazuje teorii množin a i když je s Cantorovou teorií ekvivalentní, tak může přinášet úplně odlišný pohled na věc. Právě P vs.NP má, díky své "snadné" pochopitelnosti, potenciál aby přilákal matematiky se všemožnými specializacemi a ti vytvořili nové přístupy a nebo modifikovaly stávající. Rozvoj třeba toho lambda kalkulu, který je jako stvořený k řešení obdobných problémů, nebo spojení zdánlivě nespojitelných disciplín můžou přinést vzrušující překvapení. Když to přirovnám k revolucím v klasické matematice - objevení imaginárních čísel, nekonečných veličin, ... Teorie výpočetní složitost je poměrně mladá disciplína a není vyloučeno, že se objeví něco jako "imaginární algoritmus". ad nerozhodnutelnost. Vlastně si moc nedokážu představit, co by v praxi znamenala nerozhodnutelnost. Znamenalo by to asi, že nikdy nikdo nemůže najít P algoritmus pro problém z NP(complete), protože kdyby jej našel, tak je tím problém rozhodnutý. A naopak, když jej nemůžeme najít, tak je tím pádem vlastně rozhodnutelný taky. V praktické algoritmice by se ale asi nic podstatného nezměnilo, a to by byla škoda.
12.01.2011, 23:09 czenek
Doufám, že ne.
Osobně doufám, že se současnou matematikou se to prokázat nepovede. Doufám totiž, že uzraje čas tak tento problém bude působit jako katalizátor nového přístupu k celé problematice. Pokud by se to v blízké budoucnosti povedlo prokázat, tak se obávám, že to nic nového nepřinese. Stejně, žádný matematik nevěří, že se ty třídy rovnají a velká část odborných článků v teorii složitosti stejně už začíná slovy "Předpokládejme, že se P nerovná NP ...". Ovšem naprostá bomba by byla, kdyby výzkum této oblasti prokázal, že se ty třídy rovnají. Něco takového by mělo obrovské následky, ale škoda, že to je jen takový nereálný sen. Ale kdo ví ...
Napsat vlastní komentář
Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.