neprihlásený Pondelok, 2. decembra 2024, dnes má meniny Bibiána
Ďalší pokus o vyriešenie P vs NP, zverejnený dôkaz P != NP

Značky: informatikaveda a výskum

DSL.sk, 17.8.2017


Aktuálne sa objavil ďalší pokus o vyriešenie problému P vs NP, o ktoré sa pokúsil nemecký 63-ročný teoretický informatik Norbert Blum z Univerzity v Bonne.

Blum konkrétne zverejnil dôkaz, že P sa nerovná NP.

Dôkaz je technicky zložitý, dokazuje ale ž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.

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 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 ako tvrdí aktuálne Blum 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ž viacerí vedci, vo všetkých boli nakoniec objavené chyby. Blum svoj dôkaz zverejnil na konci minulého týždňa a zatiaľ nie je jasné, či v ňom už boli prípadne objavené nejaké problémy.

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:

CEO Intelu odstúpil
mBank spustila podporu okamžitých platieb, zatiaľ ich iba prijíma
Sprístupnená testovacia verzia LibreOffice 25.2, začína ukončovať podporu Windows 7
Platené DVB-T zvýši od nového roka cenu
Oficiálne uvedený prvý WiFi router od OpenWrt
Raketa Falcon 9 dosiahla 400 úspešných štartov
Facebook vybuduje vlastný podmorský kábel okolo celého sveta
Trh s humanoidnými robotmi má v najbližších rokoch výrazne rásť
Telekom má dnes 100 GB balík pre všetkých zákazníkov predplatených kariet
Priemerná cena smartfónov rastie a má ďalej rásť


Diskusia:
                               
 

Esteze vymysleli cisla a pocitanie, ibak by sa vedci nudili a chatovali cele dni na pokeci...
Odpovedať Známka: -4.3 Hodnotiť:
 

cs.wikipedia.org/wiki/Klika_(teorie_graf%C5%AF)
Odpovedať Známka: 10.0 Hodnotiť:
 

nenudim sa, mam dsl.sk
Odpovedať Známka: 10.0 Hodnotiť:
 

moze mi niekto objasnit?
"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."

riesenim takeho problemu, ak tomu dobre rozumiem je "true" ak existuje taka skupina, alebo "false" ak neexistuje. ak tomu rozumiem dobre.
ak je nemozne zistit odpoved v polynomynalnom case, tak ani overit riesenie.
ak by totiz overenie riesenia bolo mozne v polynomynalnom case, tak najdenie riesenia tiez, kedze by stacilo iba v polynomynalnom case overit vysledok true a tiez v polynomynalnom case overit vysledok false.

predpokladam, ze tento problem vznikol nedostatocnym vysvetlenim problemu. tipujem, ze problem nie je zistenie, ci sa nachadza v grafe taka skupina vrcholov, ale najdenie takej skupiny vrcholov. problem nepoznam, citam o nom prvy krat tu na dsl.sk, tak sa pytam pre istotu na objasnenie.
Odpovedať Známka: -2.5 Hodnotiť:
 

Pičovina, to, že na zistenie existencie tej situácie je potrebné nájsť tie vrcholy, si si vymyslel. Teoreticky tak ten algoritmus nemusí fungovať a teoreticky to nie je potrebné ani na overenie výsledku. Ani všetky dôkazy sa neoverujú hľadaním konkrétneho výskytu, stačí overiť správnosť postupu.
Odpovedať Známka: 4.3 Hodnotiť:
 

je mi jasne, ze na zistenie ich existencie, nemusi byt nevyhnutne potrebne najst vrcholy.
ode o to ze
1. riesenie problemu udajne nie je mozne najst v polynomynalnom case
2. overenie riesenia ano
teda P != NP

lenze ak budes hladat riesenie tak, ze overenis pre true a overenis pre false a overenie je mozne v polynomynalnom case, tak si prave nasiel riesenie v polynomynalnom case.
Odpovedať Známka: -10.0 Hodnotiť:
 

v tvojom dokaze je problem to udajne
Odpovedať Známka: 10.0 Hodnotiť:
 

to "udajne", lebo to beriem z clanku. "...dokazuje ale že jeden konkrétny NP problém respektíve NP-úplný problém nepatrí medzi P problémy..."
beriem ich za slovo a predpokladam teda, ze problem sa neda riesit v plynomynalnom case. avsak kedze je to NP, tak overit riesenie sa da v polynomynalnom case.
Odpovedať Hodnotiť:
 

udajne je ale problem preto, lebo ak dôkaz P != NP je z NP, postupnymi krokmi je k nemu dojst nemozne a ak nie, po jednom neuspesnom pokuse sa nan eventualnym pokracovanim implicitne meni.
Odpovedať Známka: -5.0 Hodnotiť:
 

http://tinyurl.com/yc5vft2h
Odpovedať Hodnotiť:
 

"...and find any such clique that it contains..."
cize sa nejedna iba o zistenie, ci take vrcholy existuju, ale aj o ich najdenie.
Odpovedať Známka: 6.0 Hodnotiť:
 

Jednoducho povedané, rozdiel je zhruba ten, že v prvom prípade ti dám graf a ty mi máš ukázať, že aha, táto konkrétna množina bodov je klika. To zrejme v polynomiálnom čase nejde. Druhý prípad je, že ti dám graf a množinu bodov a povedz mi, či to je alebo nie je klika. To sa už polynomiálne dá.

Obdobne: je ťažké faktorizovať číslo na prvodelitele, a ľahké je zistiť, či nejaké delitele spolu dávajú pôvodné číslo.
Odpovedať Známka: 8.2 Hodnotiť:
 

cize, ulohou je najst body, ktore tvoria kliku? lebo z clanku vysvetlenia v clanku vyplyva, ze ulohou je iba zistit, ci v grafe existuje klika. a tuto dilemu sa tak neuspesne snazim odkomunikovat.
Odpovedať Známka: -3.3 Hodnotiť:
 

Ono sa to dá formulovať kadejako -- nájsť všetky najväčšie kliky, všetky kliky aspoň rádu n, všetky nezväčšiteľné... ale tuším, že všetky formulácie sú NP-kompletné.

A teda nie som na toto expert, ale neviem si celkom predstaviť, ako by sa dal spraviť nejaký všeobecný nekonštruktívny dôkaz, že v grafe je klika stupňa aspoň n, teda okrem prípadov, že je takmer kompletný.
Odpovedať Hodnotiť:
 

to som prave chcel vediet. pretoze v clanku to je formulovane takto
"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."
Odpovedať Hodnotiť:
 

Aby si zistil, ci je tam klika, musis prechadzat graf kym ju nenajdes (NP). Ked ju mas, overujes len ci klika je klika (P). Ci nie tak?
Odpovedať Hodnotiť:
 

Plavčan!=NedámPeniaze
Odpovedať Známka: 7.5 Hodnotiť:
 

Smer+sns 2.
Veselo tunelujú vedu

Môžeme všetci smútit slovenská veda dopadne ako slovenské diaľnice.
Odpovedať Známka: 0.0 Hodnotiť:
 

negative len preto ze je to v pici drahi veriaci
Odpovedať Hodnotiť:
 

Kazdy co ma IQ nad 0 (cize kladne) vie ze P == P a P != NP

Ved ako sa aj moze P rovnat NP ??? To akoze co dokazali, matematicky kruzok v blazinci?
Odpovedať Známka: -5.5 Hodnotiť:
 

true == false
Odpovedať Známka: -3.3 Hodnotiť:
 

Lekcia prvy rocnik:
if (false) som_kokot; else niesom_kokot;
Odpovedať Známka: 6.0 Hodnotiť:
 

Nie.
Odpovedať Známka: 0.0 Hodnotiť:
 

... no neviem neviem ... Bodkociaky ma zle .. takze ano....
Odpovedať Známka: 7.1 Hodnotiť:
 

Takze kym sa nezhodneme, je false pre istotu aj ano aj nie, aby nevznikali zbytocne nezhody.
Odpovedať Známka: 3.3 Hodnotiť:
 

A naviac to umoznuje optimalizaciu odstranenim podmienky.
Odpovedať Známka: 10.0 Hodnotiť:
 

P=x
N=1

x = 1*x
Odpovedať Známka: 10.0 Hodnotiť:
 

P=0
N= devet
:D
Odpovedať Známka: 8.2 Hodnotiť:
 

Veda funguje tak, ze ked nieco tvrdis, tak to aj musis vediet dokazat. Ako ano, vseobecne sa predpoklada, ze P != NP, ale stale to je len hypoteza ktoru sa nepodarilo potvrdit.
Odpovedať Známka: 10.0 Hodnotiť:
 

a ked to nemozes dokazat, nazves to teoriou
Odpovedať Známka: -5.0 Hodnotiť:
 

Práve naopak teóriou to nazveš až keď to dokážeš.
Odpovedať Známka: 10.0 Hodnotiť:
 

ak je to dokazane, tak uz to nemoze byt len prachobycajna teoria
Odpovedať Hodnotiť:
 

Jednoducho. P nie je character ani string. Rovnako tak ani NP. Ide o množiny. Problémom je zistenie vzťahu medzi P a NP. Empirické dokazovanie v praxi je takmer nemožné, vzhľadom na relatívnu pomalosť aj najvýkonnejších súčasných počítačov a ich drahý výpočetný čas. Jeden nepodarený experiment, ktorý by sa zvrhol na exponenciálne peklo, by odstavil superpočítač na ? dní, mesiacov. Clear?
Odpovedať Známka: 6.7 Hodnotiť:
 

Eventualne je mozne nebyt uplny ...exemplar a empiricke dokazovanie neriesit cez abelovske grupy, definovane priekazne prave tak, aby to cez ne neslo, co je ale odbornikom zrejme.
Odpovedať Známka: -6.0 Hodnotiť:
 

myslim ze v pripade P! a NP je znamená znamienko = relativny priemer casu a nie rovnost
Odpovedať Známka: -6.7 Hodnotiť:
 

Nie, ide naozaj o rovnosť množín. Zhruba:

P - množina programov vypočítateľných v polynomiálnom čase na deterministickom turingovom stroji
NP - množina programov vypočítateľných (taktiež) v polynomiálnom čase ale na nedeterministickom (odtiaľ to N) turingovom stroji

Je zjavné, že P je podmnožina NP. Otázkou zostáva, či aj NP je podmnožinou P (a teda či sa tieto množiny rovnajú).
Odpovedať Známka: 10.0 Hodnotiť:
 

Na cstheory http://dopice.sk/k4A prebieha online diskusia ohľadom tohoto dôkazu.

V dôkaze P != NP sa odkazuje ten profesor na ďalšie jeho publikácie, ktoré ale nie sú verejné. Trošku zvláštnosť pri dôkaze tejto vety, nie?
Odpovedať Známka: 7.5 Hodnotiť:
 

tento dokaz som necital (aj tak by som mu asi nerozumel) ale tak predpokladam, ze sa neodkazuje na dokaz, ktory ma doma v kniznici, ale ktory bol niekde publikovany a je mozne sa k nemu dostat. Takze je mozne, ze len nemoze sirit cast svojej prace zadarmo, lebo by s tym mal problem vydavatel. Alebo bol len lenivy a nechcelo sa mu robit pre neho zbytocnu pracu.
Odpovedať Známka: 10.0 Hodnotiť:
 

Publikácie sú dostupné, ale vydavateľ si práve účtuje nemalú čiastku.
Odpovedať Známka: 5.0 Hodnotiť:
 

sci-hub.cc vyriesi problem (nebudeme snad krmit vydavatelov, ktori uctuju otvaranie clankov aj ich autorom)
Odpovedať Hodnotiť:
 

A slovenski politici vam daju dokaz ze nulou sa da delit a tie nekonecna sa vyparia do danovych rajov v igelitkach a ruksakoch!
Odpovedať Známka: 10.0 Hodnotiť:
 

Vždy sa bavím, keď P a NP začnú spomínať ITčkári, aby si pripadali dôležito, pritom o tom vedia prd. Toto je otázka pre vedcov a oni sú len roboši, čo zapájajú routre.
Odpovedať Známka: 6.0 Hodnotiť:
 

pripadne "objekty"
Odpovedať Známka: 0.0 Hodnotiť:
 

Student informatiky na matfyze je tiez vlastne ITckar a takyto ludia uz robia nejaku vedu.

Inak ale pojem ITckar uz beriem skoro ako urazku, kedze je to z definicie takmer kazdy kto robi s pocitacom.
Odpovedať Známka: 8.3 Hodnotiť:
 

mas pravdu, ti dokazu spravit vedu zo vsetkeho :-)
Odpovedať Známka: 2.0 Hodnotiť:
 

Pripadali dôležito? Ty budeš asi jeden z tých, ktorých výpočtová zložitosť netrápi. Tieto triedy sú významné aj v praxi. Pretože P sa ešte považuje za prakticky použiteľnú, zatiaľ čo NP obsahuje veľa pre prax dôležitých problémov, avšak je (zatiaľ) výpočtovo príliš náročná. Aproximácia NP problémov na približné ale dostatočne presné riešenie algoritmom z množiny P je pre prax mimoriadne významná.
Odpovedať Známka: 10.0 Hodnotiť:
 

V tomto máš pravdu. V praxi sa NP problémy riešia dosť bežne ale v drvivej väčšine prípadov netreba presný výsledok, ale stačí aproximácia. Alebo sa ukáže, že vo väčšine prípadov v praxi platia ešte ďalšie obmedzenia, čo uľahčí riešenie problému, prípadne ten problém s ďalšími podmienkami spadne do P.
Odpovedať Známka: 10.0 Hodnotiť:
 

V drvivej vacsine netreba presny vysledok ale staci aproximacia. No hej, ibaze to je iba z nudze cnost -staci, ale iba pre to, ze ten presny vysledok nedokazeme efektivne dostat.
Odpovedať Hodnotiť:
 

Vôbec to nemusí byť z núdze cnosť. Ak sa riešia problémy na nameraných dátach, tak už samotné dáta obsahujú chyby, ktoré vyplývajú z meraní. V tomto prípade ak by sme aj vyriešili daný problém presne pre vstupné dáta, nedá nám to o nič lepší výsledok v realite ako aproximácia. Keďže samotné dáta, ktoré obsahujú chyby z meraní sú vlastne iba aproximácia.
Odpovedať Známka: -3.3 Hodnotiť:
 

ak P == NP tak to znamena ze si mozem vytazit vsetky bitcoiny v polynomynalnom case ked na to pridem?
Odpovedať Známka: 8.0 Hodnotiť:
 

Príliš to nesledujem ale myslím že nie. Pretože oni obťažnosť dolovania dynamicky menia podľa toho, ako rýchlo sa vyťažili predošlé.

Taktiež, hoc by sa aj P rovnalo NP, to ešte neznamená, že nájdeme efektívny spôsob ako tie programy transformovať. Dôkaz totižto nemusí byť konštruktívny.
Odpovedať Známka: 4.3 Hodnotiť:
 

Oni obtiaznost menia? Kto oni?
Ja verim ze sa obtiaznost meni sama kazdych 2016 blokov.
https://en.bitcoin.it/wiki/Difficulty

V podstate by na mega urychlenie miningu stacil kvantovy pocitac.
Odpovedať Známka: 10.0 Hodnotiť:
 

P!=NP prave vtedy, ked ! je rozne od N
Odpovedať Známka: -6.7 Hodnotiť:
 

! = N
Odpovedať Známka: 6.0 Hodnotiť:
 

a budu teraz rozky lacnejsie ?
Odpovedať Známka: 3.3 Hodnotiť:
 

matfyz oceni
nido iny neoceni.

ale jak moc oceni matfyz to nido nevi.

Odpovedať Známka: 0.0 Hodnotiť:
 

Ma zaujal skok zo strednej na výšku. Najskôr všetko priamo dokázateľne, poučky, a potom výška teória grafov a zrazu hľadáme cesty s najnižšou váhou primitivne náhodným bruteforce spôsobom...sortingy 10 typov atď...
Odpovedať Známka: 3.3 Hodnotiť:
 

To len dokazuje že tento svet stvorila neskutočne inteligentná bytosť (resp. možno bytosti), ktorá sa teraz len smeje nad našou hlúposťou.
Zhruba ako keď my dospelí sledujeme malé trebárs 1 ročné deti ako riešia a doslova sa trápia s riešením pre nás primitívnych úlohy typu poukladať objekty správnych tvarov do otvorov rovnakých tvarov :)
Odpovedať Známka: 5.0 Hodnotiť:
 

ano a to zacinaju zvladat az v puberte, su na to vzdelavacie videa na internete
Odpovedať Hodnotiť:
 

Pokus pána profesora o dôkaz je neúspešný... https://cstheory.stackexchange.com/a/38832
Odpovedať Hodnotiť:
 

Zutroy Clique - PSG
Odpovedať Hodnotiť:
 

P = P
NP = NP
P <> NP
easy
Odpovedať Hodnotiť:

Pridať komentár