Deep learning network ja koneäly

[nokkaelain]

Mies vaikuttaa matemaatikon arkkityypiltä. Jää varmaan historiaan ensimmäisenä ja viimeisenä ihmisenä, joka ratkaisi Millenium-ongelman.

Redditissä jossain math-threadissa ennustettiin sitä, ratkaiseeko ihminen enää yhtään noista Clay-instutuutin ongelmista. Keskustelu meni siihen, että on "coping" väittää, että ihminen pärjäisi enää: pari vuotta sitten LLM ei osannut edes opiskelijatason matikkaa, muutama kuukausi sitten ei uskottu, että LLM osaisi ratkaista mitään merkittävää jne. Ja uskotaan, että lähes kaikki nuo ongelmat ratkeavat nyt muutamssa kuukaudessa.

Hatusta vedettynä myös arvioita kuinka vaativa mikäkin noista on. Parista muusta noista ongelmista on huhuja, että OpenAI tai Anthropic olisi lähellä. Siis Hodge ja BSD. Googlen AI:n mielestä viimeksi mainitu on "vaikein" kaikista.

Jäitä hattuun. Riemannin hypoteesia on varmaan kauimmin yritetty selvittää ja yleinen käsitys on, että tarvittaisiin ihan jotain uutta. On aika eri asia laittaa AI etsimään vastaesimerkkiä sen jälkeen kun on tullut viitteitä siitä, että sellainen voisi olla (Navier-Stokes) kuin yrittää todistaa oikeaksi jotain, mikä näyttää melko varmasti pitävän paikkansa. Jos Riemannin hypoteesiin löytyisi vastaesimerkki, suuri osa siitä riippuvaista lukuteoriaa kaatuisi.

P vs. NP on vielä varmemmin niin että P ≠ NP. Ei vaan ole niin minkäänlaista käsitystä, miten sen voisi osoittaa. Ihan arkijärki sanoo, että P=NP ei voi pitää paikkansa: Impagliazzo's Five Worlds. Vain kahdessa viimeisessä esim. kryptografia on mahdollista ja P=NP on siis vahvin noista viidestä vaihtoehdosta. Jos osoitettaisiin, että P=NP, sillä olisi iso vaikutus vs. nuo muut ongelmat ovat enemmänkin matemaattisesti mielenkiintoisia. Käsittääkseni ko lauseen osoittamisesta seuraisi se, että olemassa oleveilla menetelmillä olisi löydettävissä algoritmi, joka tekisi kaikista kaikista optimointiongelmista triviaaleja.

[nokkaelain]

Täytyy sanoa, että P vs NP:stä ilmais-AI:ltakin kysellessä putoaa kaninkoloon. Monenlaista on näemmä yritetty ja törmätty seinään. Yksi uusimmista lähetymisatavoista:

Geometric Complexity Theory (GCT) is a highly ambitious, long-term research program designed explicitly to solve the P vs. NP problem (and related complexity questions) without running into the mathematical walls.

In short: GCT tries to prove that P ≠ NP by showing that certain multi-dimensional geometric shapes are fundamentally incompatible.

In standard computer science, we think of an algorithm as a sequence of code steps. In GCT, algorithms are transformed into polynomials, which are then treated as geometric surfaces (varieties) in a massive, multi-dimensional space.

Aika abstraktia että algoritmit muutettaisiin geometriaksi. Tosin edellä mainitsemani algoritmin konstruktio, jos P=NP kertoisi vain, että minkä vaan optimointongelman ratkaiseva algoritmi löytyisi polynomiaalisessa ajassa, kun käydään läpi kaikki mahdolliset eri mittaiset tietokoneohjelmat (Turing-koneet) vuorotellen läpi. Jos P ≠ NP, sitä ei löydy NP-ongelmille.