A Chicago-Budapest expressz
Eredeti szerző: jotunder
(dolgoztam ezen a címen egy kicsit)
Babai László idén novemberben egy háromrészes chicago-i előadássorozatban jelentette be, hogy kvázipolinomiális algoritmust talált a gráfizomorfizmus problémára. Tegnap kora délelőttől késő estéig (nem tudom, hogy pontosan meddig, én az előadás ún.központi részén voltam csak ott, amikor a Vígszínházban szünet volt, akkor beszéltem valakivel telefonon, hogy még tart az előadás). beszélt a Rényi Intézetben, ami teljesen elképesztő.
A gráfizomorfizmus probléma megoldásáról az Index is címlapon számolt be, azóta a kézirat is nyilvánossá vált. Nagyjából arról van szó, hogy van egy tetszőlegesen bonyolult szerkezetű n darabkából álló általánosított Rubik-kocka és el kellene dönteni exp(polylog(n)) időben azt, hogy egy bizonyos állapotból elérhető-e egy bizonyos másik állapot. Nem várható, hogy a probléma polinomiális időben legyen megoldható, mert két szorzótáblájával adott azonos méretű véges csoport izomorfiájának (ez egy könnyebb probléma) megoldására stabilan és teljesen reménytelenül egy merev kvázipolinomiális határ van (a logaritmikus szorzó konstanst nem sikerült 37 éve 1-ről 0.9999999-re vinni). A gráfizomorfizmus probléma Babai-féle megoldása nagyon bőven az április tréfa kategóriában volt, olyan jellegű áttörés, amire senki sem számított, és még mindig meg vannak döbbenve a komplexitás-elmélészek.
Ez az egész úgy világraszóló eredmény, ahogy van, nem nagyon tudnám, és nem is nagyon akarom hasonlítgatni más dolgokhoz, de kicsit talán egy 9 méteres távolugrásra vagy egy 9.5-ös száz síkra emlékeztet, elvileg képes lehet rá egy ember, gyakorlatilag elég nehéz elképzelni.
Babai rögtön azzal kezdte az előadását, hogy a bizonyítás még nincs ellenőrizve, és tegnap hosszú órákat töltött azzal, hogy megteremtse annak lehetőségét, hogy az esetleges hibát megtalálják. Ezt is elég nehéz elmagyarázni a matematika határain kívül.
Nincs szó alkalmazhatóságról, nincs olyan valódi világbeli probléma, ami most majd gyorsabban lesz megoldható, ez egy Mount Everest, és azért kell megmászni, mert ott van.
Egy egészen más Magyarország volt ott tegnap a Rényiben, mint amiről sírdogálni szoktunk ezen a blogon. Van ennek az országnak néhány nagyon vonzó arca, és a magyar kombinatorika-számítástudomány a határterületeivel együtt ezen nagyon vonzó arcok közé tartozik, ez az a része a nemzeti kultúránknak, amelyik messze-messze az európai élvonalhoz tartozik. És nem, nem lesz vörös farok, áthallás, nem nagyon szeretnék ilyesmit, tegnap olyan jó volt kicsinek lenni egy sarokban. Nem kell túlmagyarázni.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16518953-67d8f1cd80280' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16518953&origin=www.orulunkvincent.hu&obj_id=192691293-16518953-67d8f1cd80280&n=1' data-name='like-post-frame-192691293-16518953-67d8f1cd80280' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
És akkor az várhatóan mikor derül ki, hogy tényleg hibátlan-e a bizonyítás?
@jan: talán egy év. lehetnek gyorsító tényezők. egy nagyobb amerikai tanszéken lehet akár 4-5 prof, posztdok, plusz ph.diákok, akiknek ez különösen fontos. és elkezdik együtt olvasni. ez nagyon spéci dolog, egyrészt algoritmuselmélet másrészt csoportelmélet. van ennek is iskolája, és ők már egy ideje nézik. a hivatalos peer-review az simán lehet akár másfél év is.
Bravó! Kombinatorikában mindig is benne voltunk a világ élvonalában, de ez tényleg elképesztő eredmény. Kívülálló, de a matematikát szerető mérnökként is gratulálni tudok csak. Ha a teljes bizonyítás nem is lehet, hogy korrekt, a kidolgozott módszerek és a mellékes lemmák bizonyításai is biztosan hasznosak lesznek. Olyan ez, mint Wiles bizonyítása. Oké, hogy a cél a Fermat-tétel volt, de az út, és a felhasznált eszközök és új kidolgozott területek miatt hasznos a munkája, nem azért, mert következik belőle a Fermat-tétel.
@kerekes pereces: Nekem pont az volt a nagyon erdekes (bar en mar este fel 9-kor eljottem, amikor mar tobb unalom volt, mint izgalom, es mar haromszor keresett a felesegem), hogy majdnem mindegyik resze a bizonyitasnak olyan, amit mar korabban csinalt, korabbi munkaiban mar elojott, csak ott még nem latszott, hogy tenyleg hasznalhato lenne valami tenyleg erdekesre. A cikk irodalomjegyzeke is tele van nem tul fontosnak tuno cikkekkel. De ugy tunik, tudat alatt megis alakulgatott valami a fejeben, meg az egesz teruleten, az elmult 30 evben. A bizonyitas fo hozadeka tehat lehet, hogy nem a forradalmi uj modszerek lesznek, hanem annak felismerese, hogy a regi modszerek igy egyutt mire is hasznalhatoak.
Mondjuk azt azert kiemelte Babai, hogy kapott kritikat, miszerint ez „csak” egy rohadt bonyolult bizonyitas a regi modszerek hasznalataval, de NEM, espedig ITT van az a forradalmi otlet, amire szept 14-en jott ra. Es az tenyleg egy nagyon pofas lepes volt, amiben nem az elmelet mukodtette onmagat, hanem hirtelen valami kulso intelligencia altal mukodtetett furcsa dolog tortent. (De persze nem hasonlitott se Matolcsy, se Szaniszlo hulyesegeire, ugyanis itt van egy konkret feladat, hogy mit kell mukodtetnie az otletnek, es azt nem lehet kicsit, vagy jol-rosszul.) Hogy ez egy mashol is hasznalhato otlet lesz-e, azt persze még senki se tudja.
tudna valaki vazolni, hogy mi a bizonyitas technikai hattere, miert mukodik, es mi ez a szeptember 14-ei otlet?
@jotunder: akkor azt jól vágom, hogy az egész világon 5-6 ember lesz, aki majd elmondhatja magáról, hogy az egész bizonyítást elolvasta, átlátja és érti? izgi ez a világ!
Már az is döbbenetes számomra, hogy blogger érti, amit mond (Legalábbis remélem :))
Mindig csodáltam a matematikusokat… 🙂
Az univerzumban kb 2 db önmagától létező entitás van, „Isten” és a „szám” – bár az elsőben nem vagyok teljesen biztos. Viszont felvetődik, hogy az ősrobbanás/teremtés előtt létezett-e a szám mint entitás. Volt-e értelme pl a „kettő”-nek? (Ha feltételezzük Istennek öröktől fogva létezését, akkor biztosan, szerintem Isten tudta, hogy ő „egy”, és tisztában volt azzal, hogy létezik egytől eltérő számosság is – hogy mit gondolt a nulláról, az megint érdekes kérdés – de mi van, ha mégsem létezik? Gondolom, a matematikának – vagy a filozófiának – van olyan területe, amely ezzel foglalkozik 🙂
@jan: az ertesnek szintjei vannak. egy ilyen bizonyitas teljes megertese az mondjuk ketszaz ora tiszta munka. es hat eleve tudni kell, hogy mi az abra. en egy bizonyos szintig meg tudom ezt erteni, es van egy szint, ami fele kinok kinjaval tudnek csak kerulni, es az meg messze nem a teljesseg. a teljes attekinteshez sajnos az egesznek kepben kell lenni egy idore. azert az osszemerheto egy komoly zongoraverseny majdnem teljes memorizalasaval.
ez egyebkent is olyan, mint a zongora. vannak akik baromira szepen zongoraznak, aztan vannak, akik igazan jol, es felettuk van meg harom-negy szint, es ez a cikk a felso egy-ket szintet reprezentalja. az internetes kommunikacioban a „nagyon durva” kifejezest szoktak erre hasznalni.
@jotunder:
van olyan személy, nem írom le a nevét, aki szerint valamit megérteni nem nehéz, ő pl. bármit képes megérteni.
@DarthVader:
a számok az ember által kitalált fogalmak a mennyiségek tudatosítására.
tehát a „kettő” azóta létezik, mióta az ember megalkotta ezt a fogalmat.
a világegyetemnek nincs tudata amivel a saját mennyiségeit értelmezhetné, így nincs értelme annak a kérdésnek, hogy létezett-e a „kettő” az ősrobbanás előtt.
istenről én azt gondolom, hogy egy pszichológiai jelenség, így aztán nem tud semminek sem tudatában lenni, mivel mint jelenségnek szintén nincs tudata. az ember a saját tudatát vetíti bele isten fogalmába. de én egy csökött ateista vagyok, mostanában ezen a tájon nem ez az irány…
a matematikusokat én is csodálom. nem semmi agyuk van. én hülye vagyok a matekhoz, de mostanában az a merész gondolatom támadt, hogy megpróbálom megérteni a Riemann-geometriát. nem igazán tudom hogyan fogjak neki, gondolom az előzményekben vissza kéne mennem az alapokig, és onnan sorban előre. majd kiderül. ha ugyan sikerül. 🙂 igazából a téridő-fizika miatt érdekelne. már annak is örülnék ha a logikáját megérteném annyira, hogy értsem Dávid Gyula miről beszél a lyutyúbon…
pár napja néztem meg Krausz Ferenc előadását amit az MTA Közgyűlése előtt tartott tavaly az ELI kapcsán. elképesztő lehetőségek. és itt Magyarországon. amilyen szarul állunk világszerte politikai szempontból (mondjuk mikor nem így volt?), olyan reményteli tudományos kutatási irányok vannak. ez azért valahol megnyugtató.
@ingyenebed: a Riemann, illetve ami a terido-fizikahoz kell a Lorentz geometriahoz az ut eleg hosszu. a preciz definiciohoz eloszor bilinearis valos formakat kell megerteni linearis algebraban, aztan tobbvaltozos differencialszamitast es nemi topologiat. kb negyedeves anyag matematikusoknal amig felepitik az elmeletet es az intuiciot. Einsteinnek is vagy 10 evig tartott amig megtalalta a szukseges matematikat.
viszont a grafizomorfizmus problemahoz eleg grafokat megerteni, es ha jol ertem Babai veges csoport elmeletet is hasznal, ez talan mind elso eves egyetemi anyag, esetleg masodeves, ha hasznal reprezentacio elmeletet is. de javitsanak ki akik ertenek valamit Babai munkajabol
@wooddog: Csak a gráfizomorfizmus problémára koncentrálok (ami hülyeség, mert a Rubik-kockás általánosítás nélkül nem is értelmesek a speciális gráfos eset bizonyításának az alapgondolatai, de most mindegy). És remélem, a Babai ezt nem fogja olvasni. Sőt, igazából ne olvassa senki se, ez csak magamnak egy vázlat, hogy jobban lássam, mennyire nem értek semmit se. 🙂
A gráfnál magánál egyszerűbb struktúrákat akarunk találni a gráfban, amiket gyorsan meg lehet találni, és egy gráfizomorfizmus megőriz. Pld, ha két gráf izomorf, akkor ugyanannyi 1-fokú, 2-fokú stb csúcs van bennük (a fokszám a szomszédok száma). Szóval pld a csúcsok felosztása fokszám szerint, az egy ilyen struktúra. Sőt, ha az egyik gráfban van egy 1-fokú csúcs, aminek van 5-fokú szomszédja, a másik gráfban meg nincs, akkor se lehetnek izomorfak. Meg ha az egyikben vannak 3-fokúak, amiknek 1- és 5-fokú szomszédaik is vannak, a másikban meg nincsenek, az is baj. Szóval a csúcsoknak ez a felosztása nem egyszerűen egy felosztás, hanem vannak rajta gazdagabb, gráfszerű struktúrák is, és ezeknek is izomorfnak kell lenniük.
Vagy pld hogy páros-e a gráf vagy sem, az is egy ilyen könnyen megtalálható egyszerűbb struktúra.
Az algoritmus divide-and-conquer típusú, azaz visszavezeti a problémát sok hasonló kisebb részproblémára. Pld kábé, hogy ha a fenti fokszám-felosztás-struktúrák megegyeznek, az összes lehetséges gráfokkal rajtuk, és a két felosztásban a darabok belülről is ugyanúgy néznek ki, akkor a két eredeti gráf is izomorf, különben meg nem.
Pld a fentiből talán már lehet érezni, hogy ha megoldod a gráfizomorfizmus problémát reguláris gráfokra (ahol minden csúcsnak ugyanannyi szomszédja van), akkor megoldottad a teljes problémát is.
Na most, ilyen egyszerűbb nemtriviális struktúrát kellene találni minden gráfban, pld a regulárisokban is. A szept 14-i ötlet egy local-to-global elv. Fölvágjuk a gráfot kisebb darabokra, és megnézzük, ezek a darabok magukban mennyire szimmetrikusak. Vagy tipikusan egyáltalán nem azok, vagy eléggé azok, és attól függően, hogy melyik eset áll fenn, az egész gráfra rá tudunk kényszeríteni egy ilyen vagy olyan nemtriviális struktúrát. Hogy ezt a globális kiterjesztést meg lehessen tenni, az egy csoportelméleti lemmán múlik, aminek a Babai féle első bizonyítása használja a véges egyszerű csoportok klasszifikációját, de ma már úgy tűnik, hogy ezt ki lehet kerülni.
Ja, és ez a rákényszerítés nem működik mindig, de szerencsére kiderül (sokoldalnyi esetszétválasztás-sorozat után), hogy csak olyankor nem működik, ha a gráfunk egy nagyon spéci módon néz ki (Johnson gráfok), amikben egy teljesen másfajta módon lehet egyszerűbb struktúrát találni.
A struktúrák, amiket találunk, azok sajnos nem egészen gráfok, hanem hipergráfok, viszont szerencsére elég speciálisak, block designok, ezekről pedig sok mindent lehet tudni, ezeket is használja Babai, aminek a segítségével vissza lehet őket gráfosítani.
Első ránézésre kábé ennyi. Egészen nagy matematikusok, Terry Tao és Tim Gowers azon fantáziáltak egy blogon, hogy egy kicsit hasonlít az egész bizonyítás a Szemerédi Regularitás Lemmára, miszerint MINDEN gráf közelíthető egy globális véges struktúrával plusz lokális véletlennel. (Csak minél pontosabban akarunk közelíteni, annál nagyobb és bonyolultabb az a véges globális struktúra.) De most itt sokkal rigidebb struktúrákkal közelítjük a gráfot, sokkal pontosabban, sokkal kisebb lépésekben, sokkal bonyolultabb felbontást kapva, amitől az egész dolog, analízis helyett, mert a Szemerédi Lemma az az, sokkal inkább csoportelmélet lesz.
@Mister Gumpy: koszonom. ha hasznal veges egyszeru csoportok osztalyozasat, akkor azert nem elemi a dolog. be tudnad linkelni a Tao-Gowers-es fantazialast?
@wooddog: A konkrét csoportelmélet teljesen elsőéves anyag, már ha föltesszük a véges egyszerű csoportok klasszifikációjának azon következményét, hogy tetszőleges véges egyszerű csoport külső automorfizmus csoportja feloldható.
A csoportelméleti lemmáját akár ki is mondhatom: egy tetszőleges permutációcsoportban n elemen, ha van egy f szürjektív homomorfizmusunk az Alt(k) k elemű alternáló csoportba, ahol k > 2+log_2(n), és ha vesszük azon elem-stabilizátorok metszetét, amiknek az f melletti képe az egész Alt(k), akkor a metszet is az egész Alt(k).
Ez egy amolyan local-to-global dolog. Az f a kisebb permutációcsoportba az a már megtalált egyszerűbb részstruktúra, amit tovább akarunk bontani.
@wooddog: Sajnos nem találom. Csak a Babai mondta, eléggé röhögve, miszerint szerintük minden matek ezt az elvet követi, és mivel az ő bizonyítása is matek, hát, ráhúzták.
@Mister Gumpy: en se talalom. lehet hogy csak varosi legenda. de hiheto …
@ingyenebed:
„a számok az ember által kitalált fogalmak a mennyiségek tudatosítására.
tehát a „kettő” azóta létezik, mióta az ember megalkotta ezt a fogalmat.”
Hát, nem akartam teljesen hülyének látszani, ezért nem irtam erről, de ezt a témát én ad absurdum vittem, és arra a következtetésre jutottam, hogy a számok egyáltalán nem léteznek. Senki sem látott még pl. „kettő”-t, vagy „öt”-öt. (A mennyiségre gondolok) :)) (A régi görögök szórakozása volt sok szabadidejük lévén hogy minden hülyeséget kitaláltak, és ezért évszázadokkal/ezredekkel később nagy filozófusoknak tekintették őket:)
Ezek alapján a matematika egy vallás, amely azon a hiten alapszik, hogy a számok/mennyiségek léteznek, holott még senki sem látta őket – akárcsak Istent. Mégpedig erősen térítő jellegű vallás, mivel ahol iskolák léteznek – márpedig erős tendencia, hogy a világ minden szegletében legyenek iskolák – ott van matematika. És akkor még jönnek ezzel a marhasággal, hogy tudjukkik világösszeesküvése! Most már tudjuk, kik a tudjukkik! 🙂
„a világegyetemnek nincs tudata amivel a saját mennyiségeit értelmezhetné, így nincs értelme annak a kérdésnek, hogy létezett-e a „kettő” az ősrobbanás előtt.”
Viszont ha a „kettő” stb ember alkotta fogalom, akkor kérdés, mi van a mennyiségekkel.(Én a korábbi kommentben erre értettem a „kettő”-t) A mennyiségek léteztek, hiszen az ember előtt sem volt mindegy, hogy egy vagy 2 velociraptor szembesült egy T-rex-szel. Dacára annak, hogy nem ismerték a számosságot. És hát a fény sebessége is volt valamennyi. Annyi, amennyi. Ha a mennyiségek léteztek , akkor jön a kérdés, mi volt az ősrobbanás előtt. Akkor is annyi volt-e a Pí mint ma. Volt-e egyáltalán Pí? :)) Tekintettel arra, hogy semmi nem volt, ami több volt, mint nulla/semmi. Akkor is érvényes volt a Pitagorasz-tétel? Megannyi égető kéréds 🙂
(Tudja valaki, hogy a helyesírás-ellenőrző miért akarja 1 m-mel irni a „komment”-et? )
@DarthVader:
„Ezek alapján a matematika egy vallás, amely azon a hiten alapszik, hogy a számok/mennyiségek léteznek, holott még senki sem látta őket – akárcsak Istent.”
Szigorúan véve a „valami létezik” az egyetlen tagadhatatlan állítás (illetve az, hogy ez egy tagadhatatlan állítás 🙂 )
Minden más tapasztalat és mint ilyen esetleges. Csak ez cseppet sem érdekel bennünket, mert még a tudományos bizonyosság sem igényli a tagadhatatlanságnak ezt az abszolút szintjét.
Az eléggé valószínű már bőven jó :-).
A fideszesek köztudottan hülyék a matekhoz. Nemcsak a gráfelmélethez, a 4 alapművelethez is. Ez a hír ha elérte volna az ingerküszöbüket, akkor már bevették volna a fide…, izé kormánykampányba. De a fizikai teljesítményeken kívül más nem éri el az ingerküszöbüket. Mert az megfogható.
Továbbgondolva, pár 10 év múlva ha így folynak itt a dolgok, lesz-e majd hasonló magyar vonatkozású teljesítmény? A jövő Babai Lászlói egyáltalán bejutnak-e valamilyen műszaki felsőoktatási intézménybe? Lesz-e egyáltalán műszaki felsőoktatás a testnevelésin kívül?
@jan: megvan a varázsa azoknak a vicceknek, amit csak egy marék ember ért rajtad kívül
@DarthVader:
„_Az univerzumban kb 2 db önmagától létező entitás van, „Isten” és a „szám” – bár az elsőben nem vagyok teljesen biztos. Viszont felvetődik, hogy az ősrobbanás/teremtés előtt létezett-e a szám mint entitás. _”
Oh, hogyne! Volt a 0, az 1 és az Isten. A többi már ismert. [:)]
A ’80-as évek végén a BME Mérnöktovábbképző Intézete tartott matematikai kurzusokat amerikai egyetemisták részére, hosszabb-rövidebb terminusokban (jó kis deviza-bevételi lehetőség volt az egyetemnek).
Fantasztikus társaságot szedtek össze előadónak, páran már akkor is ismertek voltak. Lovász László, Rózsa Pál, meg hasonlók tartottak kurzusokat emlékeim szerint, azóta időnként felkapom a fejem, mikor egyik-másik a címlapokra kerül :). Ja és persze Babai is ott volt!
@DarthVader: „Viszont felvetődik, hogy az ősrobbanás/teremtés előtt létezett-e a szám mint entitás. „
Emlékeim szerint mintha az idő is az ősrobbanással jött volna létre, akkor meg nem a számfogalom nem létezett az ősrobbanás előtt, hanem nem volt olyan, hogy ősrobbanás előtt. 🙂
@gingko: en.wikipedia.org/wiki/Budapest_Semesters_in_Mathematics
erről lehetett szó. ez is egy komoly sikertörténet.
@jotunder:
Azt írják, hogy (talán) nem lesz olyan nagy gyakorlati haszna a matematikában.
Én persze kíváncsi lennék arra, hogy egy -megfelelő szintű matematikai tudással rendelkező kvantumfizikus is így gondolná-e éppen.
@jaegtoer: A matematikán BELÜLI gyakorlati haszon kissé oximoron szagú, és pláne nem világos, hogy egy kvantumfizikus mit tudhat erről. Mindenesetre, első ránézésre azért nincs túl nagy haszna az elméleti matematikai jelentőségén kívül, mert már eddig is voltak a gyakorlatban nagyon jól teljesítő algoritmusok, amik lényegében tetszőleges, a világon eddig előkerült két konkrét gráfról hamar eldöntötték, izomorfak-e.
Kicsit olyan ez, mint a kérdés, hogy mi a hasznosabb, egy 10^3000 n idő alatt futó algoritmus, szóval lineáris, csak kicsit nagy a konstans faktor, avagy egy n^7 idő alatt futó? Az elméleti jelentősége az elsőnek a nagyobb, a gyakorlati jelentősége az utóbbinak, hiszen a világegyetemben előforduló tetszőleges példára az utóbbi fog sokkal jobban teljesíteni, és érdekelnek-e minket a világegyetemnél sokkal nagyobb példák?
Vagy pld én dolgoztam egy statisztikus fizikai modellen a négyzetrácson, ahol egy nagyon természetes kérdésre a válasz az n*n-es dobozban az, hogy egy f(n) kritikus sűrűség az lényegében Pi/18 / log(n). Csak éppen fizikusok korábban szimulálták ezt, és nekik kábé kétszerakkora konstans szorzó jött ki. És bizony, amíg n kisebb, mint 10^3000, addig az ő formulájuk sokkal jobban közelíti az igazságot. Akkor most kinek van igaza?
Persze a matematikusokat részben pont az a hit élteti, és konkrétan pld ezért kapnak a társadalomtól fizetést, hogy a pontos elméleti megértés a világ lényegi működésére ad valódi magyarázatot, és így hosszú távon sokkal mélyebb, hasznosabb, mint a fizikusok vagy egyéb természettudósok által összegányolt féligmegértett felületes „megoldás”.
@Mister Gumpy: Csak ugye előre nem lehet tudni, hogy miknek a mély megértése lesz a tényleges világ szempontjából érdekes, ezért a matematikusok által kitalált összes elméleti hülyeséget finanszírozni kell. Szerencsére nem túl drága.
@jotunder: Igen, ez volt az. Jöttek még mezei egyetemisták nyári kurzusokra egy new yorki egyetemről (na ők elég egyszerűek voltak), meg jöttek orvostanhallgatók hosszabb időre a SOTE-ra. Prímán szervezett dolog volt, win-win alapon. Nekik ez gombokért volt, az egyetem meg pénzt és további kapcsolatokat szerzett.
@gingko: az utobbi evek egyik legnagyobb matematikai erdemenye a kadison-singer sejtes megoldasa volt. az egyik szerzo a budapest szemeszterre jart. en tiz evig tanitottam egy kurzust.
@jotunder: Kicsi falu ez a Pest, szokták mondani… J
(Én azóta nem forgok matematikusok társaságában, csak messziről csodálom őket, mint az egzotikus ragadozókat. Közelről viszont rendes, jófej társaság volt :P)
people.cs.uchicago.edu/~laci/update.html
@dvhr: újra megvan a kvázipolinomialitás.
helfgott, aki megtalalta az elso hibat, ugy gondolja, hogy most mar jo a bizonyitas.