Slo-Tech - Eden izmed najprivlačnejših matematičnih problemov, katerega rešitev bi pomembno vplivala na tudi na računalništvo, je vprašanje ali je P enako NP. Gre za enega izmed sedmih tako imenovanih tisočletnih problemov v matematiki, z rešitvijo katerega lahko od Clay Mathematics Instituta dobimo milijon dolarjev nagrade (kar je nekoliko več od Nobelove nagrade). Doslej je bil rešen samo eden izmed sedmerice problemov. Problem P proti NP sprašuje, ali za vsak problem, katerega rešitev lahko preverimo v polinomskem času, v polinomskem času tudi rešimo. O tovrstnih vprašanjih so se pogovarjali že Nash, Gödel in von Neumann, rigorozno formulacijo pa je leta 1971 postavil Stephen Cook.
Trenutno prevladujoče mnenje v znanosti je, da velja P ≠ NP ali z drugimi besedami, da obstajajo problemi, ki jih lahko preverimo v polinomskem času, rešiti pa jih ne moremo. Takih težkih nalog je precej, denimo potujoči trgovec, barvanje grafov in še več tisoč podobnih. Napisano je seveda poenostavitev, saj ne smemo predvidevati, da so vsi problemi P (rešljivi v polinomskem času) tudi v praksi hitro rešljivi, saj so lahko konstante enostavno previsoke. Prav tako obstajajo algoritmi za sorazmerno hitro reševanje nekaterih NP problemov za določene vhodne podatke.
Poizkusov dokaza v eno ali drugo smer smo videli že mnogo, a doslej si še nihče ni zaslužil milijona dolarjev, saj so vsi vsebovali napake. Enega izmed najnovejših je nemški matematik Norbert Blum predstavil ta mesec. Po sprva pozitivnih reakcijah matematične skupnosti se je vnovič pokazalo, da je dokaz luknjičast. Scott Aaronson z Univerze v Teksasu pravi, da bi upal celo staviti 200.000 dolarjev, da Blumov dokaz ne bo prestal temeljite preveritve. Analiza širše matematične srenje pritrjuje njegovemu mnenju.
Resnica za zdaj ostaja neznana, pri čemer niti ni znano, ali je samo vprašanje P proti NP rešljivo. V aksiomatični matematiki je prav mogoče skonstruirati vprašanje, ki ima rešitev, a je nikakor ne moremo izvedeti. Upamo lahko, da vprašanje ali je P = NP ni te vrste. Če bo komurkoli uspelo rešiti katerikoli NP-poln problem v polinomskem času, bo dokaz s tem že končan, saj so vsi NP-polni problemi ekvivalentni in jih lahko v polinomskem času pretvarjamo enega v drugega. Še najslabši izid bi bil nekonstruktiven dokaz, ki bi samo povedal, da so NP problemi rešljivi v polinomskem času, ne pa tudi kako. Seveda pa je povsem mogoče - če dopustimo demokracijo v matematiki, celo bolj verjetno - da NP-polni problemi v polinomskem času pač niso rešljivi.
Točno! Tudi ta "problem" je zelo lahko rešljiv na popolnoma enak način kot vse ostalo v življenju. Večina nima najmanjšega pojma o čem se sploh gre, tako kot pri večini stvari. Če bo v knjigah pisalo P=NP potem je pač P=NP. Kdor bo trdil drugače je čudak ali pa celo nevaren osebek, ki ga je treba odstraniti iz družbe.
n^2 x n^2 = n^4 kar je še vedno polinom... NP bi bilo 2^n ali 4^n Sicer maš pa prav, da je sudoku NP-poln. Problem se prevede na barvanje grafov (polje=vozlišče, številka=barva vozlišča + povezave med vozlišči v istem 3x3/vrstici/stolpci), kar je NP-poln problem. Ampak za mreže 9x9 se da rešit v doglednem času. Mathematics of Sudoku @ Wikipedia
Ampak to da je preverjanje rešitve težje od postopka reševanja ki ga danes poznamo, še ne pomeni da ne moremo izumiti postopka, ki bo to rešil enako hitro kot preverjamo rešitev
Ampak to da je preverjanje rešitve težje od postopka reševanja ki ga danes poznamo, še ne pomeni da ne moremo izumiti postopka, ki bo to rešil enako hitro kot preverjamo rešitev
Verjetno si mislil ravno obratno ... postopek resevanja je tezji od preverjanja resitve :) Ce P=NP, potem tak postopek sigurno obstaja. Ce N!=NP, potem pa ne, vsaj ne eksaktna varianta.
Sudoku sem uporabil zgolj kot poenostavljeno ilustracijo za tiste, ki se jim ne sanja o cem clanek govori in kaksne implikacije bi P=NP imel :)
A ni bil ta problem enkrat že kao rešen, ali se motim (očitno se)? Vem, da je Ponicarjeva domneva dokazana ampak kolikor se spomnim, naj bi bil N=NP še prej. Možno, da so ovrgli dokaz, pa sem spregledal.
Dokler se bo folk ukvarjal s takimi problem.. adijo pamet
En problem, ki ga boš imel kmalu potem, ko se reši ta problem je, da bo mogoče hitro razbit vso kriptografijo, ki jo trenutno poznamo. To pomeni, da bo vso varno komunikacijo preko neta, ki je bila šifriranjna enostavno dešifrirati. Tako, da je ta problem v resnici malo bol zanimiv kot bi si človek mislu ;)
Saj se ne išče rešitev problema. Išče se dokaz s katerim bi teorijo ovrgli ali potrdili. Kaj bomo imeli v prihodnosti od tega je pa odvisno kaj bo dokazano.
Antifašizem je danes poslednje pribežališče ničvredneža, je ideologija ničesar
in neizprosen boj proti neobstoječemu sovražniku - v zameno za državni denar
in neprofitno najemno stanovanje v središču Ljubljane. -- Tomaž Štih, 2021
Saj se ne išče rešitev problema. Išče se dokaz s katerim bi teorijo ovrgli ali potrdili. Kaj bomo imeli v prihodnosti od tega je pa odvisno kaj bo dokazano.
Those who can, do. Those who can't, teach. Če se ta teorem dokaže, ti to prav nič ne pomaga pri reševanju konkretnih problemov, torej dokaz ti ne da algoritma za reševanje sudokuja, ki je enako hiter kot preverjanje rešitve, je tako?
Bazična znanost je nujna za razvoj aplikativnih, se strinjam, ampak tule se mi pa res zdi, da gre bolj za nek prestiž, kot za uporabno zadevo.
Antifašizem je danes poslednje pribežališče ničvredneža, je ideologija ničesar
in neizprosen boj proti neobstoječemu sovražniku - v zameno za državni denar
in neprofitno najemno stanovanje v središču Ljubljane. -- Tomaž Štih, 2021
Seveda si hudo hud matematik, da lahko objektivno poveš, da tole nima smisla? Ker zabijanje atomov med sabo recimo se je sigurno kakšnemu forumašu zdelo metanje denarja skozi okno.
Če se ta teorem dokaže, ti to prav nič ne pomaga pri reševanju konkretnih problemov, torej dokaz ti ne da algoritma za reševanje sudokuja, ki je enako hiter kot preverjanje rešitve, je tako?
Neposredno ne, ampak boš pa z zagotovostjo izvedel ali je tak algoritem sploh mogoč in iz tega greš naprej. Temu se reče napredek.
Bazična znanost je nujna za razvoj aplikativnih, se strinjam, ampak tule se mi pa res zdi, da gre bolj za nek prestiž, kot za uporabno zadevo.
Dvomim, da je katerikoli slotehovec na dovolj visokem nivoju teoretične matematike, da bi lahko mi presojali ali gre samo za prestiž ali ne.
Matematikom načeloma dol visi za vse, razen matematiko. Samo Perelmana poglej.
Saj se ne išče rešitev problema. Išče se dokaz s katerim bi teorijo ovrgli ali potrdili. Kaj bomo imeli v prihodnosti od tega je pa odvisno kaj bo dokazano.
Če se ta teorem dokaže, ti to prav nič ne pomaga pri reševanju konkretnih problemov, torej dokaz ti ne da algoritma za reševanje sudokuja, ki je enako hiter kot preverjanje rešitve, je tako?
Bazična znanost je nujna za razvoj aplikativnih, se strinjam, ampak tule se mi pa res zdi, da gre bolj za nek prestiž, kot za uporabno zadevo.
Lahko gre v dve smeri.
Ce se dokaze P!=NP, potem je to dokaz, da taki algoritmi sploh ne obstajajo.
Dokaz P=NP pa bi, vsaj po mojem vedenju, bil resitev enega konkretnega NP-complete problema v P, iz cesar potem sledi da se vse NP-complete probleme da resit v P, saj so problemi v dolocenem razredu med sabo prevedljivi (se jih da izrazit kot drug problem istega razreda) ... torej ce imas resitev enega, potem druge lahko izrazis s pomocjo tega prvega. Bottom line, dokaz P=NP bi po mojem razumevanju moral biti dejanski algoritem.
Je pa tko, da za vecino computer science communityja je precej bolj verjeten prvi scenarij, torej P!=NP, saj je za mnoge kombinatoricna eksplozija pac nekaj kar je za vesolje inherentno.
Implikacije? Povsod. Logistika je en direkten primer (potujoci potnik).
Ja, ampak en algoritem še ni dokaz, da so možni povsod. Jaz mislim, da je najprej treba dokazati, da so vsi NP-ji rešljivi v P. Kako, nimam pojma ampak dokaz zagotovo ne bo algoritem. Z njimi se bomo začeli ukvarjati šele ko (če) bomo potrdili teorem. Lahko imam pa samo jaz napačno predstavo o vsem skupaj.
Oznaka NP pomeni nedeterministično-polinomski. Označuje en velik kup problemov, kjer kompleksnost (i.e. tipično potreben čas ali prostor ) postopka za njihovo rešitev narašča s polinomsko zahtevnostjo (i.e. karkoli na fiksno konstanto ki ni odvisna od velikosti problema) samo na nedeterminističnem stroju - to je računalnik z 'čarobno' palico ki v vsakem ključnem odločanju ugane najboljšo možnost. Ker naši realni računalniki nimajo takšne čarobne palice v splošnem ne preostane drugega kot da se preveri vsako izmed možnosti in tako določi najboljšo. Število "možnih možnosti" je tipično odvisno od velikosti problema, kar pomeni da kompleksnost postopka v realnem narašča hitreje kot narašča polinomska zahtevnost. Po domače to pomeni, da recimo izmed 10 krajev še lahko zračunaš najbolšo možnost, pri 20 krajih (to je 2x večji problem) pa bo reševanje trajalo recimo 2 na 10 potenco dlje.
Vprašanje P ?= NP pomeni ali mogoče obstaja algoritem, ki tudi na realnih računalnikih nima takšne "neobvladljive" eksplozije zahtevnosti z večanjem problema. Obstaja podmnožica NP-polnih problemov, kjer so dokazali da če se najde polinomski (i.e. oblvadljiv) alogitem za enga izmed njih, bodo avtomatsko rešlivi vsi. Takšno odkritje bi bilo vredno več kot odkritje kolesa. Pomenilo bi, da bi nenanodma bili sposobni oztimizirat ogromno realnih procesov, ki so trenutno daleč od optimalnih ampak boljših nimamo.
Povečevanje hitrosti računalnikov je le polinomsko (i.e. podvojitev na leto in pol), zato so problemi katerih kompleksnost narašča hitreje kot karkoli na konstanto v splošnem neobvadljivi. Tudi ultra hitrejši računalniki bodo omogočili rešitev le parkrat večjega problema.
Na kratko in poenostavljeno: 10 x hitrejši računalnik je v enakem času zmožen rešiti le 2x večji (NP) problem, 100x hitrejši pa 3x večji problem. Če se dokaže P=NP pomeni, da bomo sposobni na 100x hitrejšem računalniku rešiti 100x večji prbolem.
Se ubadam z ralnim problemom razdelitve mačk med 4 sodnike. Če mam samo 15 mačk, lahko računalnik v nekaj sekundah preveri vse možne razdelitve in najde najboljšo. Če mam 30 mačk bi preverjanje vseh trajalo že nekaj let, realna razstava 200 mačk pa bi zahtevala 1050 let.
Jaz ne razumem zakaj pri tem problemu Raptor in Jype ne združita moči in rešita tale problemček (Raptor drgač ni potreben, je pa dovolj da periodično kavo nosi Jypetu).
Dokler se bo folk ukvarjal s takimi problem.. adijo pamet
Ja, na začetku prejšnjega stoletja se je nek Einstein ukvarjal z neko precej butasto teorijo, potem so pa v 1930-tih začeli delati neke poskuse z uranom, berilijem in podobnimi radioaktivnimi zadevami.
Kakšne traparije! Itak vsi vemo, da je radioaktivnost škodljiva, sploh pa čemu služi neko razbijanje atomov. Mislim, otroci šraufajo ure, da bi videli kaj je notri, tukaj pa neki odrasli otroci zapravljajo milijone za podobno igranje.
In potem skok v 21. stoletje, kjer se Evolve greje s pomočjo elektrike iz jedrske elektrarne Krško ob tem pa nima pametnejšega dela kot jamrat po forumih s kakšnimi butastimi problemi se ukvarjajo znanstveniki.
John Cockcroft in Ernest Walton si verjetno nista mislila, da bodo ljudje nekoč pridobivali elektriko, imeli toplo vodo, svetlobo, itd. na podlagi tega, kar sta počela. Sem pa prepričan, da je bilo okrog njiju kup Evolvetov, ki so imeli marsikaj neumnega za pripomnit.
Super napisano. Ampak, ali je dokaz že nujno tudi rešitev. Npr. če dokažemo, da lahko 100× hitrejši računalnik reši 100× kompleksnejši problem, ali hkrati tudi že izvemo kako? Ne, možno sicer je, ampak ponavadi se najprej dokaže če je rešitev sploh mogoča, potem se jo pa išče. In, ja se strinjam. Če se potrdi NP=P bo prihodnost nora. Vsi bodo iskali algoritme (da bi bil en univerzalen, je najbrž preveč pričakovati, mar ne? To bi bilo že skoraj kot odgovor 42 )
Ja, ampak en algoritem še ni dokaz, da so možni povsod. Jaz mislim, da je najprej treba dokazati, da so vsi NP-ji rešljivi v P. Kako, nimam pojma ampak dokaz zagotovo ne bo algoritem.
Tukaj se motis. Verjetno sicer lahko dokazes, da so da so vsi NP resljivi v P po drugi poti, ampak obstoj zgolj enega NP algoritma, resljivega v P pomeni, da so vsi NP-polni problemi resljivi v P. Iz tega enega algoritma moras potem iskati "zgolj se" polinomsko prevedbo na ostale probleme. Tako da bi rekel da je mnogo bolj verjetno in hkrati prakticno, ce dokaz pride v obliki algoritma. Ce to dejansko drzi, potem je obstoj dokaza P=NP prakticno irelavanten (razen ce dejansko pride prej in seveda da odgovor na vprasanje a je to sploh mogoce).
Protidokaz pa seveda nikakor ne more obstajati v obliki algoritma, ce pa ta sploh ne obstaja.
Oznaka NP pomeni nedeterministično-polinomski. Označuje en velik kup problemov, kjer kompleksnost (i.e. tipično potreben čas ali prostor ) postopka za njihovo rešitev narašča s polinomsko zahtevnostjo (i.e. karkoli na fiksno konstanto ki ni odvisna od velikosti problema) samo na nedeterminističnem stroju - to je računalnik z 'čarobno' palico ki v vsakem ključnem odločanju ugane najboljšo možnost. Ker naši realni računalniki nimajo takšne čarobne palice v splošnem ne preostane drugega kot da se preveri vsako izmed možnosti in tako določi najboljšo. Število "možnih možnosti" je tipično odvisno od velikosti problema, kar pomeni da kompleksnost postopka v realnem narašča hitreje kot narašča polinomska zahtevnost. Po domače to pomeni, da recimo izmed 10 krajev še lahko zračunaš najbolšo možnost, pri 20 krajih (to je 2x večji problem) pa bo reševanje trajalo recimo 2 na 10 potenco dlje.
Vprašanje P ?= NP pomeni ali mogoče obstaja algoritem, ki tudi na realnih računalnikih nima takšne "neobvladljive" eksplozije zahtevnosti z večanjem problema. Obstaja podmnožica NP-polnih problemov, kjer so dokazali da če se najde polinomski (i.e. oblvadljiv) alogitem za enga izmed njih, bodo avtomatsko rešlivi vsi. Takšno odkritje bi bilo vredno več kot odkritje kolesa. Pomenilo bi, da bi nenanodma bili sposobni oztimizirat ogromno realnih procesov, ki so trenutno daleč od optimalnih ampak boljših nimamo.
Povečevanje hitrosti računalnikov je le polinomsko (i.e. podvojitev na leto in pol), zato so problemi katerih kompleksnost narašča hitreje kot karkoli na konstanto v splošnem neobvadljivi. Tudi ultra hitrejši računalniki bodo omogočili rešitev le parkrat večjega problema.
Na kratko in poenostavljeno: 10 x hitrejši računalnik je v enakem času zmožen rešiti le 2x večji (NP) problem, 100x hitrejši pa 3x večji problem. Če se dokaže P=NP pomeni, da bomo sposobni na 100x hitrejšem računalniku rešiti 100x večji prbolem.
Se ubadam z ralnim problemom razdelitve mačk med 4 sodnike. Če mam samo 15 mačk, lahko računalnik v nekaj sekundah preveri vse možne razdelitve in najde najboljšo. Če mam 30 mačk bi preverjanje vseh trajalo že nekaj let, realna razstava 200 mačk pa bi zahtevala 1050 let.
Zelo solidna razlaga... bi pa pripomnil, da je povečevanje zmogljivosti računalnikov v resnici eksponentno (2^x) in ne polinomsko ter da v praksi tudi pri problemih iz razreda P (za rešitev katerih obstaja polinomski algoritem) obstaja (in bo vedno obstajala) pač meja velikosti, do katere bo problem na trenutno razpoložljivi mašineriji še možno rešiti. Če ima problem časovno kompleksnost n^10 bo recimo za n=5 trajalo reda velikosti 5^10 enot, za n=10 pa 10^10 enot, kar je več kot tisočkrat dlje, čeprav se je velikost problema samo podvojila. Je pa to še vedno precej bolje kot če bi bila časovna kompleksnost eksponentna, recimo 10^n, kjer je razmerje v trajanju za n=5 in n=10 ena proti sto tisoč. Veliko je odvisno tudi od polinomskih koeficientov in eksponentne osnove, saj prav lahko v nekem območju praktične uporabe algoritma polinomska kompleksnost narašča hitreje kot eksponentna, čeprav seveda za n proti neskončno polinomi vedno naraščajo počasneje kot eksponentna funkcija.
Seveda si hudo hud matematik, da lahko objektivno poveš, da tole nima smisla? Ker zabijanje atomov med sabo recimo se je sigurno kakšnemu forumašu zdelo metanje denarja skozi okno.
Ne, nisem. Samo zdi se mi. Glej naslednja 2 odziva na moj komentar, kako se argumentirano spodbija mnenje. They succeeded. You failed.
Antifašizem je danes poslednje pribežališče ničvredneža, je ideologija ničesar
in neizprosen boj proti neobstoječemu sovražniku - v zameno za državni denar
in neprofitno najemno stanovanje v središču Ljubljane. -- Tomaž Štih, 2021
Antifašizem je danes poslednje pribežališče ničvredneža, je ideologija ničesar
in neizprosen boj proti neobstoječemu sovražniku - v zameno za državni denar
in neprofitno najemno stanovanje v središču Ljubljane. -- Tomaž Štih, 2021
Ce se dokaze P!=NP, potem je to dokaz, da taki algoritmi sploh ne obstajajo.
Kaj zdaj ta ! za vraga pomeni!? Faktorsko!?
Morda (vsaj) kakšen primer NP-polni.
Noben človek ni otok, popolnoma sam zase; smrt slehernega človeka vzame
del mene, ker pripadam človeški vrsti; in zato nikdar ne pošiljaj poizvedovat,
komu zvoni; zvoni tebi.
Se ubadam z ralnim problemom razdelitve mačk med 4 sodnike. Če mam samo 15 mačk, lahko računalnik v nekaj sekundah preveri vse možne razdelitve in najde najboljšo. Če mam 30 mačk bi preverjanje vseh trajalo že nekaj let, realna razstava 200 mačk pa bi zahtevala 1050 let.
Kaj pa je kriterij za najboljšo rešitev?
Namreč vsi problemi so lahko rešljivi zelo hitro. Ne obstaja pa nek univerzalen algoritem, ki bi lahko rešil vse NP probleme. Lahko pa se tipizira algoritme po tipih problemov. To pa potem pomeni pospešitev reševanja, ja. Če iščeš P = NP na določenem podtipu problemov, se rešitev za to da najti. Če iščeš na splošno nek dokaz, je nemogoče. Nemreč razporejanja mačk in iskanja mailman poti se ne lotevaš na enak način.
Sprašuješ konkretno ali splošno? Konkretno ni pomembno, splošno pa detajli zopet niso pomembni.
Namreč vsi problemi so lahko rešljivi zelo hitro.
"Lahko" v smislu "mogoče" ali v smislu "znamo". V drugem smislu imamo kup problemov ki nikako niso rešljivi zelo hitro. Pogosto vesolje ne bo obstajalo dovolj dolglo za določitev najboljše možne rešitve.
Ne obstaja pa nek univerzalen algoritem, ki bi lahko rešil vse NP probleme.
Catch je, da ravno tega ne vemo. Ne vemo da obstaja, ne vemo da ne obstaja.
Nemreč razporejanja mačk in iskanja mailman poti se ne lotevaš na enak način.
Mogoče ne, mogoče pa ja. Obakrat je naloga da izmed kupa različnih možnosti identificiraš tisto ki je zagotovo najboljša.
Včasih je možno stuhtat 'hevristiko', ki kombinatorično eksplozijo možnih rešitev zreducira na polinomsko zahtevnost, a garancije vnaprej ni, odvisno od konkretnega problema in prostornine lobanje, ali bo to uspelo al ne. Recepta žal ni.
Rešitev tega problema je preprosta: problema ni, je samo stvar interpretacije in perspektiva rešitve - univerzalna rešitev na vsak problem, ki ga definira situacija
Sprašuješ konkretno ali splošno? Konkretno ni pomembno, splošno pa detajli zopet niso pomembni.
Namreč vsi problemi so lahko rešljivi zelo hitro.
"Lahko" v smislu "mogoče" ali v smislu "znamo". V drugem smislu imamo kup problemov ki nikako niso rešljivi zelo hitro. Pogosto vesolje ne bo obstajalo dovolj dolglo za določitev najboljše možne rešitve.
Ne obstaja pa nek univerzalen algoritem, ki bi lahko rešil vse NP probleme.
Catch je, da ravno tega ne vemo. Ne vemo da obstaja, ne vemo da ne obstaja.
Nemreč razporejanja mačk in iskanja mailman poti se ne lotevaš na enak način.
Mogoče ne, mogoče pa ja. Obakrat je naloga da izmed kupa različnih možnosti identificiraš tisto ki je zagotovo najboljša.
Včasih je možno stuhtat 'hevristiko', ki kombinatorično eksplozijo možnih rešitev zreducira na polinomsko zahtevnost, a garancije vnaprej ni, odvisno od konkretnega problema in prostornine lobanje, ali bo to uspelo al ne. Recepta žal ni.
Poznaš rek, zaradi dreves ni videl gozda? Matematiki se včasih preveč ukvarjajo z nepomembnimi razlikami.
Če pogledaš recimo sum dveh kupčkov številk. Kolikokrat lahko razporediš tiste številke noter na različna mesta v kupčku? Ker ni nobene odvisnosti od tega na katerem mestu leži števka, je rezultatov ogromno, rešitve problema pa ne, ker ne veš, kaj iščeš. Takoj, ko okarakteriziraš, da bi na enem mestu rad imel tako številko, se možnosti drastično zmanjšajo in čas kalkulacije postane kratek.
Rešitve problemov zahtevajo okarakteriziran set zahtev.
Drugače samo pljuvaš ven vse možne in nemožne rešitve. Potem boš pa spet moral porabiti ogromno časa, da prečešeš te rezultate.
Postavi kriterije in rešitev problema bo dosegljiva hitro. Brez seta zahtev je navadna kombinatorika in to v praksi nima velikega pomena.
Na tak način reševanje problemov ohranjaš deterministično. Če moraš vedno znova ugotavljat način rešitve problema, ki si ga prej ugotovil iz prejšnjih podobnih problemov...ustvarjaš amnezijo. Zato se dolžina časa vedno znova resetira na abnormalne dolžine in tako lahko napišeš, da je čas iskanja neskončen.
Rešitev P = NP problema ni v eni sami rešitvi, ampak je rešitev konstrukt iz večih rešitev.
Mogoče ne, mogoče pa ja. Obakrat je naloga da izmed kupa različnih možnosti identificiraš tisto ki je zagotovo najboljša.
Vidiš. Govoriš, ampak se ne zavedaš, kaj govoriš. Kako veš, da je rezultat najboljša rešitev? Ti povem. Moral si postaviti nek kriterij, nek parameter po katerem se orientiraš in iščeš rešitev.
P = NP ponazarja idea vs practical solutions. Idej, možnih in nemožnih je neskončno. Kolikor ti jih kombinatorika napljuje ven. Praktičnih rešitev (zahteva karakteriziran set zahtev) pa ne in se jih da dobiti enostavno.
Vidiš. Govoriš, ampak se ne zavedaš, kaj govoriš. Kako veš, da je rezultat najboljša rešitev? Ti povem. Moral si postaviti nek kriterij, nek parameter po katerem se orientiraš in iščeš rešitev.
Vsi od naštetih problemov imajo deterministične najboljše rešitve (ki jih je pogosto lahko več, a so med seboj popolnoma enakovredne).
P = NP ponazarja idea vs practical solutions. Idej, možnih in nemožnih je neskončno. Kolikor ti jih kombinatorika napljuje ven. Praktičnih rešitev (zahteva karakteriziran set zahtev) pa ne in se jih da dobiti enostavno.
Kako po tvoje enostavno razbiješ svetovno kriptografijo?
P = NP ponazarja idea vs practical solutions. Idej, možnih in nemožnih je neskončno. Kolikor ti jih kombinatorika napljuje ven. Praktičnih rešitev (zahteva karakteriziran set zahtev) pa ne in se jih da dobiti enostavno.
Kako po tvoje enostavno razbiješ svetovno kriptografijo?
Če znaš hitro razbiti številko na prafaktorje...
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!
Ja, ampak en algoritem še ni dokaz, da so možni povsod. Jaz mislim, da je najprej treba dokazati, da so vsi NP-ji rešljivi v P. Kako, nimam pojma ampak dokaz zagotovo ne bo algoritem.
Tukaj se motis. Verjetno sicer lahko dokazes, da so da so vsi NP resljivi v P po drugi poti, ampak obstoj zgolj enega NP algoritma, resljivega v P pomeni, da so vsi NP-polni problemi resljivi v P. Iz tega enega algoritma moras potem iskati "zgolj se" polinomsko prevedbo na ostale probleme. Tako da bi rekel da je mnogo bolj verjetno in hkrati prakticno, ce dokaz pride v obliki algoritma. Ce to dejansko drzi, potem je obstoj dokaza P=NP prakticno irelavanten (razen ce dejansko pride prej in seveda da odgovor na vprasanje a je to sploh mogoce).
Protidokaz pa seveda nikakor ne more obstajati v obliki algoritma, ce pa ta sploh ne obstaja.
Aha, štekam. Se pravi je še vedno dilema kaj iskati. Dokaz, ki ni algoritem, ali kar direktno algoritem. Vsekakor je bolj praktično, če najdemo algoritem. Bi imeli že rešitev za vsaj en problem. Ampak po drugi strani pa lahko z iskanjem algoritma iščemo nekaj kar sploh ne obstaja. Se pravi ali iskati iglo v kopici sena, za katero sploh ne vemo če je v kopici, ali najprej ugotoviti ali je igla v kopici in jo nato iskati. Koliko težak pa je ta "zgolj še" za matematike? Ali je težko najti algoritme za ostale NP-je, če ga za enega že imamo? Ampak se pa vsi strinjamo, da bi potrditev teorema zelo popestrila prihodnost, mar ne?
Noben človek ni otok, popolnoma sam zase; smrt slehernega človeka vzame
del mene, ker pripadam človeški vrsti; in zato nikdar ne pošiljaj poizvedovat,
komu zvoni; zvoni tebi.
P = NP ponazarja idea vs practical solutions. Idej, možnih in nemožnih je neskončno. Kolikor ti jih kombinatorika napljuje ven. Praktičnih rešitev (zahteva karakteriziran set zahtev) pa ne in se jih da dobiti enostavno.
Kako po tvoje enostavno razbiješ svetovno kriptografijo?
Če znaš hitro razbiti številko na prafaktorje...
Če pa ne znaš hitro razbt številko na prafaktorje, ti gre pa razbitje svetovne kriptologije nekoliko počasneje.....
Zato je vedno priporočljivo, da pri nabavi nove mašine - PC, pogledaš, koliko močno kladivo (macolo) vsebuje.
Noben človek ni otok, popolnoma sam zase; smrt slehernega človeka vzame
del mene, ker pripadam človeški vrsti; in zato nikdar ne pošiljaj poizvedovat,
komu zvoni; zvoni tebi.
P = NP ponazarja idea vs practical solutions. Idej, možnih in nemožnih je neskončno. Kolikor ti jih kombinatorika napljuje ven. Praktičnih rešitev (zahteva karakteriziran set zahtev) pa ne in se jih da dobiti enostavno.
Kako po tvoje enostavno razbiješ svetovno kriptografijo?
Najhitreje...najdeš ključ (tajni del RSA enkripcije za določeno institucijo, če je to unikat ali velja globalno) - hekanje, social engineering, vlom, dobesedna kraja,...
Drugi najhitrejši pa je prisluškovanje miljardam transakcij, ki se izvedejo v svetu. Primerjaš kode in skozi statistiko in evolucijske algoritme gradiš prevajalnik (tako kot se učiš samostojno tujega jezika, ko opazuješ ljudi med pogovorom - enkripcija je podvržena enakim principom, ker gre le za še en jezik). Namreč vsako enkripcijo in vsako copyright zaščito se da zlomiti. Ne glede na to koliko dolga je, ker obstajata ključavnica in ključ zato, da lahko vstopi uporabnik ergo tat lahko inteligentno poustvari pogoje za dostop.
Z opazovanjem obnašanja poslane kode lahko oblikuješ ključ z imitacijo ključavnice in tako prideš v sisteme. Več samplov dobiš, hitreje lahko ustvariš sliko, kako izgledata ključavnica in ključ, ker je ključavnica vedno fiksna (RSA ima recimo tajni del, ki mora biti vedno neodkrit - single point of failure).
Če je ključavnica pasivna, kot v primeru RSA, potem prisluškuješ samo eni strani - klientom. Če ključavnica potem sporoča kaj nazaj, prestrežeš ta info (zelo verjetno so notri informacije za pogoje za naslednji ključ) in na podlagi tega zgradiš repozitorij uspešnih transakcij med računalnikoma...s tem ustvariš model, kako ključ in ključavnica komunicirata svoje "lozinke". To počneš na milijonih računalnikov hkrati po svetu in rešitev bo precej hitro na dlani. Kakšen cryptomining server iz nekaj 10 GPGPUjev bi znal to hitro zlomit.
Zato rešitev te zagonetke ni izključno eden algoritem, ampak glavni algoritem, ki se uči in prilagaja glede na vse ostale podalgoritme, ki jih ima v repozitoriju - v bistvu AI.
Tu znanstveniki gledajo preveč enodimenzionalno tako kot v primeru svetlobne hitrosti...ampak to je že druga tema.
Vsak problem ima svoj optimalen pristop glede časa in vlaganja energije za rešitev. Zato je iskanje singularne rešitve nesmisel.
) 
