Kicsit irigylem a fizikusokat. Az emberek ugyan nem tudják mi a kvantummechanika és a relativitáselmélet, de van valamiféle homályos elképzelésük arról, hogy létezik kvantummechanika és relativitáselmélet. És azt is tudják, hogy nagyon komoly dologról van szó. A fizika egy nagyon jó történet, van benne Einstein, Hawking, Penrose, fekete lyukak, kvarkok meg vicces dolgok. A modern matematikáról lényegében semmit sem tudnak az emberek. A matematikából valahogy a lényeg hiányzik, a Nagy Történet, ami megérinti az embereket. A modern matematikáról gyakorlatilag senki nem tud semmit a matematikusokon kivül. Persze a matematikusok sem nagyon értik egymást, nekünk magunknak sincs saját kvantummechanikánk és relativitáselméletünk, titkos tudományunk.
Szoval minden programhoz megadhato egy konstans lepesszam, amig egyaltalan a szimulacioja beindul a szimulatoron, es minden programhoz megadhato egy konstans (1/2^n ha a program sorszama n), ami azt adja meg, hogy ha mar beindult a program szimulacioja, akkor a szimulacio az eredeti program hanyadresze sebesseggel fut.
Azert ez valljuk be nem tul praktikus, de van egy meg ennel is kevesbe praktikus eszrevetelem:
Ha az n.-dik program kesz, akkor a primfaktorizaciok helyesseget ellenorzo reszt a szimulator gondolom az n. program idoszeleteben vegzi, azok szimulalat futasidejet megnovelendo.
Namost, ha netan letezne olyan primfaktorizalo algoritmus, amely ordo (aszimptotikusan?) gyorsabb, mint a faktorizacio ellenorzo algoritmus (szorzas), akkor arra az esetre ez a modszer nem eleg jo.
Tenyleg, ismert a szorzas minimalis idokomplexitasa? Milyen ismert minimalis idokomplexitast ismerunk a primfaktorizaciora? Bizonyitva van, hogy a masodik nagyobbegyenlo mint az elso?
(P?=NP-re: Ha jol ertem ez a modszer azt mondja, hogy ha barki egzisztencialis bizonyitast ad P=NP-re, azonnal adott a konstruktiv bizonyitas is ezen modszer segitsegevel.)
És miként oldható meg Turing-gépen, hogy az n-edik algoritmusra a futasido 1/2^n-ed resze jusson? Biztos úgy, hogy az időt felosztjuk egyre nagyobb 2-hatvány hosszú részekre és ezeket a részintervallumokat osztjuk ki az algoritmusok között. Jól mondom?
Egyrészt tényleg szarkasztikus volt a megjegyzésem, másrészt tényleg úgy gondolom, hogy sok ma már ismert matematikának később fog megmutatkozni a gyakorlati haszna. De ehhez az is kell, hogy a matematika egyre nagyobb része jusson el az emberekhez, a potenciális alkalmazókhoz. Legyenek bárki által hozzáférhető ingyenes (értsd: államilag vagy szuperállamilag támogatott) hagyományos és digitális könyvtárak, matematikusok, akik életben tartják, továbbadják és továbbfejlesztik a tudást stb.
Egyebkent en nem igazan hiszem, hogy a matematika tul fejlett lenne a gyakorlati elethez kepest. Nagyon sok olyan nehez matematikai kerdes van, amit pont a gyakorlat motival. Nagyon ugy tunik, hogy a fizika gyakran "tul jar" fondorlatossagban a tiszta matematikan, es mindenfele bamulatbaejto dologra vezeti a matematikusokat.
Masreszt a szamitastechnika fejlodese is hatalmas lenduletet fog ad egyes matematikateruletek "ujraeledesere". Peldaul a szamitogepes rendszerek es aramkorok tervezese tobb matematikai ag szinteziset motivalta: egyre inkabb szukseg van a komplex rendszerek viselkedesenek formalis ellenorzesere automatizalt modon. Ehhez masszivan hasznal a formalis logikat, modellelmeletet, algoritmuselmeletet, grafelmletetet es algebrat. Ennek a teruletnek a robbanasszeru fejlodese nagyon praktikus kihatassal lesz a mindennapi eletre. Szerintem par evtizeden belul minden valamirevalo halozati alkalmazas, valamint a protokollok formalisan modszerekkel lesznek ellenorizve, ami peldaul a szamitogepes virusok eltunesehez vezethet. Mindez nem lehetseges megfelelo matematikai alapok es modszerek nelkul.
Az algoritmus generalja sorban az osszes algoritmust, es parallel futtatja azokat ugy, hogy az n-edik algoritmusra a futasido 1/2^n-ed resze jut. Ha valamelyik algoritmus egy outputtal megall, akkor leellenorzi, hogy ez az input ervenyes faktorizacioja e. Ha igen, akkor kiadja a faktorokat es megall.
Töredelmesen bevallom, hogy nulla a tudásom a C-ben. Leragadtam a Pascal-nal, azt is csak kétévente egyszer használom, ha valami szerény számítási feladat adódik. Mert a Mathematica-t és a Maple-t is lusta voltam mindidáig megtanulni.
Peldaul nagyon konnyu megadni egy aszimptotikusan optimalis algoritmust a primfaktorizalasra (ez azt jelenti, hogy minden mas algoritmus olyan hogyha a futasidejet osszahasonlitod evvel, akkor csak egy konstans faktorral lehet gyorsabb)
Egy matematikusnak is kell(ene) évi néhány ezer dollár arra, hogy könyveket vásároljon, konferenciákra utazzon, vendégeket fogadjon, vagy akár könyvet írjon. A tudomány szervezéséhez pedig sokkal-sokkal több pénz kell. Szükség van matematikai intézetekre, könyvtárakra, kutatói pénzekre az egyetemeken stb. De szükség van színvonalas oktatásra is, nem csak egyetemi, hanem minden szinten. A pénzt politikusok adják, a politikusok pedig nagyjából úgy közelítik meg a matematikát, mint az emberek általában. Ha egy nem matematikusnak beszélek a munkámról, az első kérdése az, hogy "és ez mire jó". Ugyanezt kérdezi a politikus is. A probléma, amiről Jó Tündér beszél, valóságos és egyre sürgetőbb. A többi tudományág bizonyára korábban megtanulta, hogy "el kell adnia magát", mert azok támogatás nélkül életképtelenek. A matematika életképes támogatás nélkül is, de igencsak beszűkül az élettere.
Jól esett ez a megjegyzés. Itt a távolban bevezető számelméletet próbálok a nebulók fejébe verni, és a def. tétel. biz. standard formát választottam. És persze gondosan válogatom, melyik def. tétel biz. hangozzék el. A saját ízlésem szerint túl formálisra is sikerülnek az előadások, de ugyanakkor az óra egyben bevezetés a matematikába is, ami önmagában indokolja ezt a formát. Ha már valaki érti, mit jelent bizonyítani, kedvére engedhet a formalizmusból. Az én diákjaim a jelek szerint még nagyon nem értik. Egyébként döbbenetes, hogy a számelméletet nemigen lehet jobban felépíteni, mint ahogy Euklidész tette az Elemekben. Ez ad erőt nekünk.
Megprobalnam meg visszajara is forditani a kerdest: nem lenne ertelme a P!=NP helyett a (gyengebb) P'!=NP allitassal probalkozni (ahol P' a bizonyithatoan polinomialis algoritmusok osztalyat jeloli.
"Nem celja a matematikanak mindenaron gyakorlati eredmenyek azonnali elerese szerintem, sokszor az is eleg, ha szep. A kulturalis erteke felbecsulhetetlen. Es a gondolkodas-fejleszto hatasa meg fontosabb." -- Ezzel nem vitatkozom, ketsegtelenul igy van. Am megvan a gyakorlati haszna is boven, es vannak muveszeti jellegu vonasai is. Igy van jol. :-)
Bizony raadasul nem art, ha ilyesmivel az ember hamar vegez, egyik kemikus sem annyira turelmes, hogy a matematikus megoldja 10 ev alatt. Mert adott lehet egy modszer, de ha az lassu, akkor lenyegeben nem modszer a problema megoldasara.
Egy hasonló gondolatot fogalmaz meg Papadimitriou. (p. 402).
"Íme egy nyugtalanító lehetőség: tfh a P=NP állítást egy nagyon nem konstruktív bizonyítással sikerül belátni, azaz bár a bizonyításból következik, hogy a SAT problémára létezik polinom idejű algoritmus, arról semmit sem tudunk, hogyan lehetne ezt leírni, futtatható programot készíteni belőle."
Egy érdekes feladat is van hozzá.
Egy szerinte tipikus egz. biz.: 11.6. tétel: BPP-beli nyelv eldönthető polinomiális hálózatokkal (p. 309).
Ez miert nehezebb, mint egy 2 dimenzios fuggveny eseten?
A sokdimenzios fuggvenyek optimalizalasa lenyegesen kulonbozik a 2/3-dimenziosoketol. Altalban mas modszereket igenyelnek. A gradiens eljaras onmagaban csak nagyon ritkan alkalmazhato hatekonyan. Altalaban mas trukkokre is szukseg van. A matematikai optimizacio temakore, ami (tobbek kozott) evvel foglalkozik, eleg modern aga a matematikanak, mert csak az otvenes evek ota letezik.
Bizony csodakat tesz egy kicsiny algoritmus, ami egy eddig exponencialis idoben megoldhato feladatot polinomialissa tesz, ez mondjuk 5-6000 tenyezonel azt jelenti, hogy egy logisztikai problemat szuperszamitogeppel 50000 evig szamolnak, vagy 3 napig. ;-)
En amikor egy feladatot exponencialis helyett polinom idoben oldok meg, azt altalaban se nem tekintem modern mtematikai eredmenynek, se nem hasznalok modern matematikai eredmenyeket hozza.:)
Biztos vannak olyan esetek, ahol konkretan felhasznalnak valamilyen modern matematikai apparatust, de szerintem ritka mint a feher hollo.
Ez igy igaz, am hatekonyan kell, hogy kezelje az adatokat a gep, es ehhez kell a modern matematika.
Az NVidia mernokei vagy John Carmack hasznal modern matematikat? Meg tudod nevezni, hogy konkretan milyen matematikai eredmenyt hasznalnak?
Csak egy gyakorlati pelda. Egy kemikus srac azt mondta, kellene olyan algoritmus ami tudna kezelni egy nagyon sok dimenzios dolgot, tulajdonkeppen egy 50000 vagy meg nagyobb dimenzion ertelmezett fuggvenyen szeretne minimum es maximum pontokat keresni.
Ez miert nehezebb, mint egy 2 dimenzios fuggveny eseten? Megvannak a modszerek a maximumkeresesre. (Gradiens modszerek, genetikus algoritmusok) Legtobbszor ez sem tiszta matematika, mert jobb hijan heurisztikus modszereket alkalmaznak. (ami meg matek benne, az meg szerintem eleg regi) )
De azt hiszem felreertettuk egymast... A matematika nem egyedul talalja ki a szamitogepek cuccait, a logisztikat, a banantermesztes es szallitas optimalizalasat, genterkepezes algoritmusat, es effeleket, hanem szimbiozisban a tobbi tudomanyban nelkulozhetetlen segitseget nyujt. A szimbiozis kolcsonosseget is jelent, a matematika abbol profital, hogy kapja a problemakat, anomaliakat es kibogozza azokat. Azt hiszem igy korrekt es teljes az, ahogy latom.
A matematikanak a technikai fejlodesre van hatasa, de szerintem ez attetelesebb, mint az ember elsore gondolna. A szamitastechnika kozvetlenul legtobbszor csak regi matekot hasznal, vagy az ujbol csak azt a trivialitast, aminek a vizsgalata szamitastechnika nelkul eszebe sem jutott volna az embereknek.
A metekot egy kicsit a muveszethez is hasonlitanam. Nem celja a matematikanak mindenaron gyakorlati eredmenyek azonnali elerese szerintem, sokszor az is eleg, ha szep. A kulturalis erteke felbecsulhetetlen. Es a gondolkodas-fejleszto hatasa meg fontosabb.
a biologusok milyen matekot hasznalnak? hat egyreszt ugy szamolnak, hogy 1, 2, sok, szaz, ezer. igy van, hogy a szazlabunak 17 par laba van, az ezerlabunak pedig 27. es ugy integralnak, hogy lerajzoljak papirra, kivagjak es lemerik merlegen. minek ehhez szamitogep.
Ez utobbi eleg erdekes, tudnal valami linket hozza?
Ez a sajat otletem volt, de par eve megkerdeztem a batyamat, aki ketszeres Goedel-dijas bonyolultsagelmelesz, es nem tartotta hulyesegnek.
De akkor ha esetleg P=NP akkor ez nem "derulhet ki" olyan egyszeruen, nem??? Es megsem csodalkoznal..? :)
Az is kiderulhet persze, hogy a P=NP nem eldontheto kerdes a ZFC kereten belul, de csoppet sem lenne furcsa, ha valaki adna egzisztenciabizonyitast egy konkret algoritmus megadasa nelkul. Ez teljes szokvanyos a matematikaban.
Peldaul nagyon konnyu megadni egy aszimptotikusan optimalis algoritmust a primfaktorizalasra (ez azt jelenti, hogy minden mas algoritmus olyan hogyha a futasidejet osszahasonlitod evvel, akkor csak egy konstans faktorral lehet gyorsabb), anelkul, hogy akarmi mas konkretumot tudnal meg ebbol a futasidejet illetoen.
" Azt mar irtam korabban is, hogy egy csoppet sem csodalkoznek (sot valoszinunek tartom), ha kiderulne, hogy P=NP, de bizonyithato hogy nincs olyan NP teljes algoritmus ami bizonyithatoan polinomialis."
Ez utobbi eleg erdekes, tudnal valami linket hozza? De akkor ha esetleg P=NP akkor ez nem "derulhet ki" olyan egyszeruen, nem??? Es megsem csodalkoznal..? :)
Sajnos teljesen igazad van, az átlagemberek sohasem fogják megfelelően értékelni a matematikát. A legtöbb embernek fogalma sincs, hogy ki volt Gauss vagy Euler, és el sem tudják képzelni, milyen szellemi teljesítmény egy nagy matematikai eredmény elérése. A Fields-éremről valószínűleg az emberiség több mint 99%-a semmit sem tud. Szánalmasnak tartom, hogy a népszerű kvízműsorokban több operakérdés hangzik el, mint matematikai. Mindezek ellenére véleményem szerint (szerencsére) sokszor olvashatunk lenyűgöző matematikai eredményekről.
Kicsit csodalkoztam, hogy ugyan kisebbseg, de nem elenyeszo kisebbseg szavazott arra, hogy P = NP. (Nekem is eszembe jutott mar ez, es en azt hittem, hogy ez eretnek gondolat, de ugy latszik megsem annyira.)
Azt mar irtam korabban is, hogy egy csoppet sem csodalkoznek (sot valoszinunek tartom), ha kiderulne, hogy P=NP, de bizonyithato hogy nincs olyan NP teljes algoritmus ami bizonyithatoan polinomialis. (Pl. egy igazi "eros intelligencia", ami kepes uj algoritmusokat kifejleszteni es futtatni ilyen lehet).
Ez egyfajta szempontbol frusztralo lenne, mert sohase tudnank megmondani, hogy egy algoritmus eleg eros e, masreszt viszont megis meghuzna egy hatarvonalat egy ujfajta P (P') es NP kozott: P' azon algoritmusok halmaza, amik (a ZF-ben) bizonyithatoan polinomialisak.
