Rus zverejnil program, ktorý by mal dokazovať P = NP

DSL.sk, 22.1.2011

Vladimir F. Romanov zo Štátnej univerzity v ruskom meste Vladimir tento týždeň zverejnil konštruktívny dôkaz a zároveň program implementujúci vyvinutý algoritmus, ktoré majú podľa Romanova potvrdzovať rovnosť tried zložitosti P a NP.

Problém P vs NP je stále otvorený problém informatiky s potenciálne vážnymi dopadmi aj na reálne aplikácie. P vs NP sme detailne popisovali v tomto článku.

Algoritmický problém je podľa jednej z alternatívnych definícií typu NP, ak je možné správnosť riešenia problému overiť dostatočne rýchlo, v tzv. polynomiálnom čase, vzhľadom na veľkosť vstupu na výpočtovom zariadení zodpovedajúcom spôsobom fungovania súčasným počítačom. Definícia nevyžaduje, aby samotné nájdenie riešenia pre daný vstup muselo byť možné uskutočniť tiež v polynomiálnom čase.

NP problémom je napríklad rozloženie čísla na súčin prvočísel. Správnosť riešenia vieme jednoducho overiť vynásobením vypočítaných prvočísel, nájsť tieto prvočísla pre dané číslo zatiaľ v polynomiálnom čase nevieme.

Problém P vs NP, problém rovnosti množín všetkých problémov typu P a typu NP, sa zaoberá otázkou, či každý problém typu NP nie je v skutočnosti aj typu P a teda či ho vieme dostatočne rýchlo, v polynomiálnom čase, aj riešiť, nielen overiť jeho riešenie. Alternatívou je, že existujú problémy typu NP neriešiteľné dostatočne rýchlo.

Romanov tvrdí, že dokázal rovnosť tried P a NP. Malo sa mu to podariť nájdením polynomiálneho algoritmu pre problém označovaný 3-SAT, ktorý je ale NP-úplný. Ak by tak naozaj bol 3-SAT problémom typu P znamenalo by to, že každý problém typu NP sa dá riešiť v polynomiálnom čase.

Romanov zároveň zverejnil aj reálnu implementáciu svojho algoritmu v jazyku Java, ktorá podľa neho rieši 3-SAT problém v čase rádovo m * n ^ 4, kde n je počet premenných a m počet podmienok.

V dôkaze Romanova, algoritme aj jeho implementácii bolo už objavených niekoľko problémov, zatiaľ ale nie je definitívne jasné, či sú neopraviteľne nesprávne. Kredibilite nepridáva ani informácia Romanova o existencii dôkazu už od roku 2002. Prečo nezverejnil dôkaz skôr nevysvetluje.

Zároveň nie je jasné, či by v prípade správnosti algoritmus priamo umožnil prakticky riešiť súčasné ťažké NP problémy s reálne používanými vstupmi vo výrazne lepšom čase ako je to možné teraz.

Dôkazov o nerovnosti P a NP respektíve rovnosti P a NP sa objavuje v poslednom období ročne až okolo desať. Naposledy si veľkú pozornosť získal v lete minulého roka dôkaz Vinaya Deolalikara z HP, ktorý dokázal opak ako Romanov, teda P sa nerovná NP. V jeho dôkaze bolo objavených viacero vážnych problémov, Deolalikar na svojej stránke avizoval a stále po viac ako štyroch mesiacoch avizuje prípravu opravenej verzie dôkazu.

Dokázanie nerovnosti P a NP by nemalo výrazné okamžité dôsledky, potvrdilo by ale nemožnosť počítať v polynomiálnom čase všetky NP-úplné problémy. Dôkaz rovnosti P a NP by naopak mal veľmi vážne dôsledky. Pre mnoho ťažkých a v súčasnosti neefektívne počítaných problémov by mohol poskytnúť aj priamy algoritmus rýchlejšieho výpočtu, minimálne by dal zmysel hľadaniu polynomiálnych algoritmov pre mnohé ťažké problémy.

Na druhej strane medzi NP problémami sú aj faktorizácia čísiel a diskrétny logaritmus, ktoré sú základom napríklad kryptografických algoritmov využívajúcich verejný kľúč RSA, DSA, DH. Potenciálna existencia polynomiálnych algoritmov pre tieto problémy by znamenala, že z verejného kľúča by bolo možné nájsť potenciálne v dostatočne krátkom čase privátne kľúče, bezpečnosť týchto algoritmov by tak musela byť považovaná minimálne výhľadovo za nedostatočnú a bolo by potrebné ich nahradiť.


Najnovšie články:



Diskusia:

Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: konecne anarchia | Pridané: 22.1.2011 15:52 Bodaj by to prasklo, zacne sa vo velkom lamat asymetricke sifry a nastane novy zlaty vek pre haxxorov Odpovedať Známka: -8.1 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: zeratul | Pridané: 22.1.2011 16:19 a to je k comu dobre? Odpovedať Známka: 2.6 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: wx2 | Pridané: 22.1.2011 17:27 Cau Momo :D Odpovedať Známka: 0.7 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: Lotor Agresor | Pridané: 23.1.2011 14:01 Čau miky mora Odpovedať Známka: -2.0 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: maaattttooo | Pridané: 22.1.2011 19:54 ukradnu viacej emisii a svet bude čistejši :) Odpovedať Známka: 8.8 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od: locke | Pridané: 23.1.2011 16:18 Ale to by ich nesmeli predať Odpovedať Známka: 7.5 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: e3k.. | Pridané: 22.1.2011 23:12 bolo by to dobre na to aby sme vedeli ze to co pouzivame je teoreticky uz dlhu dobu naburane inymi ktori o tom davno vedeli, len my sme si mysleli ze je to bezpecne. Odpovedať Známka: 7.1 Hodnotiť:

Re: Titulok príspevku musí mať dĺžku aspoň 5 znakov. Od reg.: cipo11 | Pridané: 22.1.2011 22:24 ...no a v 14. riadku som sa stratil... Odpovedať Známka: 8.6 Hodnotiť:

aleee Od: ajajajaj | Pridané: 22.1.2011 15:53 podla mna to uz Janka Hospodarova vedela davno.. Odpovedať Známka: -2.0 Hodnotiť:

Re: aleee Od reg.: __Ondrej | Pridané: 22.1.2011 16:43 Bolo by dobré konečne zistiť ako to vlastne je. Odpovedať Známka: 8.9 Hodnotiť:

Re: aleee Od: pudipudipudi | Pridané: 22.1.2011 19:07 No konecne clanok ci sa P rovna, alebo nerovna NP to uz tu dlho nebolo a zacinal som byt nesvoj, ked som netusil akym smerom sa to vyvija... Odpovedať Známka: 8.0 Hodnotiť:

Re: aleee Od: Squeak? | Pridané: 22.1.2011 18:37 Kto je dofrasa tá ženská a čo má s P a NP...? Odpovedať Známka: -1.5 Hodnotiť:

Re: aleee Od reg.: Uhlik | Pridané: 23.1.2011 13:23 to sa bez jasného dôkazu či P=NP nedá zistiť ... Odpovedať Známka: 10.0 Hodnotiť:

Re: aleee Od: : Pjetro de | Pridané: 22.1.2011 20:07 Myslim, ze by sme mali pockat na dokaz Janky Hospodarovej. Som zvedavy co vymysli, iste jej takato vysoka frekvencia dokazov tohoto problemu nedava spavat :-) Odpovedať Známka: -4.3 Hodnotiť:

Nezda sa mi to... Od: oraJaro_off | Pridané: 22.1.2011 16:14 Podla mna dokazali maximalne to, ze niektore jednoduchsie problemy z NP patria do triedy P, co sa ale vedelo davno a bez nich. Nech dokazu naozaj povodne zadanie (na ktore je vypisana aj odmena) a nie taketo "medzikroky". Odpovedať Známka: -2.7 Hodnotiť:

Re: Nezda sa mi to... Od reg.: zeratul | Pridané: 22.1.2011 16:19 urobit velky krok bez medzikrokov sa neda :) Odpovedať Známka: 7.1 Hodnotiť:

Re: Nezda sa mi to... Od: 3znaky | Pridané: 22.1.2011 18:09 ale priepast nepreskocis tym, ze budes robit vela malych krokov, treba jeden poriadny skok Odpovedať Známka: 2.2 Hodnotiť:

Re: Nezda sa mi to... Od reg.: zeratul | Pridané: 22.1.2011 20:33 malymi krokmi si postavis zariadenie, ktore ta cez priepast prehodi Odpovedať Známka: 7.0 Hodnotiť:

Re: Nezda sa mi to... Od: rigoberto | Pridané: 23.1.2011 12:02 bez prace nie su kolace Odpovedať Známka: 10.0 Hodnotiť:

Re: Nezda sa mi to... Od: souolek | Pridané: 23.1.2011 14:42 Telce robte kotrmelce! Odpovedať Známka: 10.0 Hodnotiť:

Re: Nezda sa mi to... Od: Mumsito | Pridané: 23.1.2011 0:00 Chlape skusal si na jednu kompilaciu napisat program? Nic poriadne sa na jednu kompilaciu neda urobit. Cize medzikroky su velmi dolezite. Len musis poznat svoj ciel. Odpovedať Známka: 3.3 Hodnotiť:

Re: Nezda sa mi to... Od reg.: zeratul | Pridané: 23.1.2011 13:30 hh, ja som to raz skusal a ti poviem, bolo to nieco :))). 2 hodiny som pisal program a dalsich 10 opravoval :DDD. Z takym poctom errorov a warningov visualko neratalo :P Odpovedať Známka: -5.0 Hodnotiť:

Re: Nezda sa mi to... Od reg.: Redakcia DSL.sk | Pridané: 22.1.2011 16:26 Nie, ak je dôkaz správny a 3-SAT je v P, tak P = NP. 3-SAT je totiž NP-úplný - pozrite si, čo znamená NP-úplný napríklad v našom odkazovanom článku. Odpovedať Známka: 8.6 Hodnotiť:

Re: Nezda sa mi to... Od: oraJaro_off | Pridané: 22.1.2011 20:21 Vsetkym tym problemom aj definiciam rozumiem. Ale to, ze bol zverejneny dokaz a kratko na to sa v nom nasli rozne chyby, mi napoveda, ze ten dokaz nebude dostatocny silny. A preto ho povazujem len ako dalsi pokus o zviditelnenia sa. Tiez to podporuje aj tvrdenie autora, v ktorom stoji, ze dokaz ma uz od roku 2002. Ak by to bolo tak, tak rozumny a vierohodny clovek by ho podrobil kritike odbornikom a az potom po pripadnej oprave by ho uverejnil. Ale takto mi to pripada len akoby ho vytvoril "teraz" a sa hra na velkeho hrdinu. Odpovedať Známka: 2.0 Hodnotiť:

Re: Nezda sa mi to... Od reg.: Vektor | Pridané: 22.1.2011 16:29 3-SAT je NP uplny, ak maju dokaz ze je v P, tak naozaj P = NP. Odpovedať Známka: 8.5 Hodnotiť:

Re: Nezda sa mi to... Od: prdlajs | Pridané: 22.1.2011 18:03 No ak je dokaz v P(ici), tak tam uz naozaj nie je co riesit :) Odpovedať Známka: -3.1 Hodnotiť:

Re: Nezda sa mi to... Od: : Pjetro de | Pridané: 22.1.2011 20:17 Nerozumies principu a tomu, preco staci dokazat len toto. Je to nieco take, ako keby sme zatial nevedeli, ci nejake tvrdenie plai pre vsetky parne cisla. Vieme ze vsak plati predpoklad "p" ze su len dve moznosti: bud nejake to tvrdenie (ake konkretne je teraz irelevantne) plati pre vsetky parne cisla, alebo ani pre jedno parne cislo. Pre velke parne cisla je dokaz tazky. Zrazu pride manik a dokaze to tvrdenie pre cislo 2. Potom ale z predpokladu "p" (hovoriaceho ze to plati bud pre uplne vsetky ,alebo pre ziadne parne cislo) plynie, ze to musi uz platit pre vsetky parne cisla bez, toho ze by sme to museli dokazovat nejakym tazsim dokazom napr. pre cislo 4. Odpovedať Známka: 2.3 Hodnotiť:

Re: Nezda sa mi to... Od: : Pjetro de | Pridané: 22.1.2011 20:19 pozn.: v ulohe toho predpokladu "p" tu vystupuje definicia NP-uplneho problemu, ktory ma jednoduchotake vlastnosti, ktore dovoluju dokazat "len toto" Odpovedať Známka: 0.0 Hodnotiť:

Re: Nezda sa mi to... Od: tribodky | Pridané: 23.1.2011 5:32 Podla teba staci takto: 1=1 => P=NP ? bez ziadnych medzikrokov :) Odpovedať Známka: 0.0 Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 23.1.2011 13:48 Napisal si blbost a sam o tom nevies, ale nevadi. Prva cast implikacie 1=1 je pravdive tvrdenie, druha cast P=PN je s najvacsou pravdopodobnostou nepravdive (myslime si to), aj ked to este nie je exaktne a vseobecne dokazane. V takomto pripade by tvoja implikacia mala pravdivy predpoklad a nepravdivy zaver a zo samej podstaty implikacie by teda nebola pravdiva (implikacia je nepravdiva jedina vtedy ak z pravdy vyplavy nepravda, resp. z pravdiveho predpokladu nepravdivy zaver, t.j. ze plynie negacia zaveru). Ak chces napisat zlozeny vyrok s implikaciou, ktory bude pravdivy bez ohladu na pravdivostno hodnotu zaveru, tak je mudre aby bol predpoklad nepravdivy. napr. vyrok: "Ak je Slnko zo syra, tak ja som stonozka" je PRAVDIVY (aj ked predpoklad a zaver ako take su nepravdive). Odpovedať Známka: -3.3 Hodnotiť:

Re: Nezda sa mi to... Od reg.: Tupcek | Pridané: 23.1.2011 15:00 máš pravdu, ale nepochopil si, o čo mu išlo. Niekto tu tvrdil, že je to len ďalší medzikrok. Síce ani to nie je pravda, ale to nie je dôležité. Ten, na koho si reagoval, hovoril to, že medzikroky musia byť. Že či si snáď ten prvý myslí, že sa dá spraviť dôkaz bez medzikrokov, že z elementárnej veci (1=1) dostane hneď komplikovanú (P=NP) Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 23.1.2011 16:07 Ci su potrebne medzikroky alebo nie, je defacto irelevantne. Matematika ako kauzalna, logicka, rigorozna, exaktna a deduktivna veda (je to defacto sposob myslenia) je zalozena na logickom odvodzovani tvrdeni so zakladnych pravidiel zvanym axiomy. Ak je kazde odvodene tvrdenie pravdive (na to sluzia dokazy), potom je jedno ci nieco dokazeme v 20. krokoch, alebo naraz. Treba si uvedomit ze dokazat nieco naraz a hned je casto krat, resp. skoro vzdy nemozne. Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 23.1.2011 16:09 Ani z Peanovej aritmetiky a Zermalovho-Frankelovho axiomatickeho systemu prirodzenych cisel priamo neplynie velka Fermatova veta, ale bolo nutne velke mnozstvo pomocnych tvrdeni a ciastocnych vysledkov. V dokaze velkej Fermatovej vety sa to dokonca hemzi samymi Lemmami (pomocnymi vetami), z ktorych kazda mohla byt sama o sebe dokazovana desatrocia za pomoci dalsich 15tich na seba hierarchicky nastavaniych tvrdeni. Ak by sa vsetko dalo v matematike dokazat naraz, tak by sme to predsa nedokazovali postupne, ale bozsku mysel by sme obsiahli uz pred 5 tisc rokmi. Matematika je neskutocny hierarchicky na seba nastavany rebricek logickych uvah aplikovanych na zopar zakladnych axiom na samom spodku a stupajuc vyssie potom hierarchicky dokazujeme dalsie tvrdenia. Odpovedať Známka: 3.3 Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 23.1.2011 16:20 To je to caro umenia a sucasne charakteristika matiky: pozliepat ci pozhanat si pravdive tvrdenia niekedy aj z najroznejsich oblasti matematiky a ci uz za pomoci novo definovanych pojmov a postupov ci len konzervativnejsimi metodami z tychto pozliepanych pravdivych vyrokov vyvodit a dokazat pravdivost prekvapujuco uuuuplne ineho tvrdenia, ktore na prvy pohlad s povodnymi preppokladmi (tymi "pozhananymi" pravdivymi tvrdeniami o ktore sme sa opierali) nema nic spolocne. Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 23.1.2011 16:20 Cim vascia je tato medzera (medzi predpokladmi alias "pozhananymi" pravdivymi tvrdeniami o ktore sme sa opieralia a zavermi, ktore sme vlastne dokazali), tym je ta medzera nejasnejsia a tym tazsie by bolo prist na tazky postup a sled logickych dedukcii omocou ktorych by sme na zaver prisli hned bez medzikrokov. Je teda prirodzene ze medzikroky existuju, aj ked pravi matici ich ako medzikroky nechapu, pretoze vzdy je to ponohodnotny vysledok. Aj velka Fermatova veta sama o sebe moze posluzit spolu s dalsimi pravdivymi a dokazanymi tvrdeniami na dokazanie ineho tvrdenia, na ktoreho dokaz by sme nemali sancu bez dokazanych ciastocnych vysledkov (medzikrok je blbe slovo). Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 23.1.2011 16:10 Takze "stazovat sa" ze nieco nie je dokazane hned naraz v tom najvseobecnejsom pripade, je opat kratkozrake, kedze to s najvacsou pravdepodobnostou ani nie je mozne. A to este nehovorim o godelovskej neuplnosti istych axiomatickych systemov - tam totiz ani nemozeme dokazat vsetko (nie to si este vyberat ci naraz, alebo v 175tich medzikrokoch). :-) Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Tupcek | Pridané: 23.1.2011 21:20 zhrnutie tvojích príspevkov: áno, treba ísť po krôčikoch, nedá sa naraz:-) Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 24.1.2011 8:17 Je to vsak diskutabine. Dokazat vsetko naraz by znamenalo bud ist od samotnych zakladnych stavebnych kamenov matematickych teorii, t.j. od axiom a aj tie lahsie dokazy viet, ktore sa beru na VS by mali stovky stran a stovky logickych uvah ci pomocnych odbociek (ano uz vtedy je jasne ze radsej "medzikroky"), alebo cielove tvrdenie dokazat pomocou inej matematickej teorie s inymi axiomami a logickymi uvahami aplikaciou inych deduktivnych postupov, ktore by dovolili kratsiu cestu. Odpovedať Hodnotiť:

Re: Nezda sa mi to... Od reg.: Pjetro de | Pridané: 24.1.2011 8:18 Uz x-krat sa v matematike stalo, ze celkom prvy dokaz nejakeho prelomoveho tvrdenia (napr. prvociselna veta) bol velmi obtiazny a dlhy. Oplati sa zvazit, ci to nebolo PRAVE PRETO, ze dokaz bol robeny starsim matematickym aparatom a vychadzal jednak zo starsich a menej vhodnych pojmov, ktore boli sucasne elementarnejsie. Novsie formy dokazov su jednoduchsie a kratsie. Pricina moze byt v sucinnosti faktov, ze jednak sa pouziva novsi matematicky aparat a jednak tym ze je dokaz robeny na etapy, resp. moze sa opierat o "ciastocne" vysledky dokazane skor. Odpovedať Hodnotiť:

ziadny titulok Od: tt12345 | Pridané: 22.1.2011 16:30 "kde n je počet premenných a m počet podmienok" Nie snád počet klauzulí a literálov? Odpovedať Známka: 2.9 Hodnotiť:

Re: ziadny titulok Od reg.: Tupcek | Pridané: 23.1.2011 7:26 už tak to ledva chápeme, nekomplikuj :) Odpovedať Známka: 8.8 Hodnotiť:

WTF ???? Od: roflmaoc | Pridané: 22.1.2011 16:40 No pozrel som sa mu na to a musim uznat ze z jeho prace jednoznacne vychadza ze to plati :P /joke/ Odpovedať Známka: -4.7 Hodnotiť:

Re: WTF ???? Od reg.: foobar0 | Pridané: 22.1.2011 17:00 To "joke" na konci ma pobavilo :-> http://goo.gl/NQW4f Odpovedať Známka: 2.2 Hodnotiť:

Rus zverejnil program, ktorý by mal dokazovať P = NP Od: vasect0mianus | Pridané: 22.1.2011 18:01 do stvrtka potrebujem vediet, lebo inak ma Kucera vyrazi Odpovedať Známka: 9.4 Hodnotiť:

Re: Rus zverejnil program, ktorý by mal dokazovať P = NP Od: Squeak? | Pridané: 22.1.2011 18:38 Si mal ísť k Čepekovi, mával na skúškach veľmi dobrú náladu :) Odpovedať Známka: 9.1 Hodnotiť:

Re: Rus zverejnil program, ktorý by mal dokazovať P = NP Od: asdgfadfdfg | Pridané: 22.1.2011 20:10 Ano, s Cepkom bola sranda, ale nie kazdy ho stihol pred jeho odchodom vcera :). Mne sa zda, ze tu nastava bezny problem pri prevodoch P - NP - prevadza polynomialne velky vstup na exponencialne velky vstup, ktory sa zrejme da riesit v P, co ale nedokazuje P=NP. Odpovedať Známka: 8.0 Hodnotiť:

Penny Od: Sheldon | Pridané: 22.1.2011 18:31 Knock, knock, knock. Penny! Knock, knock, knock. Penny! Knock, knock, knock. Penny! Odpovedať Známka: 6.0 Hodnotiť:

Uff!!! Od reg.: Extraterrenista | Pridané: 22.1.2011 20:53 Ešte že som nerozumel ani slovu,inak by som sa musel začať báť! Odpovedať Známka: 5.2 Hodnotiť:

čože? :O Od: Milankovia | Pridané: 22.1.2011 21:41 Fakt ale z toho článku som úplný lampáš :( A pritom až taký blbý nie som.........alebo hej? (drunk) Odpovedať Známka: 10.0 Hodnotiť:

vsetko naj Od: iKEBAB | Pridané: 22.1.2011 22:01 a co to znamena pre bezneho bocana ? Odpovedať Známka: 8.2 Hodnotiť:

Re: vsetko naj Od: iKEBAB | Pridané: 22.1.2011 22:01 obcana Odpovedať Známka: 8.3 Hodnotiť:

Re: vsetko naj Od: tribodky | Pridané: 23.1.2011 5:41 Tak pre bezneho obcana by mohlo znamenat dost, takmer vsetko, co suvisi s nejakou sifrou, napr. el. bankovnictvo, prihlasovat na ucty, dokonca aj login na providera do internetu a radu dalsich veci, ktore by boli nuteni zmenit sposob sifrovanie. Mozno polovicu dat vo svete potrebuje zmenu. Odpovedať Známka: 3.3 Hodnotiť:

Re: vsetko naj Od reg.: Tupcek | Pridané: 23.1.2011 7:29 to by sa dialo na strane servrov a providerov. pre bežného občana by to neznamenalo zatiaľ nič :) jedine, že ak by do GPSka dal 1000 bodov, kde chce ísť, vedelo by mu nájsť najkratšiu trasu optimálnejšie, ako doteraz :) (aspoň pokiaľ som tomu celému správne porozumel) Odpovedať Hodnotiť:

Re: vsetko naj Od: hellokitty | Pridané: 22.1.2011 22:15 no radsej ani nechci vediet, z toho by ti mohla hlava prasknut =D Odpovedať Známka: 10.0 Hodnotiť:

Re: vsetko naj Od: garcia82 | Pridané: 22.1.2011 22:40 bociana? Odpovedať Známka: 10.0 Hodnotiť:

12345 Od: Matooo01 | Pridané: 22.1.2011 22:28 ma tam chybu ;) Odpovedať Známka: 7.8 Hodnotiť:

Re: 12345 Od: no totok... :) | Pridané: 23.1.2011 1:48 tak tak, hneď ma napadlo že "bocyján" sa píše s dĺžňom... ps.: aj tak budem požiarnikom!! :) Odpovedať Známka: 7.1 Hodnotiť:

to nieje fér Od: hulvaaat | Pridané: 23.1.2011 1:37 aj ja chcem byť bocian,,,, Odpovedať Známka: 10.0 Hodnotiť:

zakladna otazka... Od: prpr | Pridané: 23.1.2011 2:25 ... co to ma s wifi vo velkom kancli? Odpovedať Známka: 1.7 Hodnotiť:

Re: zakladna otazka... Od: taktak | Pridané: 23.1.2011 16:00 sila signálu je priamoúmerná počtu bocianov v okolí... Odpovedať Známka: 6.0 Hodnotiť:

slabe Od: AstaKiller | Pridané: 23.1.2011 2:33 To je nic, ja kludne dokazem ze MIKLOS = ZLODEJ. Odpovedať Známka: 0.0 Hodnotiť:

Re: slabe Od: Squeak? | Pridané: 23.1.2011 11:38 Nemáš šancu... Odpovedať Známka: 3.8 Hodnotiť:

čomámjastitulkom Od: akémenomoje? | Pridané: 23.1.2011 4:58 a čo ako teraz. fico má istotne nahrávku, ktorá toto tvrdenie dementuje. čiže sa skôr zaoberajme myšlienkou naša vláda=dementi a tam nie je o čom diskutovať. Odpovedať Známka: 5.7 Hodnotiť:

Re: čomámjastitulkom Od reg.: Uhlik | Pridané: 23.1.2011 13:26 ale ak P=NP, tak si konečne budeme môcť pustiť Mečiarovu kazetu ;o) ... Odpovedať Známka: 10.0 Hodnotiť:

..... Od: tribodky | Pridané: 23.1.2011 5:35 Pocet premennych, tak to este chapem, ze pocet literalov, ale pocet podmienok je myslene pocet klauzuli alebo co ? Odpovedať Hodnotiť:

Re: ..... Od: MenoX | Pridané: 23.1.2011 5:57 Príspevok bol zmazaný pre nevhodný a/alebo vulgárny obsah. Odpovedať Známka: 0.0 Hodnotiť:

Re: ..... Od reg.: Tupcek | Pridané: 23.1.2011 7:30 podľa mňa sa to len snažili zjednodušiť pre nás, čo máme problém pochopiť, aký je polynomiálny čas :) Odpovedať Známka: 6.7 Hodnotiť:

Re: ..... Od: : Pjetro de | Pridané: 23.1.2011 8:50 Neexistuje polynomialny cas ci exponencialny cas. Cas je jednej charakteristiky - deformovana entita podla teorie relativity, ktora ma vsade ine tempo plynutia (rastu ak chceme z pohladu funkcie). Je to vsak skrateny nazov pre fakt, ked doba potrebna na ziskanie vysledku pri zvacseni poctu premennch ci ich hodnot v algoritme, stupa bud polynomicky, alebo exponencialne (vzhladom na vstupne hodnoty). Odpovedať Známka: 7.5 Hodnotiť:

Re: ..... Od reg.: Tupcek | Pridané: 23.1.2011 10:49 hehe, ako som len chcel povedať, že sme radi, že chápeme základné pojmy, nie to ešte komplikovať :) Odpovedať Známka: 10.0 Hodnotiť:

Re: ..... Od: McUH | Pridané: 23.1.2011 11:44 Píšeš nezmysly. Výpočtová zložitosť nemá absolútne nič s časom ako fyzikálnou veličinou. Čo reprezentuje čas ako fyzikálna veličina tiež zatiaľ nie je vôbec jasné a popri fyzike sa tým výrazne zaoberá i filozofia. Výpočtová zložitosť je jasne zadefinovaná. A nejde o nejakú "dobu" ale počet krokov výpočtu (obvykle TS) a toto sa bežne označuje i pojmom "čas výpočtu" či "časová zložitosť". Takže polynomiálny či exponenciálny čas samozrejme existuje v kontexte výpočtovej zoložitosti. Odpovedať Známka: 10.0 Hodnotiť:

Re: ..... Od reg.: Pjetro de | Pridané: 23.1.2011 13:57 Mas pravdu, zlozitost problemov je definovana na zaklade zavislosi medzi vstupnymi udajmi (ich poctom ci velkostou) a poctom potrebnych krokov na ukoncenie algoritmu (vypoctu) a teda nie casom. Narazal som ale na pojem "polynomicky cas" ci "exponencialny cas", kde som sa znazil vysvetlit ze cas je vo fyzikalnej realite jedna jedina entita - neexistuje 237 roznych druhov casov (kde napr. polynomicky ci exponencialny by boli len dva z nich). To ze v podstate vsade cas plynie inym tempom, kedze vyskyt hmotoenergie casopriestor deformuje vyjadritelnym matematickym aparatom Riemanovskych geometrii a tenzoroveho poctu, je druha vec. Odpovedať Známka: -5.0 Hodnotiť:

Re: ..... Od: ach | Pridané: 24.1.2011 2:12 na jaku gutu tam zas pchas tu fyziku? Odpovedať Hodnotiť:

Re: ..... Od reg.: Pjetro de | Pridané: 24.1.2011 8:06 Asi nevies o STYROCH novodobych filozofickych pohladoch na matematiku ako sposob uvazovania druhu homo sapiens, t.j. inak preco je prave matematike a jedine matematika tak uzasny a vhodny jazyk na popisanie algoritmickej stlacitelnosti viditelneho vesmiru a teda fyzijkalnej reality ... Odpovedať Hodnotiť:

Re: ..... Od reg.: Pjetro de | Pridané: 24.1.2011 8:06 Napoveda: v staroveku pred 2,5 tisicrocim bolo DVA nazory na to co je matika: aristotelovsky realizmus a platonsky idealizmus vecnych dokonalych foriem. Prvy hlasa ez matiku neobjavujeme, ale tvorime a pouzivame ju na popis fyzikalnej reality. Druhy nazor hlasa ze matika je vecna, je to akysi vyssi sveta meta-foriem, z ktoreho vidime len vycnelky a ktory sa snazime aplikovat, resp. dohadovat sa, ako vyzera skutocny dokonaly matematicky a dalej az meta-fyzikalny svet. Platon to prirovnava k cloveku ktory cely zivot zije v jaskyni a na stenach jaskyne vidi len tiene skutocnych ludim, ktori su vonku. Napoveda: nasa fyzikalne realita podla platona su LEN tie tiene a skutocny meta-fyzikalny svet je az vonkajsok jaskyne. Odpovedať Hodnotiť:

Re: ..... Od reg.: Pjetro de | Pridané: 24.1.2011 8:07 Inak povedane matika je vecna, nezostrojojeme ju, ale objavujeje. Od najvacsich primitivit ci elementarnosti, napr. obsah stvorca bol vzdy S=a^2, aj teraz aj pred miliardou rokov, len vtedy nebol nikto kto by si to uvedomil ... az po tvrdenia vrcholovej matiky (detto to iste - vtedy nebol nikto kto by si to uvedomil, dokonca pri nedavno dokazanych tvrdeniach nebol nikto taky este pred par storociami). Na zlozitosti tvrdeni a enormnemu mnostvo uvah ktore bolo treba podniknut na ich dokazanie, rataz nezazeli. POdla platobna su to vsetko existujuce pravky v matematickom svete, ktory len postupne objavujeme od najvacsich elementarnosti stale k zlozitejsim. A protipol k tomu je ten aristotelovsky realizmus. Odpovedať Hodnotiť:

Re: ..... Od reg.: Pjetro de | Pridané: 24.1.2011 8:07 O styroch sucasnych filozofickych pohladoch na to co je matika (a hovoriacich nielen o tom ci je matika len vytvor ludskeho umu, alebo absolutna pravda existujuca v meta-svete vyssich foriem) pisat nebudem. Takze este sa cudujes preco spajam matiku a fyziku (ci ine prirodne vedy zaoberajuce sa fyzikalnou realitou)? Odpoviem si sam: bohuzial cudujes. Odpovedať Hodnotiť:

Nedeľa, 23. januára 2011, dnes má meniny Miloš, zajtra Timotej Pošli kvety Od: brumicek | Pridané: 23.1.2011 12:00 Je tu vobec niekto kto nerozumie z clanku ani vetu ako ja ?!? Odpovedať Známka: 9.0 Hodnotiť:

Re: Nedeľa, 23. januára 2011, dnes má meniny Miloš, zajtra Timotej Pošli kvety Od: Ja. | Pridané: 23.1.2011 13:09 Hanbil som sa to priznať Odpovedať Známka: 8.8 Hodnotiť:

Re: Nedeľa, 23. januára 2011, dnes má meniny Miloš, zajtra Timotej Pošli kvety Od reg.: Tupcek | Pridané: 23.1.2011 15:03 ... že všetkému chápem... Odpovedať Známka: -6.0 Hodnotiť:

Re: Nedeľa, 23. januára 2011, dnes má meniny Miloš, zajtra Timotej Pošli kvety Od: optimalizace | Pridané: 23.1.2011 17:15 ani zatat Odpovedať Hodnotiť:

Je to dokazane? Od reg.: Martin Kovac | Pridané: 23.1.2011 17:15 Program by mal dokazovat -> dokazuje? Odpovedať Hodnotiť:

Re: Je to dokazane? Od: Element2 | Pridané: 24.1.2011 11:00 Sú tam chyby, takže asi nie. Ale možno áno. Odpovedať Hodnotiť:

mam to! Od: T.Čajko - Lemon | Pridané: 24.1.2011 9:09 vsetci sa s tou vecou serete a ja to na dejepise vyriesim P=NP..... ak sa P=1 N=0 tak plati 1=01 a taktiez 1!=01 Odpovedať Známka: -2.0 Hodnotiť:

Re: mam to! Od: wrrrrrrrrrrr | Pridané: 24.1.2011 9:56 e.stankovic.....ked trepnes hovadinu tak sa aspon za nu priznaj... Odpovedať Známka: 10.0 Hodnotiť:

zasrani rusaci Od: ceco00 | Pridané: 25.1.2011 10:17 mal to zverejnit v 1968om nesrali by sa k nam rusaci! Odpovedať Hodnotiť:

Pridať komentár