» »

Problem P = NP ostaja nerešen

Problem P = NP ostaja nerešen

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.

65 komentarjev

strani: « 1 2

WarpedOne ::

Matej Huš, bravo.
One does not know what one does not know.

FireSnake ::

Tu imamo tako pametne osebke, da sem prepričan, da bodo s tem problemom z levo roko pometli.
"In The Sound Of Silence Time Is Standing Still"
Poglej, in se nasmej ----> www.vicmaher.si ;)

MrStein ::

Kaj ima demokracija veze?
Teštiram če delaž - umlaut dela: ä ?

ales85 ::

MrStein je izjavil:

Kaj ima demokracija veze?

Sprejetje večinskega prepričanja kot dejstvo :)

GreenT ::

Kot človek, ki se je boril za dvojke pr matematki,...lahko samo rečem: WTF did i just read?...

Izi ::

ales85 je izjavil:

Sprejetje večinskega prepričanja kot dejstvo :)

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.

usoban ::

GreenT je izjavil:

Kot človek, ki se je boril za dvojke pr matematki,...lahko samo rečem: WTF did i just read?...

Vzemi za primer sudoku. Preveriti, ali je pravilno resen, je enostavno. Na drugi strani je resevanje sudokuja tezji postopek.

V kolikor bi veljal P = NP, potem je resevanje sudokuja prav tako tezko, kot preverjanje njegove resitve (ob uporabi primernega postopka).

---
9x9 sudoku je sicer slab primer, ampak n^2 x n^2 je pa np-poln.

Zgodovina sprememb…

  • spremenil: usoban ()

smacker ::

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 ;)

carota ::

z rešitvijo katerega lahko od Clay Mathematics Instituta dobimo milijon dolarjev nagrade (kar je nekoliko več od Nobelove nagrade)

Zanimivost: Finančni del Nobelove nagrade je 8.000.000 SEK, v USD je to trenutno 1.004.079 USD. Trditev v novici ne drži. :)

usoban ::

smacker je izjavil:

n^2 x n^2 = n^4 kar je še vedno polinom... NP bi bilo 2^n ali 4^n

z n^2 x n^2 sem mislil velikost grida, ne casovne kompleksnosti :)


Iz linka, ki si ga postal zgoraj:

The general problem of solving Sudoku puzzles on n2×n2 grids of n×n blocks is known to be NP-complete.


smacker je izjavil:


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 :)

reeves ::

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.

usoban ::

Bilo je veliko poskusov, ampak so do sedaj vsi padli (kot bo zelo verjetno tudi zgornji).

Evolve ::

Dokler se bo folk ukvarjal s takimi problem.. adijo pamet

hojnikb ::

Evolve je izjavil:

Dokler se bo folk ukvarjal s takimi problem.. adijo pamet

dokler bo folk dajal takšne poste... adijo pamet.
#teamred
BigBox: Asus P8Z77-V, i5 3570K, 8GB DDR3, 1TB HDD & 180GB SSD, RX 480, W10
LappyBox: Akoya P6660, 1080p, 8GB DDR3L, 840PRO 256GB, 930M, i3 6100U, W10

FTad ::

V primeru, da je problem enkrat dokazan, kako bi to lahko izkoristili v naso korist? Na katerih podrocjih bi se najbolj poznalo?

SimplyMiha ::

hojnikb je izjavil:

Evolve je izjavil:

Dokler se bo folk ukvarjal s takimi problem.. adijo pamet

dokler bo folk dajal takšne poste... adijo pamet.

Pusti ga no, saj vidiš, da je še vedno v procesu evolucije.

Eandro5res ::

Evolve je izjavil:

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 ;)

Zgodovina sprememb…

reeves ::

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.

Markoff ::

ales85 je izjavil:

MrStein je izjavil:

Kaj ima demokracija veze?

Sprejetje večinskega prepričanja kot dejstvo :)

To spominja na slovensko javno upravo.
Ad astra per aspera

Markoff ::

reeves je izjavil:

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.
Ad astra per aspera

nekikr ::

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.

reeves ::

Č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.

usoban ::

Markoff je izjavil:

reeves je izjavil:

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).

Obstaja tudi film: http://www.imdb.com/title/tt1801123/ :D

Zgodovina sprememb…

  • spremenil: usoban ()

reeves ::

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.

WarpedOne ::

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.
One does not know what one does not know.

Raptor F16 ::

Včasih se vprašam, zakaj nisem šel študirat matematike.
Säge, Feile und Schw**z - benutzt man ganz.

shadeX ::

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).
You have succeeded in life
when all you really want
is only what you really need.

Matthai ::

Evolve je izjavil:

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.
All those moments will be lost in time, like tears in rain...
Time to die.

reeves ::

@WarpedOne

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 :D)

usoban ::

reeves je izjavil:

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.

Unilseptij ::

WarpedOne je izjavil:

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.

Markoff ::

nekikr je izjavil:

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.
Ad astra per aspera

Markoff ::

WarpedOne je izjavil:

.

Hvala za super razlago!
Ad astra per aspera

FrRoSt ::

usoban je izjavil:


Ce se dokaze P!=NP, potem je to dokaz, da taki algoritmi sploh ne obstajajo.

Kaj zdaj ta ! za vraga pomeni!? Faktorsko!? 8-O

Morda (vsaj) kakšen primer NP-polni.
Le uporabnik Marvik,AndrejO,Buggy,amacar,3muche5me,Packistan-ec,...
... in Ziga Dolhar ter spletno uho imajo možnost,
da v prihodnosti preprečijo genocid.

Raptor F16 ::

FrRoSt je izjavil:

usoban je izjavil:


Ce se dokaze P!=NP, potem je to dokaz, da taki algoritmi sploh ne obstajajo.

Kaj zdaj ta ! za vraga pomeni!? Faktorsko!? 8-O

Morda (vsaj) kakšen primer NP-polni.


Pri programiranju je != sintaksa za (NI ENAKO)
Säge, Feile und Schw**z - benutzt man ganz.

Sakin ::

Evolve je izjavil:

Dokler se bo folk ukvarjal s takimi problem.. adijo pamet


Dokler se bodo pojavljali takšni komentarji pod naravoslovnimi članki, bo Slovenija mentalno država 3. sveta.
Na Nach Nachma Nachman Meuman!

Grey ::

WarpedOne je izjavil:

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.

Zgodovina sprememb…

  • spremenilo: Grey ()

WarpedOne ::

Kaj pa je kriterij za najboljšo rešitev?

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.
One does not know what one does not know.

keworkian ::

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
Obscenities in B-Flat

Grey ::

WarpedOne je izjavil:

Kaj pa je kriterij za najboljšo rešitev?

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.

jype ::

Grey je izjavil:

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).

nekikr ::

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?

Yacked2 ::

nekikr je izjavil:

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!

reeves ::

usoban je izjavil:

reeves je izjavil:

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?

FrRoSt ::

reeves je izjavil:


Aha, štekam.


Ne štekaš. ;) Zadevo šteka Grey. 8-)
Le uporabnik Marvik,AndrejO,Buggy,amacar,3muche5me,Packistan-ec,...
... in Ziga Dolhar ter spletno uho imajo možnost,
da v prihodnosti preprečijo genocid.

FrRoSt ::

Yacked2 je izjavil:

nekikr je izjavil:

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. :))

WarpedOne je izjavil:

.... Recepta žal ni.


Ta stavek zmaga! ;) ABSOLUTNO. 8-)

Se ga pa išče. :D Po možnosti Univerzalnega. :)

Razpisana tudi primerna nagrada. :))
Le uporabnik Marvik,AndrejO,Buggy,amacar,3muche5me,Packistan-ec,...
... in Ziga Dolhar ter spletno uho imajo možnost,
da v prihodnosti preprečijo genocid.

Zgodovina sprememb…

  • spremenilo: FrRoSt ()

reeves ::

FrRoSt je izjavil:

reeves je izjavil:


Aha, štekam.


Ne štekaš. ;) Zadevo šteka Grey. 8-)


Upam, da ne boš zameril, če neargumentirano izpodbite moje objave od nekoga, ki ne ve kaj pomeni NP!=P ne bom jemal resno. :P

Z veseljem pa bom konzumiral kakršenkoli popravek ali dodatno pojasnilo od npr. W1, usoban, jype,...

Grey ::

nekikr je izjavil:

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.

MrStein ::

Uf, nekdo je rekel, da Grey šteka?
Ker neja. Sploh ne.
Teštiram če delaž - umlaut dela: ä ?
strani: « 1 2


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Problem P = NP ostaja nerešen (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
654979 (487) reeves
»

[Java] Kako izračunati hash diska.

Oddelek: Programiranje
331676 (506) kunigunda
»

Januarski poizkus dokaza problema P = NP neuspešen

Oddelek: Novice / Znanost in tehnologija
63169 (1705) Thomas
»

Predstavljen poizkus dokaza P = NP

Oddelek: Novice / Znanost in tehnologija
134848 (3077) gzibret
»

Problem P ≠ NP za zdaj ostaja nerešen

Oddelek: Novice / Znanost in tehnologija
256838 (3674) pecorin

Več podobnih tem