Mikä on matematiikan tärkein avoin ongelma? Minkä ongelman ratkaiseminen toisi vettä janoisille ja leipää nälkää näkeville?
..siis sinun mielestäsi.
..siis sinun mielestäsi.
Tärkein avoin ongelma?
mikä on
10657
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 10
Vanhimmat
mahtimatemaatikon mielestä tärkein ongelma on hänen mahtava palkkansa ja kuinka sitä saataisiin isommaksi.
Tuolla vesi-leipä-periaatteella ei mikään niistä. Enkä muutenkaan pistäisi niitä järjestykseen.
Ehkä matematiikan suurin ongelma on se, että monet osaavat matematiikkaa niin huonosti, että heille on helppo valhetella kaikenlaista. Joku voisi sanoa, että ei tämä ole matikan, vaan ihmisten ongelma. Jätän ajatuksen tähän.
Matematiikan eri osa-alueiden tutkijat antaisivat eri vastauksia. Esimerkiksi topologi ei välttämättä ole lainkaan kiinnostunut Schinzelin hypoteesista H toisin kuin lukuteoreetikot. Mutta joitakin kuuluisia ongelmia on olemassa, kuten vaikkapa Clay-instituutin millennium-ongelmat, joista Poincarén otaksuma on todistettu ja kuulemani huhun mukaan joku lupaava yritys Riemannin hypoteesista on tarkastettavana. Yhdenkin millennium-ongelman ratkaisija saisi kyllä palkinnollaan ostettua jonkin aikaa kotiinsa vettä ja leipää.
Kysymys oli puhtaasti mielipiteestä, eli minkä kukin nostaisi tärkeimmäksi.
Mielestäni P ?=? NP on nykyaikana aika oleellinen kysymys. Sen ratkaiseminen saattaisi tuottaa harmaita hiuksia mm. salausjärjestelmien kehittäjille ja toisaalta auttaa algoritmien kehittämisessä.
Salausjärjestelmän tekijöille ei tulisi vain harmaita hiuksia jos osoitetaan että P=NP, vaan se kaataisi kaikki lupaavat järjestelmät.
Jos taas osoitetaaan P=/=NP, niin salausjärjestelmän tekijät saavat lisää toivoa, mutta esim. optimointiongelmien kanssa pelaavat voivat sen menettää. P=/=NP ei takaa että salausjärjestelmät olisivat toimivia.
P=/=NP tarkoittaa sitä, että NP-luokassa löytyy ainakin 1 inhottava ongelma kutakin algoritmia kohden. Salailijoille pitäisi olla voimassa: NP-luokan ongelmat ovat keskimäärin inhottavia kaikille algoritmeille.
"Salausjärjestelmän tekijöille ei tulisi vain harmaita hiuksia jos osoitetaan että P=NP, vaan se kaataisi kaikki lupaavat järjestelmät. "
Jos P=NP, niin se ei *välttämättä* kaataisi salausjärjestelmiä. Se *saattaisi* johtaa siihen (jopa melko varmasti), mutta se ei ole mitenkään varmaa.
"Jos taas osoitetaaan P=/=NP, niin salausjärjestelmän tekijät saavat lisää toivoa, "
Miten he siitä lisää toivoa saisivat? Nythän "oletetaan", että P=/=NP ja meno perustuu jokseenkin siihen. Jos osoitetaan, että P=/=NP, niin se ehkä antaisi rauhallisemmat yöunet joillekin salausjärjestelmien kehittäjille, mutta ei sekään sinänsä mitään varmaksi kerro (jos ei todistus itsessään anna jotain varmuutta).
"P=/=NP tarkoittaa sitä, että NP-luokassa löytyy ainakin 1 inhottava ongelma kutakin algoritmia kohden."
Mitä tämä tarkoittaa? En ymmärrä ollenkaan viimeistä kappaletta tekstistäsi.
P on niiden päätösongelmien joukko, jotka ratkeavat deterministisellä (Turingin) koneella polynomisessa ajassa. Luokka NP koostuu taas niistä päätösongelmista, jotka ratkeavat polynomisessa ajassa epädeterministisellä (Turingin) koneella. Intuitiivisesti eroa voisi kuvata esim. niin, että jos päätösongelma on luokassa P, niin sille voidaan etsiä varmasti oikea ratkaisu polynomisessa ajassa kun taas luokassa NP olevalle ongelmalle oikea ratkaisu voidaan tarkistaa oikeaksi polynomisessa ajassa. Ja on tietysti päivänselvää, että P on NP:n osajoukko ja kysymys onkin siitä onko sisältyvyys aitoa vai ei.
"Inhottava" ongelma eli ongelma jota ei voida ratkaista polynomisessa ajassa, vaikka tietysti ratkaisuehdokas voidaan tarkastaa polynomisessa ajassa. Eli NP-luokassa on (oletettavasti)probleemia jotka pahimmillaan vievät aikaa eksponentiaalisesti ongelman kokoon nähden.
Kun taas salausjärjestelmät olettavat että NP-luokassa on ongelmia jotka keskimäärin vievät aikaa eksponentiaalisesti.
Ero on siis siinä puhutaanko pahimmasta tapauksesta vai keskimääräisestä tapauksesta.
Julkinen salaus perustuu ns. yksi-suuntaisiin funktioihin. Jos P=NP se tarkoittaa että yksi-suuntaisia funktioita ei ole olemassa. Mutta P=/=NP ei vielä sekään takaa että yksi-suuntaisia funktioita olisi olemassa. Välttämätön ehto, ei riittävä.
""Inhottava" ongelma eli ongelma jota ei voida ratkaista polynomisessa ajassa"
Tarkoitat varmaan, että "inhottavan" ongelman ratkaisu on vähintään eksponentiaalinen aikavaatimukseltaan, koska muutenhan logaritmisessakin ajassa ratkeavat olisivat "inhoittavia".
"Julkinen salaus perustuu ns. yksi-suuntaisiin funktioihin. Jos P=NP se tarkoittaa että yksi-suuntaisia funktioita ei ole olemassa."
Taidat puhua jostain ihan eri asiasta kuin minä. Miten P =?= NP liittyy siihen mitä funktioita on olemassa? Mitä tarkoitat sillä, että "funktio on olemassa"? Mitä tarkoitat funktiolla? Entä yksisuuntaisella funktiolla?
Aihe on mielenkiintoinen, mutta en yksinkertaisesti ymmärrä mitä koitat sanoa.
Yksisuuntainen funktio on sellainen funktio jonka arvo voidaan laskea polynomisessa ajassa (tai nopeammin), kun taas funktion käänteisfunktio on keskimääräiseltä aikavaatimukseltaan eksponentiaalinen.
Jos nyt P=NP, niin se tarkoittaa, että jokaisen funktion, jonka arvo voidaan laskea polynomisessa ajassa, käänteisfunktio voidaan myös laskea polynomisessa ajassa, eli yksisuuntaisia funktioita ei olisi olemassa, joka tarkoittaa sitä että julkinen salaus olisi mahdotonta.
Meillä on selvästikin käytössämme eri kieli. Minulla yksisuuntainen funktio on ei-injektiivinen, eli tietyssä mielessä "häviöllinen" ainakin joissain pisteissä.
Näin "normaalin" vaativuusteorian puolelta voidaan sanoa, että tunnetusti P =/= E joten jos P = NP, niin NP =/= E, eli pahimman tapauksen luokittelulla huolta ei olisi.
Mutta etkö sinä oikeastaan sano, että funktion arvon laskeminen on luokassa P ja käänteisarvon laskeminen luokassa NP ja koska *oletettavasti* NP = E, niin huolta ei ole? Nimittäin jos käänteisarvon laskeminen olisi luokassa E, niin P=NP ei muuttaisi tilannetta, koska P=/=E? Vai poikkeaako keskimääräisen vaativuuden käyttäminen jotenkin pahimman tapauksen luokittelusta?
No, niin tai näin, tuskin julkinen salaus kuitenkaan P=NP vastaukseenkaan kaatuisi. Onhan PRIMES:n luokassa P, mutta algoritmi on niin tolkuttoman korkeaa astetta, että ei sillä ole käytännössä käyttöä.