39-ročný Ind tvrdí, že dokázal P != NP

DSL.sk, 9.8.2010

39-ročný Vinay Deolalikar pôvodom z Indie pracujúci pre výskumné laboratóriá spoločnosti HP v Palo Alto v piatok oznámil odbornej verejnosti, že sa mu úspešne podarilo dokázať nerovnosť tried zložitosti P a NP.

Deolalikar odborníkom z oblasti teórie zložitosti zároveň v piatok rozoslal 103-stranovú predbežnú verziu dôkazu (PDF).

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. Pre prvého úspešného autora dôkazu vzťahu medzi týmito triedami je vypísaná ako pre jediný problém z informatiky odmena Millennium Prize vo výške jedného milióna dolárov.

Do triedy zložitosti P patria problémy, pre ktoré existuje algoritmus pre deterministický Turingov stroj riešiaci tento problém v polynomiálnom čase vzhľadom k veľkosti vstupu. Deterministický Turingov stroj pre praktické účely takmer zodpovedá modelu súčasných počítačov. Do triedy zložitosti NP patria problémy vyriešiteľné v polynomiálnom čase na nedeterministickom Turingovom stroji, ktorý na n krokov môže preveriť exponenciálny počet možností k n.

Problémy z P patria do NP, doteraz sa s istotou nevedelo či aj všetky problémy z NP nepatria do P. Zvláštne postavenie medzi NP problémami majú tzv. NP-úplné problémy, na ktoré je možné v polynomiálnom čase redukovať ľubovoľný NP problém.

Podľa dôkazu Deolalikara sa ale P nerovná NP, čo automaticky znamená že žiadny NP-úplný problém nemôže byť v P a teda byť riešiteľný v polynomiálnom čase na súčasných počítačoch. Medzi NP-úplnými problémami je množstvo praktických problémov riešených informatikou, známe sú celkovo tisícky NP-úplných problémov. Ak sa potvrdí dôkaz Deolalikara a P != NP, dané problémy nie je možné s istotou riešiť v polynomiálnom čase.


Najnovšie články:



Diskusia:

Je to tak Od: ad_a | Pridané: 9.8.2010 11:01 Tak som to pdfko prestudoval a zda sa, ze to sedi... Odpovedať Známka: 8.4 Hodnotiť:

Re: Je to tak Od: kido | Pridané: 9.8.2010 11:02 Takze je to v P Odpovedať Známka: 9.3 Hodnotiť:

Re: Je to tak Od: Tupcek | Pridané: 9.8.2010 11:04 Tak som tento článok preštudoval a zdá sa, že mu nechápem... Odpovedať Známka: 8.6 Hodnotiť:

Re: Je to tak Od: Ľubomíra, zajtra Vavrinec | Pridané: 9.8.2010 11:42 Bazinga? Odpovedať Známka: 6.5 Hodnotiť:

Re: Je to tak Od: ccccc | Pridané: 9.8.2010 11:43 mu nerozumiem alebo to nechapem .. ziadne mu nechapem Odpovedať Známka: 6.8 Hodnotiť:

Re: Je to tak Od: liga_z_karpatskej | Pridané: 9.8.2010 14:43 Nech i=f(n) je počet krokov výpočtu algoritmu na vstupe dĺžky n. Teraz všetky algoritmy, čo bežia zhruba i^k k>0 krokov sú P a všetky čo bežia toľko nedeterministických krokov sú NP (ako non-deterministic polynomial). Nedeterministický krok si predstav akoby sa pri každom vetvení pustil paralelný výpočet na každú vetvu. Stačí ti, aby aspoň jeden z tých výpočtov skončil a našiel nejaké to riešenie. (Doposiaľ známy) Prevod tohoto na reálny výpočet ale počet krokov zmení na exponenciálny. ..príklad: vieš rýchlo (v čase P) overiť správnosť hesla. Môžeš heslo zistiť tak, že ho nedeterministicky "natypuješ" pre všetky kombinácie (v čase NP) a overíš (v čase P). Ak P=NP, tento algoritmus môžeš previesť na deterministický polynomiálny a zistiť tak heslo v polynomiálnom čase. Je nutné si uvedomiť, že aj i^1000000 je z P. Odpovedať Známka: 3.5 Hodnotiť:

Re: Je to tak Od: ground | Pridané: 9.8.2010 17:56 dakujem, stacilo to povedat takto normalne. niektori ludia by si mali brat priklad (redaktor dsl) ;) Odpovedať Známka: 8.2 Hodnotiť:

Re: Je to tak Od: sskio | Pridané: 9.8.2010 23:25 stačí že tomu rozumie liga_z_karpatskej ja mám problém hacknuť aj svoje vlasne heslo k emailu po dovolenke. Odpovedať Známka: 8.8 Hodnotiť:

Re: Je to tak Od: zippy | Pridané: 11.8.2010 8:02 kto je to liga_z_karpatskej? Ja som sa MatFyzu (aspon tomu nasemu bratislavskemu) zdaleka vyhybal. Odpovedať Známka: 0.0 Hodnotiť:

Re: Je to tak Od reg.: gandor | Pridané: 11.8.2010 15:42 Nieze by na tom tak velmi zalezalo, ale toto je hlavne problem pre informatikov ako MatFyz-akov (aj ked nevylucujem, ze aj oni sa o to zaujimaju). Stazuj sa teda na Fei a Fiit ak chces. :) Odpovedať Známka: -7.5 Hodnotiť:

Re: Je to tak Od: mkwinco | Pridané: 11.8.2010 19:38 No informatika je cast matematiky sa uci na Matfyze. FEI-ka su zase IT-ckari, co su ti machri od pocitacov. Takze skutocne, tento problem patri do toho pavilonu na kopci (FMFI) a nie do polpyramydok pod nim... ;) Odpovedať Známka: 6.0 Hodnotiť:

Re: Je to tak Od: liga_z_karpatskej | Pridané: 15.8.2010 1:26 Je to iba provokativny nick :) Odpovedať Hodnotiť:

The puarecshs I make Od: Ibrahim | Pridané: 3.7.2014 8:43 The puarecshs I make are entirely based on these articles. Odpovedať Hodnotiť:

Re: Je to tak Od: Vlado 54 | Pridané: 11.8.2010 19:45 Nuž zaujímavý a komplikovaný kľúč výpočtu.Ale akú má tento dôkaz úžitkovú hodnotu ? Odpovedať Známka: 10.0 Hodnotiť:

Re: Je to tak Od: jerk | Pridané: 12.8.2010 15:40 Taku, ze iste veci, co sme doteraz iba nevedeli naprogramovat efektivnejsie nez exponencialne, tak teraz uz vieme, ze sa to nejak zasadne lepsie ani neda a nemusime naivne dufat a zbytocne si lamat hlavy. Nestudoval som dokaz, ale mozno to ma aj dalsie dosledky, ak poukazuje na iste teoreticke suvislosti medzi konceptami z roznych oblasti matematiky a informatiky, ktore mozu byt zaujimave a uzitocne pri rieseni ciastkovych problemov podobneho, ale predsa len ineho charakteru. (kokos, to je take vagne, ako keby som bol politik, ale snad mi rozumiete) Odpovedať Známka: 3.3 Hodnotiť:

Re: Je to tak Od: Adrique | Pridané: 9.8.2010 12:29 fuck me, nemam najmensiu sajnu o com sa tu toci.. a aky to bude mat osoh pre spolocnost? ak to pomoze predist zahlteniu print servera vo velkom kancli pri tlaci cez wifi z mnozstva PDA-ciek....tak OK :-) Odpovedať Známka: 5.7 Hodnotiť:

Re: Je to tak Od: : Pjetro de | Pridané: 9.8.2010 12:37 ano ano, aj ty spadas do absolutne drvivej 99,999 ... 9 % velkej casti populacie, ktory nevie o co sa jedna, nevie dosledky ... atd (precitaj moj comment nizsie). Odpovedať Známka: -4.7 Hodnotiť:

Re: Je to tak Od: Adrique | Pridané: 9.8.2010 12:43 Ano, spadam, suhlasim. Je na tom nieco zle? Btw, zislo by sa dodat, ze nebolo by na skodu, keby sa autor clanku aspon trosicku unuval vysvetlit, co je P a NP a cela problematika. Odpovedať Známka: 7.2 Hodnotiť:

Re: Je to tak Od: : Pjetro de | Pridané: 9.8.2010 12:47 Samozrejme ze na tom nic nie je, keby mal clovek vediet vsetko, mal by hlavu jak futbalovy stadion. Myslim si, ze dokonca sa neda udrziavat ani len zakladny prehlad vo vsetkych znalostiach na takej urovni, aby bol priemerny citatel ako-tak schopny aj ked nie plnohodnotne, tak aspon orientacne, clanok pochopit. Holt znalosti ludstva za za posl. pol tisicrocia zvacsili tisicky-nasobne ... Odpovedať Známka: 7.7 Hodnotiť:

Re: Je to tak Od: zippy | Pridané: 9.8.2010 15:55 O co ide? Chces porovnavat 2 algoritmy. Tak mas v podstate 2 moznosti: mnozstvo spotrebovanej pamate (pamatova zlozitost) alebo cas potrebny na dokoncenie (casova zlozitost). V teorii informatiky sa vymyslel tzv. Turingov stroj a oboje tieto metriky sa zistuju z neho. Definuju sa triedy: DTime[t(n)] <=> {L | existuje k-paskovy DTS M: L(M) = L a T_M je v O(t(n))} Analogicky pre NTime, DSpace, NSpace; Stoji za povsimnutie, ze priestorova zlozitost nemoze byt vacsia nez casova. Potom: P = zjednotenie od k=0 do nekonecna DTime(n^k); NP je zjednotenie od k=0 do nekonecna NTime(n^k); Odpovedať Známka: 8.2 Hodnotiť:

Re: Je to tak Od: kkkkkkkk | Pridané: 11.8.2010 20:15 100 bodov..toto malo byt v clanku.. Odpovedať Známka: 2.0 Hodnotiť:

Re: Je to tak Od: naco | Pridané: 9.8.2010 22:34 Po 2 hodinach umorneho manualneho prezerania starych spisov a mudrych knih, som pre Teba nasiel nieco o tomto mystickom probleme http://en.wikipedia.org/wiki/P_versus_NP_problem Odpovedať Známka: 10.0 Hodnotiť:

Re: Je to tak Od: Adrique | Pridané: 10.8.2010 13:51 diky. ked som si precital uvod tohto clanku na wikipedii, aj tento clanok na dsl dostal pre mna aky-taky zmysel Odpovedať Známka: 10.0 Hodnotiť:

Re: Je to tak Od: burlak (Andrej Manduch) | Pridané: 9.8.2010 13:51 No je to najäčší matematický problém tisícročia, na anglickej wiki je tuším pekne vysvetlený, ono sa predpokladalo že tam ta nerovnosť je ale nebol na to žiaden dôkaz, keby ale niekto dokáže že je tam rovnosť bolo by pre teba zbytočné používať väčšinu kryptovacých mechanizmou lebo by sa vedelo že každý sa dá jednoducho prelomiť z jednoducým výpočtom. Takže má to pre teba osoch, môžeš komunikovať z bankou cez internet a aj keď niekto bude odpočúvať tvoje spojenie vieš, že mu to nijak nepomôže. Odpovedať Známka: 4.3 Hodnotiť:

Re: Je to tak Od: vatrtko 4 | Pridané: 9.8.2010 16:32 ty sa vrat do skoly za zacni sa ucit pravopis. Keby som takto pisal do diskusie tak sa idem hned obesit. :D Odpovedať Známka: -7.3 Hodnotiť:

Re: Je to tak Od: fcdsaf | Pridané: 10.8.2010 10:56 ach ty looser, nerozumel si ani tomu co napisal, preto si sa zmohol argumentovat na grmatiku :) ja by som sa zahrabal pod zem byt tebou :D Odpovedať Známka: 4.3 Hodnotiť:

Re: Je to tak Od: hellokitty | Pridané: 11.8.2010 9:19 njn a dalsi loser co si robi srandu s ineho losera a pritom ho nazyva looserom =) Odpovedať Známka: -4.3 Hodnotiť:

Re: Je to tak Od: bigshiff | Pridané: 11.8.2010 18:42 a dalsi looser, ktory reaguje na loosera :D Odpovedať Známka: -2.0 Hodnotiť:

Re: Je to tak Od: kkkkkkk | Pridané: 11.8.2010 20:17 Sys err: looped.. xD Odpovedať Známka: 3.3 Hodnotiť:

Re: Je to tak Od: burlak (Andrej Manduch) | Pridané: 11.8.2010 21:06 Trochu tvrdé slová, ale aj tak ďakujem. Odpovedať Hodnotiť:

Re: Je to tak Od: juraj0r | Pridané: 12.8.2010 10:52 Vela nepravd. Skutocne to suvisi s kryptografiou. Ale ani P=NP neznamena, ze to bude "jednoducho" prelomitelne, lebo tie konstanty mozu byt obrovske (x^500000000 je tiez polynomialny algoritmus a prakticky neriesitelny na sucasnych strojoch pre vacsie x). Tak isto nie je jasne, ze sucasne sifry su vobec NP-uplne alebo ak bude dokazana nerovnost P!=NP, ze su v NP ale nie su v P. Odpovedať Hodnotiť:

Re: Je to tak Od reg.: cipo11 | Pridané: 9.8.2010 20:47 Podľa mňa je v 135. a 140. riadku chyba. Je teraz milión môj? Odpovedať Známka: 2.5 Hodnotiť:

Re: Je to tak Od: ... | Pridané: 10.8.2010 15:09 Nie, milion dostanes ak to spravne dokazes. Nie ked najdes chybu, to je ovela trivialnejsie. Odpovedať Známka: 10.0 Hodnotiť:

Re: Je to tak Od: asd789456 | Pridané: 10.8.2010 9:19 .. podla mna na 52hej strane dokumentu ma byt vo vzorci +. Potom to bude dobre ;) Odpovedať Známka: -4.3 Hodnotiť:

jasné Od: rts | Pridané: 9.8.2010 11:09 ja tomu tiež celkom chápem Odpovedať Známka: 4.8 Hodnotiť:

1 != 3 Od: gru | Pridané: 9.8.2010 11:14 to je jasne ze sa P nemoze rovnat NP. To uz vidno na prvy pohlad, ze NP su 2 pismena a P len jedno ;) Odpovedať Známka: 6.8 Hodnotiť:

Re: 1 != 3 Od: qdwcc | Pridané: 9.8.2010 13:16 no rovnost plati ak N=1, pre vsetky realne cisla. Odpovedať Známka: 6.6 Hodnotiť:

Re: 1 != 3 Od: vlk32 | Pridané: 12.8.2010 12:15 ... a pre lubovolne N, ak P=0 Odpovedať Známka: 10.0 Hodnotiť:

And I was just wodie Od: Themad | Pridané: 5.7.2014 14:10 And I was just wodiernng about that too! Odpovedať Hodnotiť:

kthxbai Od: rms_ | Pridané: 9.8.2010 11:17 Moze niekto to PDF uploadnut na spolahlivy server? Odpovedať Známka: -4.4 Hodnotiť:

Re: kthxbai Od: rms_ | Pridané: 9.8.2010 11:54 Ak to niekto potrebuje tak je to podla vsetkeho tento dokument http://www.win.tue.nl/ ~gwoegi/P-versus-NP/Deolalikar.pdf Odpovedať Známka: 3.3 Hodnotiť:

aj ja Od: redo | Pridané: 9.8.2010 11:21 Do riti, robím na tom 5 rokov a teraz ma predbehne nejaký Ind :-) Odpovedať Známka: 8.2 Hodnotiť:

Re: aj ja Od: Equinox | Pridané: 9.8.2010 18:24 Ja som na tom robil asi jedno popoludnie, ale vykaslal som sa na to. Bolo to na mna prilis trivialne a kedze v Indii obracaju v ruke kazdy peniaz, nechal som to tak a veril som, ze to ten Ind dokaze a zarobi si nejaky ten halier. Odpovedať Známka: 3.8 Hodnotiť:

Hmm... Od reg.: Michal Kryl | Pridané: 9.8.2010 11:21 No pozrimeze, akych mame na Slovensku odbornikov, co hned vyrukuju, ze to tak je, pritom sa jedna len o predbeznu spravu a nie hotove vypracovanie celkovej problematiky... Ked to tak je, preco si na to neprisiel aj ty? Studia este musi prejst urcitym preverovanim, aj ked vypada znacne vierohodne a skutocne sa javi pravdivou. Ide o to, ze by mala celkom zaujimavy dopad na IT celkovo. A jedine co nateraz moze clovek objektivne znaly aspon nejednoznacne problematiky, ze je riesenie problemu zrejme spravne. Preto prosim vyjadrite sa korektne... :D Odpovedať Známka: -5.6 Hodnotiť:

Re: Hmm... Od reg.: Redakcia DSL.sk | Pridané: 9.8.2010 11:28 Formulácie "39-ročný Ind tvrdí, že dokázal P != NP", "v piatok rozoslal 103-stranovú predbežnú verziu dôkazu", "Podľa dôkazu Deolalikara sa ale P nerovná NP" a "Ak sa potvrdí dôkaz Deolalikara a P != NP" zrejme veľmi presne vystihujú presný stav. Odpovedať Známka: 7.9 Hodnotiť:

Re: Hmm... Od reg.: Michal Kryl | Pridané: 9.8.2010 11:34 Vazena redakcia, ospravedlnujem sa, ale zle sme sa pochopili, nemam vyhrady k clanku, ale mam vyhrady ku komentarom niektorych ludi :) Urovne clankov na DSL hodnotim z vacsej casti ako vyspele a dobre citatelne, cim chcem povedat, ze odvadzate sakra dobru pracu :) Odpovedať Známka: 1.2 Hodnotiť:

Re: Hmm... Od reg.: Redakcia DSL.sk | Pridané: 9.8.2010 11:41 OK, díky. Odpovedať Známka: 8.3 Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 9.8.2010 12:16 Vazeny pan Kryl, som si na 99,999 999 % isty, ze na uzemi SR sa nenachadza akademik z prislusnej oblasti, ktory by dokazu rozumel (podobne napr. aj dokazu Velkej fermatovej vety). Komentare typu "5 rokov na tom pracujem a teraz ma predbehne nejaky Ind" kazdy normalny clovek ako clen society s patricne vyvinutym EQ nepochopi inak ako peknu recesiu, srandu a ironiu. To ze ste to nepochopili vy, pravdepodobne svedci o nedostatku istych neuronovych drah, ktore maju za ulohu komunikaciu, porozumenie a vobec kooperaciu s jednotlivcami a spolocnostou. Odpovedať Známka: 5.9 Hodnotiť:

Re: Hmm... Od: fortyTwo | Pridané: 9.8.2010 12:54 Pjetro, ty zijes v zahranici, alebo sa len momentalne nenachadzas na uzemi SR ? :) Odpovedať Známka: 9.0 Hodnotiť:

Re: Hmm... Od: hrr | Pridané: 9.8.2010 13:08 Ja som si na dobrych 99% isty, ze na uzemi SR sa takych akademikov nachadza aspon niekolko, len silne pochybujem, ze sa zdrzuju na servri dsl.sk. Pretoze je dobre zname, ze pochopit predlozeny dokaz je daleko jednoduchsie ako ho vymysliet. Takze ja by som (obzvlast niektorych vybranych) akademikov na slovenskej hrude nepodcenoval... Odpovedať Známka: 8.9 Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 9.8.2010 14:08 Preto som napisal prvdepodobnost 99,99999% ze tu takeho nemame, miesto 100%. Dokaz vymysliet a pochopit su ozaj dve rozlicne veci. Avsak aj na pochopenie dokazu vo vedeckej sfere treba patricne znalosti. Pochybujem ale, ze tu mame tucty Prof. Bukovskych ci inych vrcholovych osobnosti matiky. Netvrdim ze tu na 100% nikto taky nie je a ked nahodou hej, budu sa dat tito intelektuali velmi rychlo spocitat. Odpovedať Známka: 4.5 Hodnotiť:

Re: Hmm... Od: hrr | Pridané: 9.8.2010 15:00 Tak s tymto uz suhlasim a s pravdepodobnostou limitne sa blizciacou k jednej by nam na ich spocitanie stacila jedna ruka. Odpovedať Známka: 10.0 Hodnotiť:

Re: Hmm... Od: Rolando | Pridané: 12.8.2010 7:41 Ale musi to byt ruka cloveka, ktory dlhorocne a velmi neopatrne pracoval na cirkularke, a dnes je invalidom. Odpovedať Známka: 10.0 Hodnotiť:

Preco? Od: jerk | Pridané: 12.8.2010 15:48 Znizovanim poctu prstov sa zmensuje aj sanca, ze bude stacit jedna ruka. Cim menej prstov, tym menej staci jedna ruka. Neoruzmiem logike, ze mensi pocet prstov je nutnou podmienkou na spocitanie maleho mnozstva objektov. Na spocitanie nula objektov je ruka s milion prstami uplne rovnako vhodna ako ruka bez prstov. Odpovedať Hodnotiť:

Re: Preco? Od: Rolando | Pridané: 13.8.2010 9:47 Podstatou je naznačiť nulový počet, čomu najlepšie vyhovuje ruka bez prstov. Bolo to tak tazke na pochopenie? Odpovedať Známka: 10.0 Hodnotiť:

Re: Hmm... Od: dd_ | Pridané: 12.8.2010 10:46 no v skutocnosti su matikov z tej ligy ako prof. bukovski na slovensku naozaj desiatky, navyse mnohi z nich su o generaciu mladsi a teda aktivni. Odpovedať Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 9.8.2010 14:16 Pravdepodobne je, ze spominani akademici sa preto nezdrzuju na DSL.SK, lebo nevedia ani len zapnut pocitac. Su totiz radi, ked udrzia moč a kriedu. Nic v zlom. Odpovedať Známka: 4.1 Hodnotiť:

Re: Hmm... Od: maxos | Pridané: 9.8.2010 20:55 Neviem kde zijes ale nepaci sa mi tvoje podcenovanie. Take nieco mozno sa deje na prirodovedne zaloznych univerziatch (o com som pocul i z rozpravania) ale urcite nie technickych a hlavne zameranych na infromatiku. Odpovedať Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 10.8.2010 10:53 Tak jest, su univerzity, fakutly ci katedry, kde 70-75 rocni akedemici (ktori sice negarantuju odbor, lebo to mozu tusim len do 60 rokov, ci 65 - ale ich znalsoti a skusenosti v prislusnej vedeckej oblasti, ako aj pedagogicke skusenosti volaju po ich zotrvani v akademickej pode), takze su aj postarsi akademici, ktori sa vedia pri PC otacat. Taki ale nie su vsetci a to je nesporny fakt, dokonca sa domnievan ze tych zrucnych je zo vsetkych mensina. Opat nic v zlom, lebo konstatovanie. Odpovedať Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 10.8.2010 10:54 len, nie lebo konstatovanie Odpovedať Hodnotiť:

Re: Hmm... Od: maxos | Pridané: 10.8.2010 15:27 Prispievas do diskusie ktora sa silne opiera o informatiku takze pisat o profesoroch ktori nevedia ani zapnut pocitac nieje na mieste...Ja som napr pocas studia nemal ziaden problem nieco vybavit cez email a to mi ked som sa nahlasoval na skusku profak odpisoval aj v nedelu. Odpovedať Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 10.8.2010 17:38 Je jedno kde prispievam, pravda o veci X by si nemala vyberat forum s tematikou Y. Bohuzial toziz pocas celej mojej posobnosti na VS (10 rokov) som nepoznal starsieho akademika nad 65-70 rokov, ktory by s PC vedel narabat na urovni, ktoru by som opisal ako relativne slusna a primerana veku, postaveniu a pouzivaniu. Dokonca poznam jedneho veduceho katedry informatiky, ktory je tak duty a prispaty, ze to musi byt len sen (zije v prvej polovici 90tych rokov 20. storocia a tam aj koncia jeho vedemosti). Cest dvom vynimkam, na alma mater unievrzite som poznal dvoch akademikov, ktori s PC vedia narabat relativne slusne (50tnik a 60tnik). Ani jeden jediny nema nic spolocne s informatikou. Odpovedať Hodnotiť:

Re: Hmm... Od reg.: Michal Kryl | Pridané: 9.8.2010 13:55 Ako vidim, nie som jediny ktory bol nepochopeny... Narazal som na ludi, ktory tvrdia ze tomu chapu a potvrdzuju, ze je pravdiva :) Tym nejde o recesiu a ironiu, tak to mozeme pochopit mi, ale nie vzdy to tak je :) Nechajme vyklady tez a radsej sa vratme k normalnejsej komunikacii ;) Lebo by som musel napadnut vacsinu tvojich vyjadreni clovece a to by sa ti nemuselo pacit :) Moje EQ je dostatocne na to aby som chapal recesiu a pokus o vtip, ale ako som pisal vyssie, ludia co myslia veci vazne a pritom im nerozumeju mi proste vadia :) Odpovedať Známka: -2.0 Hodnotiť:

Re: Hmm... Od: : Pjetro de | Pridané: 9.8.2010 14:09 OK, ale s tou gramatikou by si mal vazne nieco robit clovece. Odpovedať Známka: 7.1 Hodnotiť:

Re: Hmm... Od reg.: Michal Kryl | Pridané: 9.8.2010 14:32 Jo, toho som si celkom vedomy, bohuzial degradacia s pouzivania cudzich jazykov aj v praci :( Odpovedať Známka: 5.0 Hodnotiť:

Re: Hmm... Od: fafsa | Pridané: 9.8.2010 17:03 ale uplne zaklady by sa mohli udrzat v hlave od detstva.. z koho z coho.. s kym s cim... po praci si precitat knihu po slovensky urcite nezaskodi :) Odpovedať Známka: 10.0 Hodnotiť:

Re: Hmm... Od reg.: Michal Kryl | Pridané: 9.8.2010 18:03 Tak to sa zase zastanem sam seba, citam velmi vela, len so Slovenskou gramatikou (hanba mi) som mal problemy vzdy. Dalsi problem je, ze Slovenske preklady zahranicnych autorov su obvykle hrozne ;) A co sa tyka Slovenskych autorov, tak tych dobrych je pomenej... Odpovedať Známka: 10.0 Hodnotiť:

Re: Hmm... Od: Maxos | Pridané: 9.8.2010 20:52 Mozno ze slovensko ma na hovno vysoke skoly ale urcite nie tak ako opisujes dam ruku do ohna ze niekto kto by danemu dokazu rozumel sa nachadza na bud na matfyze alebo STUcke ci FRI alebo TUKE. Konkretne u nas na FRI par blaznov bolo co sa niecim podobnym zaoberalo. Odpovedať Hodnotiť:

Re: Hmm... Od: hrr | Pridané: 9.8.2010 23:09 Jarda alebo Frco? ;) Odpovedať Hodnotiť:

Re: Hmm... Od: maxos | Pridané: 10.8.2010 15:30 Dovolim si tvrdit ze obaja a k nim by sa mohol pripojit aj Paluch a urcite takych sa tam najde viac... :)) Odpovedať Hodnotiť:

Re: Hmm... Od: adte | Pridané: 9.8.2010 12:12 Slovo NP-complete sa dá preložiť ako NP úplný. Prečo to nespraviť? Takto článok vyzerá hrozne, ako zmeska slovenských a anglických slov. Odpovedať Hodnotiť:

Re: Hmm... Od: liga_z_karpatskej | Pridané: 9.8.2010 15:01 Ja ti poviem preco. Lebo P!=NP, preto! Odpovedať Známka: 10.0 Hodnotiť:

P != NP Od: iKEBAB | Pridané: 9.8.2010 11:30 Uff, viem ze je uz poncelok, ale takto zhurta zacat tyzden :-) Odpovedať Známka: 10.0 Hodnotiť:

vysvetlit Od: gmjqmj | Pridané: 9.8.2010 11:32 Pjetro de, prosim ta vysvetlis nam o co tam ide? DIK Odpovedať Známka: 8.8 Hodnotiť:

Re: vysvetlit Od: : Pjetro de | Pridané: 9.8.2010 12:20 Ked sa to potvrdi, tak uz o nic, nakolko vysledok tohoto dokazu bol predpokladany, t.j. hypoteza bola ze to tak je (len to nebolo dokazane - teda ak sa to naozaj potvrdi). Vsetci zachovajte klud, Zem nebude zburana kvoli intergalaktickej dialnici. Ani sucasna kryptografia sa nemusi triast. Az ked pridu kvantove pocitace. Odpovedať Známka: 2.6 Hodnotiť:

Re: vysvetlit Od: fortyTwo | Pridané: 9.8.2010 12:37 Nejaka kratka odpoved, zvykol si sa obsirnejsie vyjadrovat (no offense) :) Ale ked ty pises ze mozeme byt kludni, tak je to OK a uz to viac neriesim :) Odpovedať Známka: 4.7 Hodnotiť:

Re: vysvetlit Od: Pedro El | Pridané: 13.8.2010 0:05 Pjetro, chyba ti tam ciarka. Gramatika neni k...a, ze si s nou mozes robit co sa ti zachce :) Odpovedať Hodnotiť:

Using or not using i Od: Liliez | Pridané: 3.7.2014 17:00 Using or not using ie8 won't increase data speed. That's hwarrade, not software. Telco can think whatever they like, but only if they're capable of thinking, which is doubtful given their discussions with me. Their responsibilities don't include how I hook up my phones, and that includes my DSL splitter. It's 100% legal to hook one of these up. I also discussed this with my provider, and they said it was worth trying, so I guess they might know if it's illegal. Odpovedať Hodnotiť:

..... Od: Ja. | Pridané: 9.8.2010 11:35 Kurňa, prečo sa ma na to nikto neopýtal? Veď to je jasné. Odpovedať Známka: 6.9 Hodnotiť:

pdfko Od: alo | Pridané: 9.8.2010 11:43 tak som si to celé pdf pozrel a dospel som k jednému dvôležitému záveru.. To PDF má len 98 strán!! Odpovedať Známka: 8.5 Hodnotiť:

Re: pdfko Od: jerk | Pridané: 12.8.2010 16:02 Vazeny pan 39-rocny Ind, Je nam luto, ale spravnost Vami zaslaneho riesenia nemohla byt preskumana z dovodu nesplnenia anedodrzania prislusnych noriem a predpisov ohladom deklarovaneho minimalneho a maximalneho rozsahu zaslanej prace, pouzitych sadzieb pisma, riadkovania a odstavcov, ako aj dalsich technickych nedostatkov vyplyvajucich z konfliktu s prislusnymi regulaciami a nariadeniami vydanimi prislusnymi organizaciami v tejto suvislosti v sulade s vyhlaskou a zakonom cislo 1337/1984 zbierky. Z tohto dovodu Europska komisia, Europsky parlament, a Europska rada pre vedu a vyskum Vas dokaz N E A K C E P T U J E ako odpoved na prislusnu otazku. Na tuto odpoved as mozete do 15 dni odvolat, alebo o preskumanie mozete opatovne poziadat po uplynuti odvolacej lehoty a nasledneho prechodneho obdobia 42 dni. Za pochopenie dakujeme. Odpovedať Hodnotiť:

hm... Od: didoa | Pridané: 9.8.2010 11:47 z 1000 ludi co cita DSL.sk kolko dokaze ocenit vyznam tohoto clanku v tejto jeho podobe? Je to dost silno odborne napisane, skutocne specificka oblast. Myslim ze autor/prekladatel sa mohol malo hecnut a trochu ludskejsie popisat o co ide, dat nejake ludsky priklad na P, NP...nech si aj neMatFyz nieco z toho clanku odnesie. Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od reg.: michal6103 | Pridané: 9.8.2010 11:51 ked nerozumies, tak si dostuduj, su to vseobecne pojmy Odpovedať Známka: -8.5 Hodnotiť:

Re: hm... Od: Xujer | Pridané: 9.8.2010 12:26 Ja mam prosim dotaz, pane profesore. Ci ten plynomialny cas sa meria hodinkami? Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: : Pjetro de | Pridané: 9.8.2010 12:50 samozrejme hureje, plynomialnymi hodinkami Odpovedať Známka: 6.7 Hodnotiť:

Re: hm... Od: Hacik neregistrovany | Pridané: 9.8.2010 13:38 Polynomialny cas znamema, ze pocet krokov potrebny na vyriesenie daneho problemu sa da vyjadrit polynomom. Ide teda o vypocet poctu krokov. Casto je tento pocet zavisly od poctu prvkov mnoziny, v ramci ktorej sa problem pocita. Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: Hacik neregistrovany | Pridané: 9.8.2010 14:00 Este som mozno zabudol poznamenat jednu dolezitu vec. Pri vypocte krokov sa berie ten najhorsi scenar, to znamena, ze ide o horny odhad poctu krokov. Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: zippy | Pridané: 9.8.2010 16:00 nie tak celkom. mas dolne a horne ohranicenie. A pri alghoritmoch sa berie este aj priemerne. Napr. quicksort ma najhorsie n^2, najlepsie n*log(n), priemerne n*log(n); Odpovedať Hodnotiť:

Re: hm... Od: Hacik neregistrovany | Pridané: 9.8.2010 16:35 Pri rieseni zaradenia problemu medzi P/NP uplne problemy ma pri vypocte poctu krokov riesenia podla mna zmysel len horne ohranicenie. Je sice pekne, ak s pravdepodobnostou 50 % viete nieco vypocitat v polynomialnom case, ale ked co i len s pravdepodobnostou 5 % riesenie neviete najst v rozumnom case, nemozete prehlasit, ze nieco viete vypocitat v rozumnom case. O existencii dolneho a priemerneho ohranicenia viem, ale to podla mna nema vplyv pri posudzovani toho, ci je nieco P/NP riesitelne. Aby som to zhrnul, pre to, ci je nieco riesitelne v polynomialnom case, je dolne ohranicenie irevelantne. Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: zippy | Pridané: 10.8.2010 19:35 to povedz tym, co sa predbiehaju v tom, kto spravi lepsi SAT solver Odpovedať Hodnotiť:

Re: hm... Od reg.: gandor | Pridané: 11.8.2010 16:01 :D V tomto pripade je teoria dolezitejsia. Ta vecsinou znizuje narocnost algoritmov na urovni polynomov a viac... Odpovedať Hodnotiť:

Re: hm... Od: dd_ | Pridané: 12.8.2010 10:58 ale ti asi nezlepsuju dolne odhady, ze ;-) Odpovedať Hodnotiť:

Re: hm... Od: Ja. | Pridané: 9.8.2010 12:21 Keby to zjednodušili, zas sa nájde hromada kecálkov, ktorá pindá, že ten článok je na chuja napísaný a nevystihuje podstatu Odpovedať Známka: 7.8 Hodnotiť:

Re: hm... Od: : Pjetro de | Pridané: 9.8.2010 12:52 vzdy niekomu nevyhovies Odpovedať Známka: 7.8 Hodnotiť:

That kind of thiknin Od: Dendi | Pridané: 4.7.2014 7:59 That kind of thikning shows you're an expert Odpovedať Hodnotiť:

Re: hm... Od: : Pjetro de | Pridané: 9.8.2010 12:36 Odpoved na prvu otazku je na celu debatu. Ak sa v nejakej oblasti urobi prevratny objav, kolko % popualcie vie o co sa jedna, aky to ma vyznam, ake to ma/bude mat/moze mat dosledky (prakticke a teoreticke)? Neslusne male promile. Koho zaujima dokaz Velkej fermatovej vety ci P <> NP? Ci dokaz ze prvoiselnych dvojiciek, trijiciek, n-ticiek je nekonecne vela? Alebo ze Riemanova hypoteza plati? Alebo ze v 1994 nasli Top Quark? Alebo ze mozno najdu Higgsov bozon? Alebo ze sa odhali zadna opona kvantovej mechaniky a budeme vediet preco je pravdepdobnostna a preco existuje vlnovokorpuskularna dualita. Alebo vznikne novy vedny odbor "morfomatika", ktora skuma prostriedky, cesty, sposoby a vlastnosti vedeckeho badania v dvoch protichodnych smeroch (redukcionistickom a holistickom) a ze nema zmysel sa lapotat po teorii vsetkeho. Koho to zaujima? Aka cast populacie to oceni? Odpovedať Známka: 8.3 Hodnotiť:

Re: hm... Od: ozchar13 | Pridané: 9.8.2010 13:09 ocenia to, ked sa v praxi vyuziju tie poznatky. Aj ked nebudu napr. vediet, ze ich novy procak je zalozeny na zas mensej 32nm technologii, budu radi (i/y?) ze maju vykonnejsi pc. Odpovedať Známka: 3.3 Hodnotiť:

Re: hm... Od: Hacik neregistrovany | Pridané: 9.8.2010 13:49 To,co zaujima Vas, je aplikovana veda. Ta ale casto vychadza zo zakladneho vyskumu, pricom prechod myslienok od zakladneho vyskumu (kam patri aj dokaz z clanku) k aplikovanej vede zvladnu asi len vedci a inteligentnejsi (ci lepsie vzdelani) ludia. V praxi ma clanok prinos v tom, ze sa v dohladnej dobe napriklad nezruti kryptograficky system. Na druhu stranu, nadeje, ze sa urcite problemy budu dat vyriesit rychlejsie, padli. (V pripade, ze by sa nejaky NP uplny problem dal vyriesit v polynomialnom case mozno by sa dalo lepsie predpovedat pocasie. Alebo takto, diferencialne rovnice by sa dali riesit jednoduchsie, co by viedlo k obrovskym pokrokom vsade tam, kde je treba fyzika. Tiez by sa jednoduchsie hladali lieky, pretoze niektore vyskumy v biologii potrebne pri vyvoji liekov su NP uplne problemy.) Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: : Pjetro de | Pridané: 9.8.2010 14:03 tak jest :-) Odpovedať Známka: 3.3 Hodnotiť:

Re: hm... Od: spooxik | Pridané: 9.8.2010 14:33 Bravooo... vycuc dosledku ... som rad ze taki ludia tu chodia... posunulo mi celu vec do oblasti ktoru aspon poxopim po precitani Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: nojane | Pridané: 9.8.2010 14:40 mna len to sere ze nikdy nebudem chapat tie transcedentne abstrakne myslienky a sposoby riesenia problemov..pripada mi to ze ked tomu nerozumiem tak si nezasluzim zit :( :) Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: Hacik neregistrovany | Pridané: 9.8.2010 14:53 (Poctivy clovek s nizsim IQ) > (Svina s vysokym IQ) Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: liga_z_karpatskej | Pridané: 9.8.2010 14:59 Tie sposoby riesenia problemov su take, ze nad tym rozmyslas den a noc a studujes stale nove a nove veci ktore by ti mohli pomoct a potom sa ti to jedneho dna prisni. Nemysli si, ze to je tak, ze teraz si sadnes cielene dokazes P!=NP. Odpovedať Hodnotiť:

Re: hm... Od reg.: kulinarik | Pridané: 9.8.2010 14:35 mna aj teba:-P Odpovedať Hodnotiť:

Re: hm... Od: : Pjetro de | Pridané: 9.8.2010 12:38 Reducionizmus svetko redukuje az na same spodne najjednoduchsie a najjednoduchsie pravidla, avsak ich aplikacia na vyssie urovne poznania je uplne nemozna, alebo kontraproduktivna. Holisticky pristup naopak zjednodusuje kazdu uroven sposobom, ze na tej urovni vytycuje nove zakladne pravidla, ktore nemusime odvodzovat z pravidiel spodnejsej (fundamentalnejsej) vrstvy. Napr. ked studujeme DNA, musime vediet biochemiu, a veci o cukroch, tukoch a bielkovinach. Tie posledne su tvorene aminokyselinami, ale nikto po nas nechce aby sme vedeli vypocitat vlnove pravdepodobnostne funckie 20-30 atomovych molekul aminokyselin. Tam zacinaju nizsie a fundamentalnesjie polozene pravidla kvantovej mechaniky, ale aplikovat ich v tomto stadiu (urovni) je uplne kontraproduktivne (cest vynimkam ako su PC simulacie spravania sa sekundarnych, tercialnych a kvarternych 3D struktur molekul na zakl. kvantovej mechaniky). Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: : Pjetro de | Pridané: 9.8.2010 12:39 Holistika jednuducho postavi chemiu ako "zaklad" a chemicke zakony postavi ako zakladne a ignoruje fakt, kt. sokoval vedecku verejnost v 20tych rokoch 20. storocia po objaveni kvantovej mechaniky, ze cela chemia je vlastne aplikovana fyzika na vyssie struktury. Elemektarne castice, jadra, elektronove obaly a jednotlive atomy - to je fyzika. Ale 2-atomova molekula - to uz je chemia. Odpovedať Známka: 10.0 Hodnotiť:

Re: hm... Od: spooxik | Pridané: 9.8.2010 14:28 myslite ze ten co to googletranslatol a poslovencil rozumie tomu co vlastne urobil a dal na vedomie? Odpovedať Hodnotiť:

NP-complete Od: npp != jpp | Pridané: 9.8.2010 12:16 NP-complete = NP-úplny problém? Odpovedať Hodnotiť:

Re: NP-complete Od: atde | Pridané: 9.8.2010 12:19 Ano. Odpovedať Hodnotiť:

Mafstory Od reg.: Martin xx. | Pridané: 9.8.2010 12:24 Alinko, tu som sa ja niekde stratil.... Odpovedať Známka: 10.0 Hodnotiť:

taka samozrejmost Od reg.: 5om@post.sk | Pridané: 9.8.2010 12:29 Nemusel sa unuvat, je predsa jasne, ze P sa nerovna NP. Staci, keby sa spytal tu na DSL fore a nemusel to rozpisovat na 130stran. :D Odpovedať Známka: 10.0 Hodnotiť:

Reakcia na clanok a komentare Od: Hacik neregistrovany | Pridané: 9.8.2010 12:31 K clanku a komentarom by som rad napisal par svojich slov: ze P != NP si myslela vacsina matikov. Islo len o to, ze sa o tento dokaz urcite pokusalo vela ludi a nikto zatial uspesne. Samozrejme, bola urcita cast ludi, ktori skusali nejaky NP uplny problem vyriesit v polynomialnom case (na klasickom turingovom stroji). Mimochodom, vsimnite si, ako skvele dokazal formulovat sprievodny list: This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. (zdroj: http://en.wikipedia.org/wiki/Vinay_Deolalikar). Tym padom ma nejaku zmluvu s HP, ze keby na to prisiel pocas prace v HP, musi dat prachy HP. Takto formulovane dostane prachy (a slavu) on :-) Odpovedať Hodnotiť:

Re: Reakcia na clanok a komentare Od: Hacik neregistrovany | Pridané: 9.8.2010 12:31 ... Medzi NP uplne problemy patri tusim rozlozenie velkeho cisla na sucin dvoch velkych cisel (na com na zalozene zabezpecenie). Keby sa tento problem dal vyriesit v polynomialnom case, mnoho zabezpeceni by padlo. Preto je tento dokaz dolezity z hladiska zabezpecenia klucmi. V pripade, ze som nieco niekde zle napisal, snad ma niekto opravi... Odpovedať Známka: 10.0 Hodnotiť:

Re: Reakcia na clanok a komentare Od: : Pjetro de | Pridané: 9.8.2010 12:49 jo, wo tom je to ze dnesna kryptografia moze zatial pokojne spavat :-) Odpovedať Známka: 6.7 Hodnotiť:

Re: Reakcia na clanok a komentare Od: repelent | Pridané: 9.8.2010 13:08 si na skole, alebo v praxi? Odpovedať Hodnotiť:

Re: Reakcia na clanok a komentare Od: : Pjetro de | Pridané: 9.8.2010 14:13 Na skole som posobil, dakujem uz nemusim (neprosim za 600-700 €), tak si len tak si citam IT servery. V praxi som, ale nie vedeckej. Odpovedať Hodnotiť:

Re: Reakcia na clanok a komentare Od: zippy | Pridané: 14.8.2010 0:48 no. ona mohla pokojne spavat aj tak. Aj x^1000 je P. Aj x^A(4,4) je v P, ale nechcel by som to ratat. Odpovedať Hodnotiť:

Re: Reakcia na clanok a komentare Od: ^_^ | Pridané: 11.8.2010 5:35 Predpokladá sa, že faktorizácia prirodzených čísel nie je ani P, ani NP úplná. Odpovedať Hodnotiť:

aodasldasnadsnlk Od reg.: DeeerDance | Pridané: 9.8.2010 13:14 Vo futurame to vedeli uz davno. http://i33.tinypic.com/3539rat.jpg Odpovedať Známka: 8.6 Hodnotiť:

Re: aodasldasnadsnlk Od: sher | Pridané: 9.8.2010 14:16 ROFL Odpovedať Známka: 10.0 Hodnotiť:

este ma napada Od: Hacik neregistrovany | Pridané: 9.8.2010 13:56 Mozno by bolo dobre pritomnym vysvetlit jednu dolezitu vec. Pred casom sa tusim dokazalo, ze lubovolny NP uplny problem sa da previest na lubovolny iny NP uplny problem. Tym padom, keby sa nahodou zistilo, ze nejaky NP uplny problem sa da vyriesit v polynomialnom case, dali by sa vyriesit vsetky. A to by malo obrovsky dopad (pozrite si moje prispevky vyssie). Odpovedať Známka: 2.0 Hodnotiť:

sdgfgdfhd Od reg.: kartan marketovy | Pridané: 9.8.2010 14:02 No ja tomu chapem. Ale len preto ze som otom pred par dnami cital clanok. Inak by som tiez nechapal. Odpovedať Hodnotiť:

Re: sdgfgdfhd Od: atde | Pridané: 9.8.2010 14:12 Presne tak. To pdfko je pisane ako pre uplnych redatrdov. Vysvetluje tam totalne jasne veci. Nechapem jak to nemoze byt niekomu jasne. Odpovedať Hodnotiť:

Re: sdgfgdfhd Od: Hacik neregistrovany | Pridané: 9.8.2010 14:46 Do not feed troll. Odpovedať Hodnotiť:

Re: sdgfgdfhd Od reg.: kartan marketovy | Pridané: 9.8.2010 15:07 bolo to v nejakom vydani .tyzdna za posledne 3 tyzdne, neviem presne v ktorom...sice len na 2 strany ale tak aby to pochopil kazdy Odpovedať Hodnotiť:

Re: sdgfgdfhd Od: liga_z_karpatskej | Pridané: 9.8.2010 15:19 http://www.tyzden.sk/ casopis/ 2010/31/ je-p-to-iste-co-np.html Odpovedať Hodnotiť:

Re: sdgfgdfhd Od: petko99 | Pridané: 11.8.2010 15:18 http://www.tyzden.sk/casopis/2010/31/% %je-p-to-iste-co-np.html keď to skopírujem pridá tam percenta alebo medzery a nejde to musím zmatovať percentá Odpovedať Hodnotiť:

kurva..... Od: wawa | Pridané: 9.8.2010 14:51 kurwya&..ten Ind ma predbehol o dva dni.ô...serwem na to ..tento problem riesim uz dva tyzdne... a pokrocil som poriadne daleko...a tento mamrd ma predbehol..ma sklak asi trafi :-))))))))))))))))))))ň Odpovedať Známka: -10.0 Hodnotiť:

husty matros Od: liga_z_karpatskej | Pridané: 9.8.2010 15:06 Nech sa prihlasi ten, kto seriozne rozumie tym veciam v tom dokaze. To som zvedavy ako dlho sa bude overovat. Odpovedať Hodnotiť:

Re: husty matros Od: atde | Pridané: 9.8.2010 15:11 Aspon polka diskutujucich na DSL.sk. Ty snad tomu nerozumies? Odpovedať Známka: 6.7 Hodnotiť:

Ja som to vedel už pred 10 rokmi. Od: asdf2 | Pridané: 9.8.2010 15:36 Lenže všetci boli leniví sa ma opýtať. Odpovedať Hodnotiť:

clanok Od: m44 | Pridané: 9.8.2010 15:48 clanok som pochopil v polynomialnom case :) Odpovedať Známka: 10.0 Hodnotiť:

Re: clanok Od: atde | Pridané: 9.8.2010 15:53 V závislosti na počte písmen? Gratulujem. Odpovedať Známka: 10.0 Hodnotiť:

Re: clanok Od reg.: gandor | Pridané: 11.8.2010 16:15 :DDD Tak toto sa podarilo :D Ale pravda. Musiet to pochopit v exponencialnom case, tak sa na cely clanok... :) Odpovedať Hodnotiť:

whau... Od: matti | Pridané: 9.8.2010 15:57 pekne obrazky tam ten ind povsuval, skoro som to dopozeral az dokonca Odpovedať Hodnotiť:

SG1 help Od reg.: saruman | Pridané: 9.8.2010 16:12 Treba kontaktovať veliteľa asgardskej flotily Thora, nech preverí, či dôkaz toho inda je v poriadku. Možno by na to stačila aj Samantha Carterova. Jack O'Neill by sa radšej postrelil zaknachtelom, ako by mal ten dôkaz v pdf čítať. Odpovedať Známka: 5.0 Hodnotiť:

Re: SG1 help Od: liga_z_karpatskej | Pridané: 9.8.2010 16:38 Prosím ťa, veď Carterová vymýšľa také dôkazy počas prechodu bránou.. Odpovedať Známka: 6.0 Hodnotiť:

príklady Od: skafander | Pridané: 9.8.2010 16:14 -Algoritmy triedení - P -Algoritmus vynásobenia dvoch n-ciferných čísel; T(n)=O(n2) - P -Prejsť šachovnicu koňom tak, aby na každé políčko stúpili práve raz. T(n)=O(8 n) - NP - Z n osôb vybrať maximálnu skupinu ľudí, ktorí sa navzájom poznajú. T(n)=O(2 n) - NP Odpovedať Hodnotiť:

mudrlanti Od: malymato | Pridané: 9.8.2010 17:06 Samozrejme, nerozumiem tomu ani ja, vlastne... nemam ani opnatia, o co ide. Osobne si myslim, ze takyto clanok nema na dsl.sk co robit, kedze drviva vacsina nema ani paru, o com je rec - ked uz niekto chce takyto clanok uverejnit, mal by citatelov aspon lahko uviest do problematiky. Omnoho viac mi vsak vadia niektore "odborne" komentare, ktore su napisane takym stylom, ze je zrejme, ze ich autor by nebol schopny vypocitat ani obycajnu kvadraticku rovnicu. Kedy sa uz ludia naucia, ze ked niecomu nerozumeju, je lepsie drzat hubu... Odpovedať Známka: -2.0 Hodnotiť:

Re: mudrlanti Od: :Pjetro de | Pridané: 9.8.2010 17:34 Az na to, ze toto akosi spada do teoretickej informatiky a DSL je portal o IT. Teoreticka informatika sice z extremalneho pohladu matematika nie je nic ine len aplikovane iste partie matematiky, ale aj tak. Samozrejme skripta z OOP, automatov, diskretnej matiky, numerickej matiky ci inych srand na informatike sem hadzat nemusia, ale tato newska sem imho patri presne tak ako rit na serbel :-) Odpovedať Známka: 10.0 Hodnotiť:

Re: mudrlanti Od: Solaris78 | Pridané: 9.8.2010 17:39 A je to jasné, používaš šerbel! Odpovedať Hodnotiť:

Re: mudrlanti Od: liga_z_karpatskej | Pridané: 9.8.2010 18:36 Ked to znesie casopis ako .tyzden, tak neviem kde vidis problem? Toto nie je nejaky bocny zaujimavy problemik informatiky, je to jeden z tych hlavnych. Nad tym, ze higgsov bozon je na titulke sme.sk sa nikto ani len nepozastavi. Nezaujima ma to, tak to necitam. Jednoduche. Odpovedať Hodnotiť:

Terazky Od: Adam2 | Pridané: 9.8.2010 20:08 Aku recu ste terazky hovorili??? Odpovedať Hodnotiť:

hej hej Od reg.: Zypa Cupak | Pridané: 9.8.2010 20:35 napísať napísal ale tak pekne pokosiť trávu z kosačku ako viem ja, ta toto nevie... Odpovedať Známka: 10.0 Hodnotiť:

Hmmmm Od reg.: Sheridan | Pridané: 9.8.2010 20:54 Vidim ze dnes informatici zazivaju orgazmus. Odpovedať Známka: 7.1 Hodnotiť:

asdfa Od: hoax | Pridané: 9.8.2010 21:28 milion za nieco comu nechape 99,9% ludi :D alebo to dsl iba tak zlozito napisalo Odpovedať Hodnotiť:

Re: asdfa Od: Peter Sveter | Pridané: 9.8.2010 23:36 Prečítaj si o tom v týždni http://www.tyzden.sk /casopis/2010/31 /je-p-to-iste-co-np.html Odpovedať Hodnotiť:

Zavolajme Od: iKEBAB | Pridané: 9.8.2010 22:19 Chucka, on to da.. Odpovedať Hodnotiť:

JAJ - a to P _=NP Od reg.: rikam | Pridané: 9.8.2010 23:57 No som s toho totalny magor, neviem o čo go ale hlevne že si viem zapnuť mikrovlnku, uvariť, čaj, a niečo napísať na PC. To ostatné nechám múdrejším. Odpovedať Hodnotiť:

Re: JAJ - a to P _=NP Od: AstaKiller | Pridané: 10.8.2010 13:17 Nic si z toho nerob. 99 percent podobnych magorov ani netusi ako vobec funguje monetarny system zalozeny na dlhu a uroceni a uz vonkoncom nechape, ze to je novodobe a sofistikovane otroctvo v ktorom len nedovidiet na mreze. Odpovedať Hodnotiť:

????? Od: *shrek* | Pridané: 10.8.2010 0:15 hm,ak nieco nejde riesit tak naco sa tym zaoberat a nie este dokazovat ze to nejde. Idem radsej bahnit do baziny :D. Ale co uz clovek neurobi koli melonu dolarov dokaze ,ze nieco nejde nedokazat nie to este vyriesit. Odpovedať Hodnotiť:

Re: ????? Od: oraJaro | Pridané: 10.8.2010 7:43 Aha, takze tvoj postup je taky, ze ked nieco nevies spravit, tak to nespravis vobec? Ano potial, pokial vies ? Alebo aspon tak dobre ako vies? Presne taka sa riesia taketo "tazke" (NP) problemy. V praxi sa pouzivaju tzv. aproximacne algoritmy, ale tymi ta radsej zatazovat nebudem, lebo si privodis este uraz.... Odpovedať Hodnotiť:

tazko sa to bude obhajovat Od: mgr. 2009 | Pridané: 10.8.2010 15:59 tych 100 stran je dost zle napisanych, uz od 9 strany je jasne, ze nerozlisuje medzi velke O a Omega. Odpovedať Hodnotiť:

Hm... Od: besný_pes | Pridané: 13.8.2010 13:28 Nerobme si nádeje, ešte stále nie je isté, či nemá v dôkaze chybu. Nie je prvý a možno ani posledný, ktorý prišiel s dôkazom platnosti/neplatnosti tvrdenia P != NP. Pozrite sa tu: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Ďalej by som vás rád upozornil, že z radov špičkových matematikov sa ozvali niektorí, ktorí si nie sú istí správnosťou jeho dôkazu. Pozrite sa tu: http://rjlipton.wordpress.com/ No uvidíme. Odpovedať Hodnotiť:

hmmmmmmmmmmmmmmmm Od: JoeJoe321 | Pridané: 13.8.2010 14:47 To som zvedavy kto pochopi to riesenie a schvali mu milion... Odpovedať Hodnotiť:

otazka Od: tralala123123 | Pridané: 13.8.2010 20:17 A preco prave tento milionprvy radoby dokaz problemu P vs. NP sa javi tak slubne ? Odpovedať Hodnotiť:

Pridať komentár