Autor dôkazu P != NP tvrdí, že ho opravil

DSL.sk, 30.8.2010

Vinay Deolalikar, ktorý na začiatku augusta oznámil odbornej verejnosti dokázanie nerovnosti tried zložitosti P a NP, oznámil opravenie všetkých problémov identifikovaných v pôvodnej verzii dôkazu.

"Opravil som všetky problémy identifikované v predbežnej verzii v novej revidovanej 126-stranovej verzii, vyjasnil niektoré koncepty a vytvoril jednoduchšie dôkazy niektorých tvrdení," uvádza Deolalikar na svojej stránke.

39-ročný Deolalikar pracujúci pre výskumné laboratóriá spoločnosti HP v Palo Alto na začiatku augusta rozoslal 103-stranovú verziu dôkazu, že triedy zložitosti P a NP sa nerovnajú. V predchádzajúcich týždňoch bolo v dôkaze objavených viacero problémov, z ktorých sa minimálne jeden javí ako závažný, a viacero odborníkov sa vyjadrovalo k celkovej správnosti dôkazu zatiaľ skepticky.

Revidovanú verziu Deolalikar už rozoslal viacerým odborníkom. Zatiaľ nie je známe, či aj v nej boli objavené nejaké prípadné problémy.

Problém porovnania tried zložitosti P a NP je jedným z najzávažnejších problémov teoretickej informatiky s vážnymi dopadmi aj na reálne aplikácie. Jeho cieľom je, zjednodušene, odpovedať na otázku či je na klasických počítačoch možné dostatočne rýchlo, v tzv. polynomiálnom čase, vypočítať všetky problémy, pre ktoré je možné rýchlo na klasických počítačoch overiť správnosť riešenia.

Pre prvého úspešného autora dôkazu vzťahu medzi triedami P a NP je vypísaná ako pre jediný problém z informatiky odmena Millennium Prize vo výške jedného milióna dolárov.

Čo problém porovnania tried zložitosti P a NP znamená a aké by boli dôsledky rovnosti P a NP a skôr predpokladanej nerovnosti P a NP sme detailne vysvetlili v tomto článku.


Najnovšie články:



Diskusia:

viacery to vedeli uz davno... Od: tnt | Pridané: 30.8.2010 11:01 ako vo futurame tak aj v simpsonovcoch vedeli ze p!=np, vid carodejnicky diel v 7. serii, dokaz: cut.sk/8e7 Odpovedať Známka: 7.3 Hodnotiť:

Re: viacery to vedeli uz davno... Od: tnt | Pridané: 30.8.2010 11:03 sory viacerI ... :) Odpovedať Známka: 6.0 Hodnotiť:

Re: viacery to vedeli uz davno... Od: jjdasfj | Pridané: 30.8.2010 11:13 Tam je ze p=np Odpovedať Známka: 10.0 Hodnotiť:

Re: viacery to vedeli uz davno... Od: rms_ | Pridané: 30.8.2010 12:30 To nie je zo Sipsonovcov. To je nejaka trapna 3D neviemco. Odpovedať Známka: -9.0 Hodnotiť:

Re: viacery to vedeli uz davno... Od: ___ | Pridané: 30.8.2010 13:35 ale je Odpovedať Známka: 10.0 Hodnotiť:

Re: viacery to vedeli uz davno... Od: eeeeeeb | Pridané: 1.9.2010 11:26 su to simpsonovci, vola sa to Homer 3-D... Odpovedať Hodnotiť:

Re: Autor dôkazu P != PN tvrdí, že ho opravil Od: Jondy | Pridané: 30.8.2010 11:15 Vzhledem k tomu, ze uz nejakou dobu leti povyk okolo tohohle dukazu tak si dovolim trochu osvety. Zda P != NP nebo ne je dulezity problem informatiky, ale ne tak zasadni. Zasadnejsi problem je, ze neni mozne dokazat, ze problem pro ktery zname pouze NP reseni neexistuje lepsi reseni. Nemoznost dukazu vychazi z principu matematiky (pokud by se takovy matematicky spravny dukaz objevil, tak je cela matematika spatne). Z toho vyplyva ze P != NP se tak nejak predpokladalo, akorat nebylo dokazano. Dusledek toho, ze se to dokaze, je IMHO zajimavy jen pro teoreticke informatiky. Pokud by se objevil dukaz ze P = NP, tak by byla otazka, kde je v matematice chyba, zda v zakladech nebo v definici algoritmu. Jak uz bylo uvedeno prava bomba by byla pokud by nekdo dokazal, ze konkretni NP problem (a tim vlastne vsechny NP) nema lepsi reseni nez NP. Milenium prize taky neni na dukaz zda P != NP, ale na dukaz, ze neexistuje lepsi nez NP reseni konretniho problemu. Odpovedať Známka: -5.0 Hodnotiť:

Re: Autor dôkazu P != PN tvrdí, že ho opravil Od reg.: Redakcia DSL.sk | Pridané: 30.8.2010 11:27 Máte tam viacero nepresností a nepravdivých informácií, na začiatok odporúčame prečítať napríklad http://www.dsl.sk/article.php?article=9589 Špeciálne odporúčame naštudovať termín NP-úplný. Odpovedať Známka: 8.0 Hodnotiť:

Meredit spravil chybu? Od: MMMman | Pridané: 30.8.2010 11:18 Meredit spravil chybu? No to sú mi veci :-D Odpovedať Známka: 10.0 Hodnotiť:

P != PN Od: paapi | Pridané: 30.8.2010 13:02 PN akoze prace neschopny ? :) Redakcia by mohla opravit nadpis, takto to vyzera dost divne. Odpovedať Známka: 5.7 Hodnotiť:

Re: P != PN Od reg.: Pjetro de | Pridané: 30.8.2010 20:49 no co, P faktorial je Prace Neschopne co je na tom nejasne? Odpovedať Známka: 10.0 Hodnotiť:

som to Od: kolohnath | Pridané: 31.8.2010 13:15 som to prave prekontroloval a zas tam ma chybu! to je nejaky laik...co strasne tuzi po odmene ale fusuje do coho nerozumie Odpovedať Známka: 10.0 Hodnotiť:

Pridať komentár