  |
Za poslednú hodinu: 127 meraní | ||||
|
inzercia |
|||||
 
neprihlásený 
| Štvrtok, 25. apríla 2024, dnes má meniny Marek |
|
Dôkaz P != NP nie je správny, potvrdil autor
informatika
Jeho autor, 63-ročný teoretický informatik Norbert Blum z Univerzity v Bonne, totiž po zverejnení dôkazu o nerovnosti P a NP v prvej polovici augusta minulý týždeň po niektorých výhradách iných expertov potvrdil, že v jeho dôkaze je chyba a je kvôli tomu zlý. Bližšie vysvetlenie plánuje zverejniť na svojej stránke, bude to podľa neho vyžadovať čas a zatiaľ sa tak ale nestalo. Blumov dôkaz je technicky zložitý, snažil sa ale dokázať že jeden konkrétny NP problém respektíve NP-úplný problém nepatrí medzi P problémy a teda triedy zložitosti P a NP sa nerovnajú. Daným problémom je tzv. problém kliky, zistenie či sa v grafe nachádza skupina aspoň definovaného počtu vrcholov taká, že každý z nich je spojený s každým ostatným z nich. Už niekoľko dní po zverejnení dôkazu sa ale v tejto diskusii objavil sprostredkovaný názor Alexandra Razborova, na teórii ktorého dôkaz stavia, podľa ktorého jedna teoréma z dôkazu odporuje už predtým dokázanej skutočnosti a dôkaz kvôli tomu musí byť chybný. Problém ekvivalencie množín problémov P a NP je jedným z najdôležitejších otvorených problémov informatiky, ktorý by mal v prípade oboch odpovedí dôležité dopady. Do množiny P patria problémy, ktoré sa dajú na klasickom počítači vyriešiť počítačovým algoritmom s tzv. polynomiálnym počtom krokov, tzv. polynomiálnou časovou zložitosťou. Teda zložitosťou rastúcou s veľkosťou vstupu relatívne pomaly, čo znamená v závislosti na konkrétnom vzorci pre počet krokov možnosť problém riešiť efektívne dnešnými počítačmi aj pre veľké vstupy. Na druhej strane sú problémy, ktoré sa dajú vyriešiť len s horšou zložitosťou, dobrým príkladom sú problémy s exponenciálnou zložitosťou. Pri takýchto problémoch sa zložitosť s veľkosťou vstupných dát veľmi rýchlo zvyšuje a klasickými počítačmi takéto problémy pre väčšie riešiť nevieme. Veľa bežných výpočtových problémov je typu NP, čo sú podľa jednej definície problémy, u ktorých vieme dodané konkrétne riešenie overiť v polynomiálnom čase. Definícia nevyžaduje, aby samotné nájdenie riešenia pre daný vstup muselo byť možné uskutočniť tiež v polynomiálnom čase a teoreticky môže byť zložitejšie. A práve u veľa výpočtových problémov vieme, že sa riešenie dá overiť v polynomiálnom čase, ale nevieme, či sa dajú aj rýchlo vyriešiť. Preto vieme, že sú NP problémami, ale nevieme, či sú problémami typu P. Dôležitá otázka informatiky tak znie, či existuje NP problém, ktorý nie je P problémom. Pri známej odpovedi na túto otázku budeme vedieť, či máme šancu s klasickými počítačmi vyriešiť efektívne mnohé problémy alebo na druhej strane potenciálne či je napríklad súčasná kryptografia dostatočne bezpečná. Okrem iného je tak za vyriešenie tohto problému ako jediného informatického problému vypísaná odmena Millenium Prize vo výške jedného milióna dolárov. Množstvo bežných výpočtových problémov sú tzv. NP-úplne problémy. Čo znamená NP-úplný a celkovo sme P vs NP veľmi komplexne a detailne odborne ale zároveň pochopiteľne aj pre čitateľov, ktorí nie sú teoretickými informatikmi, popisovali v tomto článku. Ak by sa ukázalo, že P sa nerovná NP, žiadny z mnohých NP-úplných problémov nemôže byť vypočítateľný na klasickom počítači v polynomiálnom čase. Pre kryptografiu nemá dokázanie P != NP žiadne priame následky, keďže nie je dokázaná NP-úplnosť faktorizácie čísiel a diskrétneho logaritmu. O vyriešenie problému P vs NP sa pokúšali a dôkazy v minulosti predložili už mnohí vedci, vo všetkých boli nakoniec objavené chyby. Vyriešenie P vs NP je stále dôležité aj keď v budúcnosti sa očakáva postupný príchod kvantových počítačov schopných počítať rádovo rýchlejšie ako klasické počítače. Zatiaľ ale nevieme, či bez ohľadu na P vs NP je možné všetky NP problémy na kvantových počítačoch vypočítať v polynomiálnom čase. 
Najnovšie články: Diskusia:
Pridať komentár | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
