 
neprihlásený 
|
Sobota, 23. novembra 2024, dnes má meniny Klement |
|
|
P vs NP pre každého. Čo by znamenalo P != NP a čo P = NP
V piatok predminulý týždeň zverejnil Vinay Deolalikar svoj dôkaz, ktorý má riešiť zrejme najväčší otvorený problém informatiky a dokazovať nerovnosť tried zložitosti P a NP. Hoci v dôkaze bolo objavených viacero závažných problémov, Deolalikar avizoval ich odstránenie a definitívny osud tohto pokusu o dôkaz tak zatiaľ stále nie je jasný. Čo znamená problém P vs NP, čo by znamenali obe možnosti a ako to pravdepodobne je.
DSL.sk, 17.8.2010
|
|
Jednou z dôležitých oblastí, ktorými sa zaoberá informatika, je skúmanie či, ako rýchlo a čím je možné riešiť jednotlivé algoritmicko-výpočtové problémy.
Do predmetu jej záujmu patrí hľadanie praktických algoritmov pre jednotlivé problémy ale tiež aj dokazovanie toho, že niečo nie je možné ani teoreticky vypočítať alebo vypočítať dostatočne efektívne.
Problémy typu P
Za účelom skúmania zložitosti výpočtov klasifikuje informatika problémy do skupín, tried, podľa toho, ako časovo náročne idú vypočítať.
Zjednodušene problém patrí do tzv. triedy zložitosti P (Polynomial time), ďalej len "je typu P", ak je ho možné vypočítať klasickým programom aké výkonávajú súčasné klasické počítače v čase polynomiálnom vo vzťahu k veľkosti vstupných dát.
Program respektíve algoritmus počíta v polynomiálnom čase ak pre neho existuje polynóm f(x) = a0 + a1 * x^1 + ... + ak * x^k taký, že pre vstup o veľkosti n tento algoritmus problém vypočíta na počet krokov nanajvýš rovný f(n). Napríklad utriedenie n čísel je možné triviálne vyriešiť algoritmom, ktorý potrebuje 0.5 * n + 0.5 * n^2 krokov. Problém triedenia je tak typu P, triediť je samozrejme možné ale aj lepšími rýchlejšími algoritmami ako kvadratickými.
Algoritmy počítajúce v polynomiálnom čase vedia ľudia efektívne počítať na súčasných počítačoch, hoci samozrejme pre praktické účely je podstatné aký presne počet krokov je potrebné uskutočniť.
Pre neskoršie porovnanie s exponenciálnymi algoritmami, ak polynomiálny algoritmus napríklad počíta s kubickou zložitosťou, zdvojnásobenie veľkosti vstupu znamená zvýšenie počtu krokov približne 8-násobne. Takéto zvýšenie je v praxi tak zvyčajne realizovateľné zvýšením výpočtového výkonu, predĺžením doby výpočtu alebo kompromisom medzi obomi.
Problémy typu NP
Viaceré teoretické a praktické problémy zatiaľ vieme na klasických počítačoch riešiť ale len pomalšie ako v polynomiálnom čase, často až v exponenciálnom čase. Exponenciálny čas znamená, že algoritmus pre problém so vstupom o veľkosti n vyžaduje nanajvýš f(n) = c^n krokov, pričom c > 1.
V závislosti na konštante c môže počet krokov so zväčšujúcou sa veľkosťou vstupu u algoritmov s exponenciálnou zložitosťou veľmi rýchlo rásť a už pre malé vstupy dosiahnuť hodnoty prekračujúce súčasné výpočtové možnosti. Ak napríklad c = 2 a veľkosť vstupu zvýšime dvojnásobne napríklad z 50 na 100, počet krokov výpočtu sa zvýši až 2^50-krát na v súčasnosti nerealizovateľných 2^100 krokov.
Dôležitou skupinou problémov, kam patrí veľa problémov zatiaľ neriešiteľných v polynomiálnom čase, je tzv. trieda zložitosti NP (Nondeterministic Polynomial time). Základná definícia NP problémov je zložitejšia, k dispozícii je ale aj ekvivalentná alternatívna jednoduchšia definícia.
Podľa alternatívnej definície je problém typu NP, ak je možné správnosť riešenia problému overiť v polynomiálnom čase, hoci výpočet nemusí byť možné uskutočniť v polynomiálnom čase. NP problémom je tak napríklad rozloženie čísla na súčin prvočísel, ktoré zatiaľ nevieme uskutočniť v polynomiálnom čase. Správnosť riešenia ale vieme jednoducho overiť vynásobením vypočítaných prvočísel.
Originálna definícia NP problém definuje ako problém, ktorý je možné vypočítať v polynomiálnom čase na teoretickom modeli nedeterministického počítača, tzv. nedeterministickom Turingovom stroji, NTS. NTS si je možné predstaviť napríklad ako počítač, ktorý môže v každom kroku rozvetvovať vlákno výpočtu na viacero nezávislých vlákien s vlastnými dátami, po každom kroku tak znásobovať počet paralelne vykonávaných vlákien a po n krokoch mať spustených exponenciálne k n nezávislých vlákien. Pre vyriešenie problému pritom stačí, aby výsledok vypočítalo úspešne iba jedno vlákno.
Počítač, ktorý by počítal ako NTS, zatiaľ nevieme zostrojiť. Krokom týmto smerom sú tzv. kvantové počítače, ani tieto ale pre niektoré zákonitosti platné v ich konštrukcii priamo nezodpovedajú NTS. Zároveň zatiaľ nevieme, či všetky NP problémy je možné na kvantových počítačoch vypočítať v polynomiálnom čase.
NP-úplné problémy
Medzi problémami typu NP hrajú dôležitú úlohu tzv. NP-úplné problémy. Problém je NP-úplný, ak je typu NP a zároveň je naňho možné pretransformovať akýkoľvek NP problém prerobením jeho vstupov dostatočne rýchlo, v polynomiálnom čase.
NP-úplné problémy sú tak tými najťažšími problémami typu NP. V prípade, že by sme pre ľubovoľný NP-úplný problém našli polynomiálny algoritmus, vedeli by sme v polynomiálnom čase riešiť každý NP problém v najhoršom transformáciou na tento NP-úplný problém.
V súčasnosti je o viac ako troch tisíckach dôležitých problémov respektíve algoritmov z mnohých oblastí dokázané, že sú NP-úplnými. Sú nimi napríklad mnohé optimalizačné problémy každodenne využívané v praxi, napríklad problém obchodného cestujúceho, ofarbovanie vrcholov grafov.
O dvoch základných problémoch dôležitých v kryptografii a využívaných v algoritmoch s verejnými kľúčmi, faktorizácii čísel na súčin prvočísel a hľadaní diskrétneho logaritmu, ale nie je dokázané, že sú NP-úplnými.
P vs NP
Zrejme najdôležitejším nevyriešeným problémom v informatike je práve otázka vzťahu tried problémov typu P a NP. Zároveň ako na jediný problém z informatiky je za vyriešenie tohto problému vypísaná odmena Millenium Prize vo výške jedného milióna dolárov.
Každý problém typu P je automaticky problémom typu NP, keď vyriešiť problém v polynomiálnom čase automaticky znamená byť schopný overiť riešenie v polynomiálnom čase.
Intuitívne by mohol mať NTS väčšiu silu ako klasický deterministický počítač a mohol by byť schopný v polynomiálnom čase vypočítať aj zložitejšie problémy ako klasický počítač. Zatiaľ, neberúc do úvahy Deolalikarov ešte neobhájený dôkaz, sa ale nepodarilo dokázať, že je tomu tak a teda existujú problémy typu NP, ktoré nie sú typu P a teda ich určite nie je možné vypočítať na klasických počítačoch v polynomiálnom čase.
Väčšina vedcov predpokladá, že P != NP a teda takéto problémy existujú. Nezanedbateľná časť sa ale zatiaľ s istotou neprikláňa k ani jednej možnosti a len veľmi malá časť si myslí, že P = NP.
Čo by znamenalo P = NP
Ak by platilo P sa rovná NP a teda každý problém z NP by bolo možné vypočítať na klasickom počítači v polynomiálnom čase, znamenalo by to množstvo pozitívnych aj negatívnych dôsledkov.
Pozitívnym dôsledkom by bol poznatok, že všetky aj ťažké často v praxi využívané problémy typu NP sa dajú vypočítať v polynomiálnom čase. Dôkaz platnosti P = NP by ale nemusel dávať návod ako počítať ťažké problémy v polynomiálnom čase a algoritmus by bolo potrebné rovnako ako doteraz hľadať jednotlivo.
Ani polynomiálny algoritmus zároveň nemusí zabezpečiť pre vstupy, pre ktoré sa jednotlivé problémy bežne počítajú, rýchlejší výpočet ako umožňujú súčasné algoritmicky menej optimálne nepolynomiálne algoritmy. Stupeň polynómu, koeficienty a tak počet krokov totiž môžu byť tak vysoké, že pre bežné vstupy by polynomiálny algoritmus potreboval väčší počet krokov.
Veľmi nepríjemným dôsledkom P = NP by bola vypočítateľnosť faktorizácie čísiel a diskrétneho logaritmu v polynomiálnom čase. To by znamenalo, že napríklad pre algoritmy s verejným kľúčom RSA, DSA, DH by bolo možné z verejného kľúča nájsť v polynomiálnom a teda vysoko pravdepodobne dostatočne krátkom čase privátne kľúče. Podstatná časť súčasnej kryptografie by tak prestala fungovať a mať zmysel.
Opäť by ale potvrdenie platnosti P = NP nemuselo znamenať, že by bolo možné hneď nájsť polynomiálne algoritmy pre tieto dva problémy alebo že by bolo možné nájsť polynomiálne algoritmy rýchlejšie ako súčasné algoritmy. Vysoko pravdepodobne by ale v každom prípade po potvrdení P = NP musela kryptografia okamžite začať prechádzať na nové algoritmy.
Čo by znamenalo P != NP
Ak by sa dokázala nerovnosť medzi P a NP, samotné dokázanie tohto vzťahu by nemalo také vážne dôsledky ako v prípade dokázania P = NP.
Jediným priamym dôsledkom by bolo potvrdenie, že žiadny NP-úplný problém 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. Dôkaz P != NP by tak neznamenal, že tieto dva problémy sa určite nedajú riešiť v polynomiálnom čase ani že sa určite dajú riešiť v polynomiálnom čase.
Stav Deolalikarovho dôkazu
Pokus o dôkaz platnosti P != NP od Vinaya Deolalikara má pomerne náročnú konštrukciu, ktorá sa vymyká doterajším smerom dokazovania P != NP.
V uplynulom týždni bolo v dôkaze ale už objavených viacero problémov, z ktorých sa minimálne jeden javí ako závažný a pravdepodobne neodstrániteľný. Objavené problémy zhŕňa Richard J. Lipton, viacero odborníkov sa vyjadruje k celkovej správnosti dôkazu zatiaľ skepticky.
Deolalikar v reakcii ale avizoval úpravu dôkazu, ktorá má tieto problémy vyriešiť respektíve obísť. Kedy by mala byť k dispozícii nová verzia zatiaľ neoznámil.
Platí podľa Vás P != NP alebo P = NP? (hlasov: 437) 
Najnovšie články:
inzercia
![]()
Diskusia:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
pekny clanok
Od: P != NP a čo P = NP
|
Pridané:
17.8.2010 0:57
pekny clanok :)
|
| |
Re: pekny clanok
Od: aqwer
|
Pridané:
17.8.2010 8:51
Suhlasim, aspon som si to zopakoval zo skoly... Ale myslim ze ak niekto nechapal, tak nepochopi ... :)
|
| |
Re: pekny clanok
Od: mr.ch
|
Pridané:
17.8.2010 11:28
ja som ten minuly clanok moc nechapal, ale tento uz asi trocha ano... moj nazor je taky, polemizovat o P a NP je relativne vzhladom na cas - obdobie. nakolko z hladiska momentalnych dosahovanych vykonov sa nam moze zdat momentalny problem ako NP a za par rokov uz moze byt kategorizovany ako P. a preto dokazat rovnicu (alebo vyvratit) nebude az take lahke...
|
| |
Re: pekny clanok
Od: atde
|
Pridané:
17.8.2010 11:52
Ty tomu nechapes ani teraz.
|
| |
Re: pekny clanok
Od: someone
|
Pridané:
17.8.2010 14:43
podla mna aj tak bola prva sliepka nie vajce ;-)
|
| |
donate?
Od: ch.
|
Pridané:
17.8.2010 16:09
kde je tlacitko donate pre autora clanku? z tohto clanku by si mali brat priklad taki ako napr. gigel zo sme.
|
| |
Re: donate?
Od: waveeee
|
Pridané:
17.8.2010 16:55
podla mna sa najprv rodili prazivocichy bez škrupiny a postupne sa zacala vytvarat v tele samice obranna stena (z dvovodu nejakej nezelanej zmeny vonkajsieho prostredia). a tato stena sa evoluciou zdokonalila az natolko ze nakoniec nebolo nutne (alebo bezpecne) plod nechavat az po narodenie v tele samice. takze najprv bola prasliepka. mozno ze to bola este v tedy "jednobunkova sliepka" ale mozno ze ked raz zverejni ICQ vysledky svojej ankety, tak zmenim nazor =)
|
| |
Re: donate?
Od: ...........
|
Pridané:
30.8.2010 12:53
a podla mna je zase evolucia blbost :)
|
| |
Re: pekny clanok
Od: ground
|
Pridané:
18.8.2010 0:35
nie, vajce bolo skor.
ucia to na detskej univerzite UK :D
|
| |
Re: pekny clanok
Od: Hacik neregistrovany
|
Pridané:
18.8.2010 19:06
Ak berieme evolucnu teoriu ako pravdivu, tak vzhladom na to, ze jastery boli pred vtakmi, a kedze jastery rodia vacia, je jasne, ze prve bolo vajce. Ak by otazka znela, ci bolo prve slepacie vajce alebo sliepka, bolo by treba definovat pojmy. Osobne si myslim, ze aj tak bolo prve slepacie vajce a nie sliepka. To vsak koresponduje s tym, ako tieto pojmy vnimam ja. Pravda, ak si niekto tieto pojmy definuje inak, tak to moze byt aj inak.
|
| |
Re: pekny clanok
Od: ^_^
|
Pridané:
19.8.2010 1:03
Záleží od toho, či slepačie vajce definujeme ako vajce, z ktorého sa môže vyliahnuť sliepka, alebo ako vajce, ktoré zniesla sliepka.
|
| |
Re: pekny clanok
Od: Swampy
|
Pridané:
19.8.2010 8:59
Ak je evolucna teoria pravdiva, musela v historii existovat jasterica ktora znasala kuriatka a sakra dobre sa pred smrtou schovat, aby tento medziclanok nikto (nikdy?) nenasiel. A mozno tento medzidruh stale zije niekde hlboko v brazilskom pralese, ci v dutine v antarktide ci pod islandom pri zemskom jadre (Verne).
|
| |
Re: pekny clanok
Od reg.: Pjetro de
|
Pridané:
19.8.2010 13:30
Lenze vajce ma obe tie vlastnosti: aj ho zniesla sliepka a aj sa z neho moze vyliahnut sliepka (pokial na nom sliepka sedi a stara sa onho a vajco nie je na pancivi, alebo vydlabane pradatorom). Rozrasta sa to oboma smermi a za tychto predpokladov je to dokonca stelesny paradox. Za tychto predpokladov prva nemohla byt ani sliepka a ani vajce !!! T.j. jeden z tych predpokladov v minulosti nemohol platit (logicka uvaha). Takze bud
1A) existovali vajcia, kt. nezniesla ziadna sliepka a z ktorych sa mohli vyliahnut mlade sliepky uz so schopnostou znasat vajcia
1B) existovali vajcia, kt. zniesla sliepka a z ktorych sa nemohli vyliahnut mlade sliepky
2A) existovali sliepky, ktore sa nevyliahli z vajca ale boli schopne znasat vajcia
2B) existovali sliepky, ktore sa vyliahli z vajca ale neboli schopne znasat vajcia
|
| |
Re: pekny clanok
Od reg.: Pjetro de
|
Pridané:
19.8.2010 13:30
Ako sa s tym zahrala evolucia a ako to bolo predtym mi je tazko povedat, avsak cele je to len o nahodnej mutacii v jednej generacii a na jednom mieste. Ak sa mutacia ukazala velmi vyhodna, jedinci s touto mutaciou postupne globalne vytlacili jedincov bez nej.
|
| |
Re: pekny clanok
Od: Oryg
|
Pridané:
25.8.2010 0:28
A kde kua ste nechali Kohuta ?
Niekto tu promiskuitnu slepicu musel predsa nabuchat.
|
| |
Re: pekny clanok
Od: Mumsito
|
Pridané:
17.8.2010 14:18
Ten problm bude vzdy NP. Jediny rozdiel bude v rychlosti jeho vypocitania.
|
| |
Re: pekny clanok
Od: Miso V.
|
Pridané:
17.8.2010 14:42
Nemas pravdu.
|
| |
Re: pekny clanok
Od: : Pjetro de
|
Pridané:
17.8.2010 18:51
sorry, ale vobec nerozumies ani len myslienke
|
| |
Re: pekny clanok
Od reg.: gandor
|
Pridané:
30.8.2010 16:48
Toto nikdy nenastane. To ze je algoritmus exponencialny znamena, ze cas potrebny pre jeho vypocitanie sa zvysuje OMNOHO rychlejsie, ako polynomialny. Vobec to neznamena, ze ten polynomialny je za kazdych okolnosti rychlejsi...
Pre jednoduchost sa to da vysvetlit ako ze polynomialny algoritmus je stihacka a exponencialny algoritmus je bezec. Ale ked bezec ma prejst 10m vzdialenost, tak to stihne rychlejsie ako stihacka, ktoru treba pred startom skontrolovat ci funguje, nastartovat a podobne...
Ale ked uz sa ma prejst 1000km, tak uz to ta stihacka stihne asi o nieco rychlejsie a je jedno, ze si tych bezcov postavil na trat 10 (to by mohol predstavovat ten tvoj pokrok a zvysenie vypoctu pocitacov), ktory si ten usek rovnocenne medzi sebou podelia...
No a v reali je ten rozdiel dokonca este vecsi...
|
| |
Re: pekny clanok
Od: szaga2
|
Pridané:
17.8.2010 17:12
pekny clanok :)... Ano pekny len ja mu vobec nerozumiem. A podla mna dalsich 99% ich je na tom ako ja. Ani som nehlasoval lebo tam nedal pan redaktor odstavec comu by som robumel.....
|
| |
Problémy typu P
Od: didoa
|
Pridané:
17.8.2010 1:10
myslim ze "triediť" v tom odseku malo byt spravne "usporiadať"
:P
inak pekny clanok
|
| |
Re: Problémy typu P
Od: _PM
|
Pridané:
17.8.2010 9:43
Ano, ak autor myslel "triedenim" zoradenie postupnosti, tak je spravne "usporiadanie". Triedit mozno hrusky od jablk. Postupnosti sa usporiadavaju.
|
| |
Re: Problémy typu P
Od: chellynka
|
Pridané:
17.8.2010 13:53
v informatike sa pouziva "triedenie" ako odborny nazov. algoritmy su triediace, nie usporiadavacie. takze akokolvek sa vam to zda cudne, je to tak spravne.
|
| |
Re: Problémy typu P
Od: didoa
|
Pridané:
17.8.2010 13:59
triedit je odborny vyraz pre triedenie - zaradenie prvkov do tried - do mnozin s nejakou spolocnou charaktertistikou (napr. jablko a hruska = ovocie a mrkva = zelenina)
usporiadavanie je zase odborny vyraz pre operaciu, kde sa meni poradie prvkov mnoziny tak, ze medzi kazdymi dvoma prvkami vedla seba plati nejake pravidlo (napr. prvok1 je mensi/rovny ako prvok2)
|
| |
Re: Problémy typu P
Od: chellynka
|
Pridané:
17.8.2010 14:11
a toto mas, prosim ta, odkial? ako sa v informatike nieco triedi do mnozin so spolocnou charakteristikou?
este raz: na zoradenie prvkov sa pouzivaju TRIEDIACE algoritmy, obcas sa este vyskytne nazov "algoritmy usporiadania", ale pouziva to malokto, zabehany je skratka nazov triedenie, vzniklo to z prekladu "sort" z anglictiny. castokrat sa stane, ze pri vytvarani noveho slova sa pouzije nie prilis stastny preklad, ale ak sa to uz raz zazije medzi ludmi, je tazke to zmenit.
|
| |
Re: Problémy typu P
Od: _PM
|
Pridané:
17.8.2010 14:10
Ceska wikipedia to ma hned v prvej vete. Slovensku budem ignorovat vzhladom na to, ze ten clanok na SK wiki je len atrapa. Oznacenie sa ujalo z doslovneho prekladu "sorting". Pamatam si ako nas na to niekolko krat upozornovali na skole pocas semestra o algoritmoch (cesky řazení). Logicky k tomu mozno dojst (tak ako som pisal v komentari hore). To, ze je zauzivany neznamena ze aj spravny.
|
| |
Re: Problémy typu P
Od: chellynka
|
Pridané:
17.8.2010 14:28
ano v cesku sa to viac menej uspesne snazia presadit (ocividne aj pomocou wikipedie, co nie je ziadny odborny zdroj a v tomto pripade ani nema relevantne odkazy), ale este stale sa triedenie pouziva. kazdopadne by som nikoho nepopotahovala za to, ze pouzil vyraz, ktory sa v odbornych (aj menej odbornych) kruhoch bezne pouziva, hoc nie je na 100% presny. maximalne sa na tom chyti niekto, kto vobec nevie, o com je rec.
|
| |
Anketa
Od: Slavius
|
Pridané:
17.8.2010 7:45
Anketa typu "Platí podľa Vás P != NP alebo P = NP?" je hodna Tipos-u a nie DSL.sk...
|
| |
Re: Anketa
Od reg.: foobar0
|
Pridané:
17.8.2010 10:15
Ale aký Tipos, prosím ťa. Ja som si to overil na papieri predtým, než som zahlasoval.
|
| |
analyza zlozitosti algoritmov
Od: deepblue
|
Pridané:
17.8.2010 8:54
toto sme sa na aze ucili s Dukom, tak apson som si zopakoval :)
|
| |
Re: analyza zlozitosti algoritmov
Od: jjjjj
|
Pridané:
17.8.2010 9:31
my tiez :)
|
| |
Re: analyza zlozitosti algoritmov
Od: medooo
|
Pridané:
17.8.2010 13:23
precital som, ze si sa to ucil na azet-e :) az ma zamrazilo:-D
|
| |
P = NP
Od reg.: Spike
|
Pridané:
17.8.2010 8:57
Autor ankety a vlastne celého článku si musel dačo predtým šľahnúť :)
|
| |
čo to je?
Od reg.: Flety
|
Pridané:
17.8.2010 8:59
Čo to je ten polymoniálny čas?
|
| |
Re: čo to je?
Od: chellynka
|
Pridané:
17.8.2010 14:33
je to funkcia, ktora vyjadruje cas potrebny na vyriesenie nejakeho problemu, ktory pracuje s N prvkami, pricom tato funkcia sa da zapisat ako nejaky polynom s premennou N. co je polynom, si vygoogli.
|
| |
konečne som to aspoň trochu pochopil
Od: athelas
|
Pridané:
17.8.2010 9:17
toto je asi prvý článok, ktorý celú tú problematiku približuje takmer ľudskou rečou, vďaka!
|
| |
veľká pochvala
Od: hupapo
|
Pridané:
17.8.2010 9:44
klobúk dole autorovi článku, dobre vysvetlené. nikdy predtým som sa o tom neučil a pochopil som to.
|
| |
Re: veľká pochvala
Od: oraJaro
|
Pridané:
18.8.2010 7:54
Tak nam to vysvetli, aspon zistism, ci tomu naozaj chapes. :D
|
| |
Pekne
Od: adsdf
|
Pridané:
17.8.2010 9:54
Pekne napisane, vdaka za zopakovanie :)
|
| |
jednoduche riesenie
Od: asdfff
|
Pridané:
17.8.2010 10:33
Neviem co s tym tolko stresuju. Nech poziadaju Chucka Norrisa aby povedal, ze ako to ma byt a tak to aj bude :).
|
| |
Re: jednoduche riesenie
Od: mr.ch
|
Pridané:
17.8.2010 11:33
chuck norris: je uplne jedno ci P = NP alebo P != NP dolezite je (P*NP)*∞ < CuckNorris
|
| |
Re: jednoduche riesenie
Od: mr.ch
|
Pridané:
17.8.2010 11:34
∞ - toto mal byt znak NEKONECNA - dsl to htmlspecialchars-uje.... alebo respektive htmlentitiuje...
|
| |
Re: jednoduche riesenie
Od: 0dee
|
Pridané:
18.8.2010 13:56
Ja som za zasmial viac na mene Cuck ako na rovnici :)
|
| |
Re: jednoduche riesenie
Od: alt.x
|
Pridané:
17.8.2010 20:15
Jemu je to jedno, lebo dokaze vsetky vypoctove problemy riesit v konstantnom case.
|
| |
Pošli kvety
Od: vietor
|
Pridané:
17.8.2010 10:36
Este tu aspon 10siati napiste aky bol super ten clanok.
Ale bol super. :D
|
| |
P vs NP pre každého
Od: Peter.Ke
|
Pridané:
17.8.2010 15:15
prišiel som, klikol som, prečítal som, nepochopil som.
Takže ešte raz a pekne od začiatku. ÁÁÁÁÁ ako auto. Mama má Evu. Eva má mamu...
|
| |
Re: P vs NP pre každého
Od: precoja?
|
Pridané:
17.8.2010 19:34
Pekne od zaciatku..to sa prihlas na fmfi, staci bc studium.
|
| |
Čo si o tom myslia informatici
Od: Stevko_
|
Pridané:
17.8.2010 16:45
Tu je pekné zhrnutie výsledkov podobnej ankety ako je pri článku, kde sa otázky okolo P=?NP pýtali informatikov: http://www.cs.umd.edu/~gasarch/papers/poll.pdf
|
| |
asdasd
Od: aaaaaaaaa
|
Pridané:
17.8.2010 17:55
V akej triede zlozitosti je dokazanie, ci P = NP alebo P != NP?
|
| |
Re: asdasd
Od: bbbbbbb
|
Pridané:
17.8.2010 19:32
Zaujimava otazka :).
|
| |
Re: asdasd
Od reg.: Pjetro de
|
Pridané:
17.8.2010 20:02
Neviem ci otazka dava zmysel a ci je samotny dokaz algoritmizovatelna uloha. Potom by bola algoritmizovatelna uloha aj samotne ludske myslenie a to uz suvisi s umelou inteligenciou. V konecnom dosledku ci je mozne jednoducho algoritmizovat ludske myslenie.
|
| |
Re: asdasd
Od reg.: Pjetro de
|
Pridané:
18.8.2010 8:04
To sme vsak vo svete metajazyka a metainformacii (metaifnormacia je informacia o informacii - napr. Exif data v hlavicke fotiek informuju o tom, ako, kedy, s cim, za akych podmienok a nastavini bola urobena samotna fotka a samotne data tvoriace tuto fotku nasladuju az za touto hlavickou).
Podobne je to s godelovskou neurcitostou axiomatickych systemov. V istom axiomatickom systeme logicky a axiomovo tak bohatom ako napr. system teorie mnozin, existuju tvrdenie ktore sa nedaju ano dokazat ani vyvratit - su nerozhodnutelne. Ak priberieme nove potrebne axiomy, tieto tvrdenia uz zmiznu - daju sa principialne dokaz ci vyvratit, samozrejme to neznamena ze taky dokaz uz niekto nasiel, len je principialne zrejme ze dokaz v systeme s novymi axiomami uz existuje. A to je defacto metadokaz, dokaz o dokaze, t.j. dokaz, ze sa nieco da/neda vobec dokazat! Bez toho ze by niekto samotny dokaz poznal.
|
| |
Re: asdasd
Od reg.: Pjetro de
|
Pridané:
18.8.2010 8:10
Este som zabudol pripomenut, ze s pribratim dalsich axiom do systemu sa objavia nove dalsie nerozhodnutelne tvrdenia, ktore sa nebudu dat ani dokazat ani vyvratit a sme tam kde sme boli pred rozsirenim systemu.
|
| |
Re: asdasd
Od reg.: Pjetro de
|
Pridané:
18.8.2010 8:12
Inak defacto povedane, co vlastne dokazal Kurt Godel svojimi vetami o neurcitosti? Ze nech sa znazime akokolvek, VZDY budu v poznani existovat biele miesta!
|
| |
Re: asdasd
Od reg.: Pjetro de
|
Pridané:
18.8.2010 8:07
Napr. v sucasnom axiomatickom systeme teorie mnozin je dokazane (metadokazom), ze existencia nekonecnej mnoziny s miohutnostou vacsou ako alef0 a sucasne mensot ako muhutnost kontinua, tak existencia takej nekonecnej mnoziny je nerozhodnotelna. T.j. bolo "metadokazom" dokazane, ze jej existencia sa neda ani dokazat ani vyvratit.
|
| |
Re: asdasd
Od: ^_^
|
Pridané:
19.8.2010 1:13
Ak taký dôkaz existuje, tak v triede zložitosti O(1) na DTS. Problém rozhodnutia, či daný text je dôkazom P != NP, resp. P = NP, je podľa mňa nerozhodnuteľný.
|
| |
clanok
Od reg.: Pjetro de
|
Pridané:
17.8.2010 18:59
Po eskapade minulotyzdnoveho clanku informujuceho o tejto problematike recou skript (mne osobne to nevadilo, ale takych bola velmi vyrazna minorita), je tento clanok o dost ludskejsi. Musim pochvalit redakciu, ktora bud zamestnala matematika, kryptologa, alebo rozhladeneho absolventa informatiky v zalube o teoreticku informatiku.
Samozrejme neda sa vyhnut primitivnej definicii polynomickej ci exponencialnej funkcie, co je ucivo absolutner kazdeho matematickeho ci aj vseobecneho gymnazia. Ale aj tak definicia polynomickej a exponencialnej funkcie, pre mna primitivita, pre niekoho v zivote nevidena a stale nepochopitelna vec. Celkovo vsak clanok mozno hodnotit vyrazne pozitivne :-)
|
| |
comment
Od reg.: Pjetro de
|
Pridané:
17.8.2010 19:15
Podľa alternatívnej definície je problém typu NP, ak je možné správnosť riešenia problému overiť v polynomiálnom čase, hoci výpočet nemusí byť možné uskutočniť v polynomiálnom čase ---------- casto totiz overenie riesenia problemu je neporovnatelne jednoduchsie ako najst riesenie samotne a jedna sa o tzv. efekt padacieho mosta, resp. takmer-jednosmerne operacie. Overit spravnost faktorizacie zlozenych cisel na sucin niekolkych prvocisel ich vynasobenim je ako padnut do hlbokej priekopy s kolmymi smyklavymi stenami, priekopy zaplnenej vodou, ktora oddeluje hrad. To sa stane velmi lahko. Samotna faktorizacia je vsak ako dostat sa z tejto priekopy s hlbokymi, kolmymi a klzkymi stenami potom, co nam na prsty padne padaci most a odsekne nam ich. Nie je to nemozne, avsak neporovnatelne tazsie ako do priekopy padnut.
|
| |
comment
Od reg.: Pjetro de
|
Pridané:
17.8.2010 19:21
Ani polynomiálny algoritmus zároveň nemusí zabezpečiť pre vstupy, pre ktoré sa jednotlivé problémy bežne počítajú, rýchlejší výpočet ako umožňujú súčasné algoritmicky menej optimálne nepolynomiálne algoritmy. Stupeň polynómu, koeficienty a tak počet krokov totiž môžu byť tak vysoké, že pre bežné vstupy by polynomiálny algoritmus potreboval väčší počet krokov ---------- da sa dokazat ze: ku kazdej rastucej exponencialnej funkci f(x) = a^x s lubovolne malym zakladom "a" sprava blizkym k 1, existuje x0 take, ze pre vsetky x vacsie ako x0 je tato exponencialna funckia vacsia ako lubovolna polynomicka funkcia n-teho stupna v bode x0, t.j. f(x0) = a(n)*x0^n + a(n-1)*x0^(n-1) + a(n-2)*x0^(n-2) ... + a(3)*x0^3 + a(2)*x0^2 + a(1)*x0 + a(0) s lubovolnymi koeficiantami. Samozrejme ide o to, ako daleko je to x0.
|
| |
Re: comment
Od reg.: gandor
|
Pridané:
30.8.2010 16:36
Pokusim sa trocha poludstit: polynomialny algoritmus moze ten problem vypocitat rychlejsie pre nejaky velmi velky vstup.
Co je nam to ale platne, ked taky velky vstup v praxi nemusime nikdy potrebovat...
Ci nastane tento efekt, kedy je exponencialny algoritmus v praxi vyhodnejsi zalezi od:
1, velkosti vstupnych dat
2, ako male su koeficienty v exponenialnom algoritme
3, aky velky je stupen polynomu
4, ako velke su koeficienty v polynomialnom algoritme
Zhrnute dokopy na priklade:
Majme vstup o 10 prvkov.
Exponencialny algoritmus 2^N (kde N predstavuje pocet prvkov na vstupe = u nas 10).
Polynomialny algoritmus N^4
V tomto pripade exponencialny algoritmus musi vykonat 2^10=1 024 operacii.
Polynomialny 10^4=10 000 operacii. Polynomialny algoritmus by teda isiel dlhsie.
Pri zvecseni vstupu na N=20 nam da polynomialny algoritmus 160 000 operacii ALE exponencialny dava 1 048 576 operacii...
|
| |
comment
Od reg.: Pjetro de
|
Pridané:
17.8.2010 19:21
Inak povedane: lubovolna rastuca exponencialna funkcia po istom case (v istej vzdialebnosti napravo od nuly) bude mat vascie funkce hodnoty (bude nad grafom) ako lubovolna polynomicka funckia. Avsak pred tymto zlomom moze byt situacia opacna, ako podotyka clanok. Existncia tohto zlomu je casto uplne nepochopitelna, napr. ak si vykreslime grafy funckii f1(x) = 1,00000000001^x a f2(x) = x^10000000000, sotva by niekto niekedy tipoval, ze graf f1 bude niekedy nepredstavitelne daleko vpravo na osi x-ovej za cislo x0, nad grafom f2.
Cislo x0 moze byt tak velke (avsak konecne), ze sa vymyka akejkolvek konvencii a akejkolvek predstave aj najerudovanejsich matematikov o velkych cislach a bolo by potrebne nasadit vedomosti o vekych cislach (napr. tetraciu, kvintaciu a dalsie vyssie operacie zapisane napr. pomocou Ackermannovej rekurentneej funkcie ci Knuthovho šípkoveho zápisu, dalej Steinhausov polygonický zápis, Moserov-Steinhausov polygonický zápis ci Conwayov reťazový šípkový zápis).
|
| |
Re: comment
Od reg.: Pjetro de
|
Pridané:
17.8.2010 19:56
Darmo je, exponenialna funkcia je velka svinuch, ktorej sa boja aj derivacie - (n+1)vou derivaciou lubovolneho polynomu n-teho stupna totiz dostavame nulu, ale (n+1)vou derivaciou specialnej exponencialnej fukcie e^x dostavame stale tu istu funckiu, dokonca v pripade vseobecnej exponencialnej fukcie a^x dostavame stale len zlozitejsie vyrazy.
Exponencialna fukncia je taka svina, ze su o nej v matematickej obci zname aj vtipy :-)
|
| |
Re: comment
Od: ^_^
|
Pridané:
19.8.2010 1:17
ten o derivácii e^x podľa y? :)
|
| |
Re: comment
Od reg.: Pjetro de
|
Pridané:
19.8.2010 7:30
jo :-)
dalsi vtip je: "nech epsylon je zaporne", ale nepochopi to nikto, kto nemal matematicku analyzu
dalej existuju aj matematicke rozpravky, tusim ich aj niekde mam, napr. ako stary mudry integral slubil polovicu definicneho oboru tomu, kto skroti zlu derivaciu. do boja sa prihlasili vseliake funkcie, ale vzdy po nich ostali len nuly. dobrovolnici sa potkynali o korene algebraickych rovnic, ktore v bojoch tiez neuspeli, no samozrejme ma to nakoniec happyend ... a takych rozpravok je tusim asi 5-6 :-)
|
| |
nechapem
Od: zolike
|
Pridané:
17.8.2010 19:46
bud som nechapavy clovek alebo potom debil :D lebo stale tomu nechapem o com je rec :D
|
| |
Re: nechapem
Od: martinc
|
Pridané:
17.8.2010 22:29
Neboj sa ani ja..asi sme obycajni ludia a nie kadejaki nerdi co im toto beha po rozume.. :-)
|
| |
...som asi za kopec...
Od reg.: romeo1987
|
Pridané:
17.8.2010 23:06
Som jednoznačný idiot, keď to nechápem? Alebo to je naozaj až za kopec logiky bežného smrteľníka?
|
| |
Re: ...som asi za kopec...
Od reg.: Pjetro de
|
Pridané:
18.8.2010 7:52
Vela zalezi aj od vysvetlenia. Ak ma program linearnu algoritnmicku zlozitost, tak pocet krokov potrebnych na vyriesenie problemu je priamo umerny mnozstvu vstupnych dat.
Veeeeeeeeeeelmi zjednodusene (nezodpoveda definicii linearnej funkcie y = ax+b): napr. ak program nakrmime poctom "n" dat, tak po "n" krokoch mame vysledok. Ak nabachame do programu "2n" vstupnych dat, na vypocet potrebujeme "2n" krokov ... atd az vseobecne "kn".
Napr. program potrebuje data v podobe 250 znakov no a po 250tich krokoch mame vysledok. Ak vsak vstupne data bude 500 znakov, potrebujeme uz 500 krokov na ukoncenie vypoctu. Ak program bude na zaciatku nacitavat a operovat (spracuvat 10 000 znakov, ktore budu tvorit vstup), potrebujeme az 10 000 krokov programoveho postupu na ukoncenie vypoctu (behu programu).
|
| |
Re: ...som asi za kopec...
Od reg.: Pjetro de
|
Pridané:
18.8.2010 7:52
Ak by bola zavislost kvadraticka a nie linearna (podobne je to zjednodusene a nezodpoveda to celkom kvadratickej zavislosti vo vseobecnom zmysle), tak zatialco pri vstupe 1 znak potrebujeme 1 krok na vypocet, pri velkosti vstupu 25 znakov potrebujeme az 25^2 = 625 krokov vypoctu! No a 25 a 625 je nenaaaaapadny rozdil. Pri velkosti vstupu 50 znakov (program nacita a bude oparovat s 50 znakmi), postup s kvadratickou zlozitostou potrebuje az 50^2 = 2500 krokov! A zase 50 a 2500 je rozdiel. Pri 10 000 spracuvanych znakoch to bude pri kvadratickej zlozitosti az 100 000 000 potrebnych krokov a opat 10 000 krokov a 100 000 000 krokov je rozdiel.
Pr kubickej zlozitosti je to este horsie, napr. pri 25 znakoch potrebujeme az 25^3 = 15625 krokov vypoctu, pri 50 spracuvanych znakoch az 125000 krokov no a pri 10 000 znakoch az 1 000 000 000 000 krokov.
|
| |
Re: ...som asi za kopec...
Od reg.: Pjetro de
|
Pridané:
18.8.2010 7:52
Dalej ak predpokladame, ze na jeden krok vypoctu na istom pocitaci v istom case potrebujeme konstantny cas, tak je zrejme, ze ak napr. spracovanie 50 znakov trva pri linearnej zlozitosti 50 krokov a pri kvadratickej 2500 krokov a kedze pocet potrebnych krokov je 50-nasobny, tak aj cas potrebny na vypocet je pri kvadratickej zlozitosti 50-nasobny.
Exponencialna funkcia je ale este ovela vacsia svina. Ak je zlozitost vypoctoveho algoritmu umerna napr. 2^x, tak pri 25 spracuvanych znakoch to mame 2^25 = 33554432 potrebnych vypoctovych krokov ale pri 50tich spracuvanych znakoch az 2^50 = 1125899906842624 potrebnych krokov, t.j. (2^25 = )33554432-nasobne viac.
|
| |
Re: ...som asi za kopec...
Od reg.: Pjetro de
|
Pridané:
18.8.2010 7:52
T.j. ak zmenime pocet spracuvanych udajov z 25 na 50, tak pri linearnej zlozitosti nam pocet potrebnych krokov (no laicky povedzme ze aj potrebny cas vypoctu) stupne 2nasobne podobne ako pocet vstupnych dat. Podoha a relax. Pri kvavdatickej zlozitosti nam pocet potrebnych krokov stupne (50^2)/(25^2) = 25^2 = 625nasobne. To uz je blbe. No a pri exponencilnej zlozitosti zo zakladom 2 je to ciste svinstvo, tam totiz pri 2nasobnom zvyseni poctu spracuvaynch dat z 25 na 50 stupna pocet potrebnych krokov a teda aj caova narocnost az 33554432nasobne!
|
| |
Re: ...som asi za kopec...
Od: precoja?
|
Pridané:
18.8.2010 16:13
Zavisi od veku, vzdelania a tak. Ako FIT/FEIkar by si to mal pochopit, pokracovat radsej nebudem aby sa niekto neurazil :D.
|
| |
planeta
Od: dghlkghlsd
|
Pridané:
18.8.2010 0:06
A predsa sa točí :D
(inak pekny clanok len mu akosi nechapem :D)
|
| |
hmmmm
Od: meno priezvisko
|
Pridané:
18.8.2010 9:31
darmo, je to mačka.
|
| |
P ?= NP
Od: iKEBAB
|
Pridané:
18.8.2010 10:32
Cize Skynet sa blizi ?
|
| |
super
Od: ondrej nezaregistrovany
|
Pridané:
18.8.2010 14:04
naozaj pekne a zrozumitelne napisane... +1b autorovi
|
| |
Nebol tento clanok v casopise Tyzden minuly tyzden?
Od: truhlik73
|
Pridané:
18.8.2010 14:10
Nebol tento clanok v casopise Tyzden minuly tyzden?
|
| |
Ďakujem
Od: livthomas
|
Pridané:
18.8.2010 20:21
Ďakujem autorovi tohto článku. Konečne mi niekto zrozumiteľne vysvetlil, o čo v tom probléme ide. ;)
|
| |
NTS == DTS
Od: zippy
|
Pridané:
20.8.2010 10:10
Intuitivne je este mozne ze NTS je silnejsi nez DTS. Ale v teoretickej informatike ma NTS rovnaku vyjadrovaciu silu ako DTS. Zavedenim nedeterminizmu nezvysime schopnost turingovych strojov prijimat jazyky!
|
| |
P <> NP
Od: M...
|
Pridané:
20.8.2010 14:53
Pekny clanok, vdaka. Ujo Galan by bol hrdy!
|
| |
Zaujimave
Od: AG.
|
Pridané:
23.8.2010 0:49
Zaujimave. No, myslim ze s tym ako dlho sa dnes pocitaju prvocisla, pi a podobne veci, tak neviem aky optimista moze verit v P = NP.
Ale jedno ma zaujima, je toto cisto informaticky problem? Lebo ako sa tu hovori o sucinoch prvocisel a podobne, neznamenalo by (HYPOTETICKY!) dokazanie P = NP aj nove konstrukcie v matematike? Ted ak je dnes nejaky matematicky problem nevypocitatelny v P, a dokazalo by sa ze P = NP, nemalo by to spatny dopad aj na ten prvotny matematicky problem?
Len ma zaujima, ci sa informatici zaoberaju aj tymto alebo ide cisto o IT problem.
|
| |
Re: Zaujimave
Od: precoja?
|
Pridané:
23.8.2010 4:05
To ako dlho sa DNES pocitaju prvocisla ma s P,NP len velmi malo. Ano, ak mas algoritmus z NP a najdes rychlejsi z P, vyhral si, ale s rychlostou CPU to nic nema. Teoreticka informatika rata na kroky vypoctu, nie na cas.
Co sa druhej veci tyka, je to zle polozena otazka. Laicky to matematika neriesi, matematici dokazuju vztahy, vety, vzorce atd. Prave informatika riesi zlozitost nasobenia, faktorizacie..., snazi sa najst lepsie algoritmy (a dokazuje vztahy, vety, vzorce :) ).
Ale informatika je aplikaciou matematiky, preto zle polozena otazka. Nemyl si informatiku s IT!
|
| |
No pekne
Od: Jozko z lazov
|
Pridané:
1.9.2010 22:35
Len pripomienka: mozno tento clanok je pre niekoho zaujimavy, ale pre 99% populacie je dolezity asi ako nesmrtelnost chrusta. Venujte sa zaujimavejsim clankom pre LUDI.
|
| |
Re: No pekne
Od reg.: antitalent15
|
Pridané:
4.9.2010 12:25
to mozes napisat o akomkolvek clanku, ze nie je pre vsetkych rovnako dolezity. Radsej si si mal pripustit, ze tomu nerozumies. To predsa nie je hamba.
|
| |
Evolution
Od: Mepho
|
Pridané:
5.9.2010 0:30
Ak je evolucia pravdiva, tak sa to secko zacalo delenim buniek, prechadzalo sa dalej a dalej {odstepovanie} az to doslo k takej aktivite, ze ta cast co sa mala odstepit sa zacala od materskej casti diferencovat {tvorit plod,vajicko,pankharta} cize sliepka bola zrejme skor, aj ked sa to na sliepku nepodobalo respektive bolo skor vajce, pretoze sa to este na sliepku nepodobalo - vyberte si :D
Tak nejako nas to ucili, len mi do toho nezapada ta teoria ze clovek prechadza vyvojovymi stadiami ako embryo {ze mame chvost kery zakrpatie, blany na prstoch a pod}. Sa to dako mudro volalo len si uz nepamatam.
Takze, bolo vajce ci sliepka? :D
|
| |
Re: Evolution
Od reg.: Pjetro de
|
Pridané:
7.9.2010 12:16
precitaj si vysvetlenie evolucneho biologa na detskej univerzite:
http://mozgovna.pravda.sk /co-bolo-skor-vajce-alebo-sliepka-dnp- /sk-mzar.asp?c=A090808_232521_sk-mzar_p34
a zistis ...
|
| |
Re: Evolution
Od: ......
|
Pridané:
20.9.2010 12:29
Nic same od seba nevznikne ani nebude.... Poloz si kladivo na stol a uvidime ci za miliardu rokov bude z neho hydraulicky buchar .... Druhy vymieraju a nic nevznika ..... Kde je evolucia? Iba vramci jedneho druhu moze dochadzat k urcitym zmenam vramci hranic danych genetikou.... Novy druh podla nasich vedomosti a najnovsej vedy moze vzniknut umelym zasahom do genetickej informacie
|
| |
Re: Evolution
Od reg.: Pjetro de
|
Pridané:
7.9.2010 12:19
ako som pisal v komentari k tomuto clanku:
Pjetro de | Pridané: 19.8.2010 13:30
absolutne elementarnou (alebo aj sedilackou) logikou bez akejkolvek znalosti evolucnej biologie sa da zistit, ze musela nastat jedna z tych styroch moznosti, ktore som v prispevku vymenoval, 1A, 1B, 2A, 2B ...
clanocek na mozgovni vysvetluje, ze nastala moznost 1A
|
Pridať komentár
|
|
|
|
