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.Edit: ei näemmä tarvittaisi kuin käydä kaikki mahdolliset algoritmit yksi kerrallaan läpi - kyllä se sieltä tulee vastaan jos on matemaattisesti osoitettu.

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

[nokkaelain]

Kysyin vielä, miten AI ratkaisisi P vs NP -ongelman:

Phase 1: Creating the "Sandbox" (Using Lean)
The AI translates the definitions of Turing machines, polynomial time, and NP-completeness into Dependent Type Theory. Every time the AI proposes a logical step, Lean instantly evaluates it and says "Valid" or "Error."

Selvää tähän asti...

Phase 2: Solving the "Sub-Problems" via Reinforcement Learning
Instead of aiming for the grand prize immediately, the AI would be trained to automatically close thousands of smaller, unproven lemmas in Algebraic Geometry and Representation Theory—the exact building blocks needed for Geometric Complexity Theory (GCT).

Pitää vaan ratkaista tuhansia toistaiseksi tuntemattomia lauseita matematiikan uusimmilla aloilla ("representation theory" oli käytössä Fermat'n teoreeman todistuksessa.)

Phase 3: Attacking via Geometric Complexity Theory (GCT)
1. Symmetry Matching: The AI would analyze the high-dimensional "orbit closures" of the Determinant and the Permanent polynomials.
2. Kronecker Coefficients: A major bottleneck in GCT is calculating incredibly complex, abstract numbers called Kronecker coefficients to find "structural obstructions" between the two geometric shapes. Humans find these calculations brutally tedious.

Mikään ei takaa, että mitään löytyy...

Phase 4: Attacking via Bounded Arithmetic (The "Near P=NP" Hunt)
Alternatively, if the AI is searching for a way to prove that the problem is independent of certain axiom systems

Matemaatikot ovat vahvasti sitä mieltä, ettei tämä ole oikea tie, koska on osoitettu, että P olisi käytännössä melkein sama kuin NP: Se ei kuitenkaan johtaisi samaan absurdiuteen kuin P=NP, jossa ei olisi mm. pseudorandom-lukuja (niille kaikille olisi siis polynomiaalisessa ajassa toimiva algorimi, joka löytäisi lukusarjan riippumatta miten se on tehty.)

The Ultimate AI Paradox
* If P = NP; The universe is a place where finding a solution is just as easy as verifying one. In a P=NP world, an AI looking for a proof will find it almost instantly
* P=/= NP; The AI will have to work just as hard as human mathematicians, grinding through the exponential search space of geometry and logic

"Almost instantly" eli polynomiaalisessa ajassa eli saisi odottaa kunnes viimeinenkin protoni on hajonnut.

[nokkaelain]

Kävin vielä tuntikausien keskustelun AI:n kanssa, jotta ymmärsin (mielestäni riittävästi) Yang-Millsin. Se on vähän kuin Navier-Stokes steroideilla. Samantapaisia yhtälöitä mutta ihan hele-vet-in paljon karvaisempia.