neprihlásený Sobota, 15. júna 2024, dnes má meniny Vít
Dôkaz P != NP nie je správny, potvrdil autor

Značky: informatikaveda a výskum

DSL.sk, 4.9.2017


Aktuálne najnovší pokus o vyriešenie dôležitého problému teoretickej informatiky P vs NP s potenciálnymi praktickými dopadmi opäť nebol úspešný.

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.


      Zdieľaj na Twitteri



Najnovšie články:

Po vyradení ČT Sportu majú operátori blokovať aj ČT 2
Western Digital ohlásil 256 GB čip flash pamäte
NASA po poškodení pamäte obnovila kompletnú funkčnosť sondy Voyager 1
Slovenská sporiteľňa bude mať opäť veľkú odstávku služieb, netypicky cez deň
Hodnota Raspberry Pi po vstupe na burzu prekročila miliardu
Po ARM notebookoch prichádza aj výkonnejší RISC-V notebook
Podpora predposlednej verzie Windows 10 definitívne skončila
Satelitné dáta ukázali anomálie už 19 dní pred ničivým tureckým zemetrasením
YouTube testuje vkladanie reklám priamo do videí na serveroch
Čoskoro majú prísť lacnejšie SSD pre PCI Express 5.0, demonštrovaný prototyp


Diskusia:
                               
 

Radsej NPN, na PNP sa mi furt daco nepozdavalo.
Odpovedať Známka: 9.4 Hodnotiť:
 

Zo SPSE LH si vela nepamatam, ale mnemotechnicku pomocku:
PNP - "Pod na pivo" a
NPN - "Nemam peniaze, nejdem"
si budem pamatat do smrti :)
Odpovedať Známka: 9.4 Hodnotiť:
 

Mi ostatni, ktorych elektronika bavi, si pamatame, ze "NPN sipka ven"...
Odpovedať Známka: 8.0 Hodnotiť:
 

mi? ozaj?
Odpovedať Známka: 6.3 Hodnotiť:
 

sak mi vsetci, mnozne cislo neeeeee?
Odpovedať Známka: 4.1 Hodnotiť:
 

Koho trápi nejaké y.
Oveľa horšie je, že Fico s Dankom predali národnú doménu.
To ani Maďari Slovákom neurobili.
Odpovedať Známka: 7.9 Hodnotiť:
 

BUSTED! :D

gramatika mu ide ako čítanie jednoduchých schém :D
Odpovedať Známka: 5.0 Hodnotiť:
 

Mi ktorích bavila elektronika a nye kramatyka. :D
Odpovedať Známka: 10.0 Hodnotiť:
 

To je fajn, ale gramatika rodného jazyka Ti nikdy moc nešla, však? :)
Odpovedať Známka: 8.0 Hodnotiť:
 

dokonalosť na svete je ojedinelá... na dsl.sk chodí len jeden pán dokonalý a to je pán maniak. Identita pána maniaka je síce už zahodená, alebo premenovaná na kapitána, ale každopádne to bol krok správnym smerom...
Odpovedať Známka: 3.3 Hodnotiť:
 

NPN sipka ven...
Odpovedať Známka: 10.0 Hodnotiť:
 

Jandasa si pamätáš? :D
Odpovedať Hodnotiť:
 

A ty Strucku ?
Odpovedať Hodnotiť:
 

Pod na pivo, nemam peniaze nejdem... Mnemo pre total dememtov
Odpovedať Známka: 3.3 Hodnotiť:
 

A co tato: Cievka ako dievka, najprv napatie, potom prud ;)
Odpovedať Známka: 3.3 Hodnotiť:
 

Riesenie je jednoduche.
Cursor.Current = Cursors.WaitCursor
Odpovedať Známka: -3.3 Hodnotiť:
 

Jeho autor, 63-ročný TEORETICKÝ INFORMATIK Norbert Blum z Univerzity v Bonne...

Takych "teoretickych" informatickov veru poznam - v kopec uradoch a firmach pracuju.
Odpovedať Známka: -5.0 Hodnotiť:
 

Sorry, mam tam preklep.
Nemalo byt "pracuju", - ale "su zamestnani".
:D
Odpovedať Známka: 5.2 Hodnotiť:
 

Rozdiel je že Norbert Blum je naozaj teoretický informatik, a nie len teoreticky infomatik.
Odpovedať Známka: 10.0 Hodnotiť:
 

S debilkom sa nehadaj, nema to zmysel, obzvlast ked najzlozitejsie k comu pricuchol je fyzika zakladnej skoly
Odpovedať Známka: 3.3 Hodnotiť:
 

http://vixra.org/pdf/1708.0473v1.pdf
Odpovedať Hodnotiť:
 

Proglém je že vydaných dôkazov riešení P=/!=NP je strašné prehrštie, lebo milión amerikorún a sláva, ktoré by riešenie prinieslo, je veľmi lákavá. Problém je že žiaden z nich zatiaľ nebol bezchybný.
Odpovedať Hodnotiť:
 

toto citat v pondelok rano je ina kava.
Odpovedať Známka: 10.0 Hodnotiť:
 

Tiez som z toho zdrteny. Uz som mal nachystanu flasu na oslavu pri potvrdeni teorie a teraz musim cakat kym ju budem moct vychlastat :'(
Odpovedať Známka: 10.0 Hodnotiť:
 

------------ ------------ ------------ ------------
komunita na dsl by sa mala schaporit a poriadne sa do toho obut

zisk by bol: prestiz, melon $ a zrejme aj turingofka
------------ ------------ ------------ ------------
Odpovedať Známka: 8.3 Hodnotiť:
 

Ty to ani neskúšaj, pičus.
Odpovedať Známka: -8.3 Hodnotiť:
 

presne na taketo reakcie som cakal, hlavne od tych s G bodom a G vyvodom
Odpovedať Známka: 5.4 Hodnotiť:
 

To bude asi tým, že si si vedomý toho, aký si pičus.
Odpovedať Známka: -8.5 Hodnotiť:
 

To aj Tebe sa takto rano mamka zdravi ked Ta odprevádza do školky ? Že "Ahoj pičus. Prídem po Teba poobede pičus" ? Nie je to pekné.
Odpovedať Známka: 7.3 Hodnotiť:
 

podla toho ci jej predtym trafil cez vyfuk G..
Odpovedať Známka: 10.0 Hodnotiť:
 

podla toho ci jej predtym trafil cez vyfuk G..
Odpovedať Známka: 3.3 Hodnotiť:
 

Ktovie, kolko ludi tu vobec rozumie tomu, co to znamena zlozitost algoritmov. Ja uz si to tiez nepamatam, ale aspon sa mozem hrdit, ze som to kedysi vedel :D
Odpovedať Známka: 10.0 Hodnotiť:
 

uzavrime to tak, ze vacsina z nas z toho mala skusku a presli sme. a to je hlavne:D
Odpovedať Známka: 10.0 Hodnotiť:
 

Sak pozrem a vidim... P=NP vtedy a len vtedy ked N=1, inak P!=NP. Komu poslat cislo uctu ???
Odpovedať Známka: 10.0 Hodnotiť:
 

No a už si zistil, koľko je N? Transformácia "platí to práve vtedy keď ..." nie je dôkaz, len prenesenie problému inam.
Odpovedať Známka: -10.0 Hodnotiť:
 

Vie mi niekto povedat, aky je rozdiel medzi spojenim "vtedy a len vtedy" a spojenim "len vtedy"? Na matfyze mi to nevedel vysvetlit ziaden profak, a ked som sa ozval, ze naco potom pouzivaju zbytocne slova, tak som bol za kacira. Namiesto inteligentneho vysvetlenia z ich strany, ako by to spravil kazdy slusny clovek.
Odpovedať Hodnotiť:
 

Ked to plati vtedy, nemusi to platit inokedy.
Ale ked to plati vtedy a len vtedy, uz to inokedy platit nemoze.
Odpovedať Hodnotiť:
 

Jj, ale ak to plati "len vtedy", tiez to nemoze platit inokedy a "vtedy a" je tam zbytocne.
Odpovedať Hodnotiť:
 

Nuz pravdepodobne to bude taky matematicky zargon, kde sa kladie doraz na jednoznacnost
Odpovedať Hodnotiť:
 

Stačí sa na to pozrieť a hneď je jasné, že P nemôže byť to isté ako NP. V prvom prípade tam predsa chýba N.
Odpovedať Známka: 8.6 Hodnotiť:
 

Ešte pls dajte čo je P a NP
Odpovedať Známka: 2.0 Hodnotiť:
 

Pismena nasej abecedy, existuju aj mensie verzie a to: "p" a "np"
Odpovedať Známka: 6.0 Hodnotiť:
 

nestem.
zadne p ani np a uz vobec ne !


Odpovedať Hodnotiť:
 

Iným problémom je tzv. problém kontroly, zistenie či sa v priestore nachádza skupina aspoň definovaného počtu uzlov taká, že každý z nich je spojený s každým ostatným z nich. Iným problémom je tzv. problém kontroly kontroly, zistenie či sa v priestore nachádza skupina aspoň definovaného počtu uzlov taká, že každý z nich je spojený s každým ostatným z nich. Iná abstrakcia je tzv. abstrakcia reťazenia. Vzájomné vznikanie, spojenie, je podmienené, nepodmieňovaním zaniká spojenie. Zistenie či sa v abstrakcii nachádza skupina aspoň definovaného počtu podpriestorov taká, že každý z nich je vzájomné vznikanie s každým ostatným z nich, sa prenesene premenná hladinnosť prázdnoty (priestoru) a javiská rozoznávania (abstrakcie či).
Odpovedať Hodnotiť:
 

Daj do priestoru vedla seba dva, tri kable (naprikla od sluchadiel) a zachvilu ti garantujem, ze budu vsetky uzly navzajom spojene
Odpovedať Známka: 6.7 Hodnotiť:

Pridať komentár