Názory k článku Faktorizace na DNA počítači

Uloha c. 1:
Spocitejte, kolik vazi molekula DNA zobrazujici druhou mocninu prvocisla 2^859433-1.

Reseni pro netrpelive: Hmotnost molekuly o nekolik set tisic radu prekroci hmotnost vesmiru.

Pouziti unarni reprezentace pro velka cisla je ve vsi ucte pitomost.
Uz vubec neuvazuji, kolik reakci by se muselo provest, aby se takhle krasne molekuly spojily. To by trvalo dalsich mnoho miliard let (trochu velka cena za to abychom zjistili, ze si sef NSA prisne tajne poslal pro pizzu).
Ano vim, takhle velka cisla se v praxi nepouzivaji, ale krasne to demonstruje nesmyslnost metody. Tim nerikam, ze je uplne nepouzitelna a nerealizovatelna, jen velmi rychle narazite na prakticka omezeni. Neco jako pocitani lidi na Zemi na prstech jedne ruky - pokud bude lidi dost malo, bude to fungovat.

Jak se technicky realizuje to "nechame postupne reagovat s deliteli"? To je pro kazdeho delitele jedna zkumavka (a tedy celkem int(sqr(N)) zkumavek? To uz je lepsi to nechat spocitat na pocitaci. Pokud by se to cele snad nechavalo reagovat dohromady, tak tim nezjistime faktorizaci ale rozklad na soucet nekolika mensich cisel.

-Yenya

No jo. Ono je to jeste vetsi hloupost nez jsem si myslel. Zjisti to jen delitelnost dvou cisel.

Ano, máte pravdu:
- nemůžete to dělat přesně takhle, tj. na takhle dlouhé jediné molekule (už i proto, že je dost obtížné připravit molekulu třeba o přesně 8 milionech nukleotidů). Budete to muset nějak "rozdělit". To "rozdělení" bude muset platit už i pro testování větších dělitelů.
- samozřejmě, že dělat to postupně s každým číslem v oddělených zkumavkách hodně zdržuje a postrádá smysl
- předností DNA počítačů je ten paralelismus, tj. musíte samozřejmě přidat všechny dělitele najednou. A to tak specificky, aby se vedle nukleotidu reprezentujícího 31 připojoval zase jen nukleotid reprezentující číslo 31. Ty nukleotidy musí mít tedy nějaké specifické vlastnosti.
- snažil jsem se nezatěžovat článek těmito biochemickými podrobnostmi, protože popravdě nevím, zda by to pak čtenáře zajímalo. V případě zájmu se takový článek pokusím vytvořit, ale předem upozorňuju, že to bude "ano, ale..." "jde to zrealizovat takhle, jenže narazíte na tohle..." apod. V původním textu se třeba vůbec nezmiňuje možnost, že to dělení můžete také reprezentovat přes stříhání molekul DNA enzymy.

Také jsem trošku chtěl ťuknout do ostatních, aby vymysleli algoritmus vlastní, protože téma DNA počítačů mě velice zajímá. Chtěl jsme prostě těmhle compům udělat trochu reklamy :-)

Ano, myslim ze by nas zajimaly vsechny ty biochemicke podrobnosti. Pokud je nezname, nevime jake operace se s tim daji delat a tezko budeme vymyslet nejaky algoritumus...
Ted me napadlo neco, co by se mozna dalo pouzit. Jde jenom ale o obecny princip:
-do skumavky vlozim cisla od 2 do cisla, ktere faktorizuju (kazde cislo ne jednou, ale hodne krat :-)
-probiha nasobeni nahodne vybranych dvou cisel, vysledek je specielne oznacen jako "neprvocislo" (s tim, ze si nese informaci o cinitelech)
-zaroven probiha porovnavani cisel a "neprvocisel", vsechny cisla, ktere se sparuji s "neprvocislem" rozbiju nahodne na vice mensich cisel
Po nejake dobe tak ziskam skumavku plnou vysokych neprvocisel. Pak jenom zjistim, jestli je faktorizovane cislo mezi nimi. Pokud je, tak jsem vyhral, a podivam se, jak jsem k nemu prisel...

Problem s DNA pocitacmi je ten, ze ani ten paralelizmus nestaci na NP-uplne problemy. Sice mozme robit plno reakcii - operacii naraz (odhadom 10^12), ale algoritmus s casovou zlozitostou O(N!) to nebude zvladat riesit uz pre pomerne male N... co si pomozeme je mozno konstanta... casova zlozitost zostane stale exponencialna. Dalsi problem je s materialom... pri NP-uplnych problemoch uz pre male N (okolo 100) by sme potrebovali viac hmoty ako je vo vesmire... Dalej ohladom kvantovych pocitacov, tie sice vedia faktorizovat v polynomialnom case (od velkosti vstupu, cize logaritmu daneho cisla), ale NP-uplne ulohy riesit nevedia - faktorizaciu sa nepodarilo previest na ziaden znamy NP-uplny problem a veri sa tomu, ze sa to ani neda. (to by podla mna znamenalo aj to, ze existuje nejaka mnozina, ktora ma vacsiu mohutnost ako alef0 (mohutnost N) a mensiu ako 2^(alef 0) (mohutnost R).

S prominutim, pan Oravce, jak jste prisel na takovy nesmysl? Ujistuju vas, ze at uz je to s NP-uplnosti faktorizace jakkoli, muzete si k tomu konzistentne primyslet jak CH, tak i jeji negaci.

Má to ještě jeden háček. Pokud totiž odfiltrujete ten balast, kde jednotlivé řetězce "přesahují", zbude vám jen spousta řetězců typu
AAAAAA
------
TTTTTT
a jak vy pak odlišíte, jestli to je např 1+5, nebo 3 + 3? Neboli jak nakonec zjistíte ty dvě prvočísla?

...uz nekdo zkousel misto skutecnych molekul pouzit nejakeho jineho modelu? Je zrejme, ze molekul i v hodne male zkumavce bez problemu ziskam miliardy, ale ta manipulace je preci jen ponekud neexaktni:)

Co takle vyuzit Internetu, pridelit kazdemu Pocitaci, ktery by do toho sel jednu, (pripadne vsecky 4 z nichz by jednu nahodne vybral) baze a nechat je nahodne bombardovat obdobou pingu nejaky server. Ten by mel ulozene ono prvocislo a jak by nahodne chodily pingy od klientu, tak by je prikladal k jednomu, nebo vice paralelnim obrazum toho prvocisla.

Jestli to chapu dobre, tak u DNA computingu se jedna o pravdepodobnosti, tj nahodny system. Pokud by se takovychto nodu udelalo vic, tak by to mohlo byt na bazi SETI@Home ... pricemz by to krome konektivity nestalo temer nic.

Predpokladam, ze to nekdo briskne vyvrati. Predesilam, ze o problemu nevim temer nic, cili prosim necinte to prilis odbornou hantyrkou:)

Jako vtip by to bylo dobre, obavam se ale ze to bylo mysleno vazne, ne ?

Proč? S dostatečně velkým počtem počítačů, mezi kterými se vhodně nadefinují vztahy by mělo jít nasimulovat cokoli. Jistý je jen ten fakt, že počítačů které by byly k dispozici by byl vždy velmi omezený počet.

Jen by to postrádalo tu masivní paralelnost v rámci jednoho stroje, ale to je otázka designu:)

A pokud bychom připustili větší zatížení účastníků, tak po vzoru neuronových sítí, by šly simulovat i řetězce ADCT atd. Samozřejmě to je teorie:) Lidem, co tvrdili, že Země je kulatá, se taky nejdřív smali:)

No, ono to alespoň trochu exaktní být, musí protože na tom stojí i přenos informace v nás samých :-). Uvádí se, že špatné spárování nastane tak u 1 báze z miliardy (v živých organismech jsou pak další kontrolní mechanismy, něco na způsob kontrolních součtů - nakonec regulace stejně selže a my zemřeme - pardon, to je samozřejmě strašně zjednodušující tvrzení).
V DNA počítači můžete luštit příklady, u nichž vás zajímá alespoň nějaké řešení - tj. nakonec vám někam připlave molekula, vy ji přečtete a zjistíte, že to vyhovuje podmínkám (nebo také ne, i to se může stát). Vezmete další molekulu, která se tváří jako "vyhovující", pak ještě další. Je jich tam strašně moc, tj. brzy skončíte. Nebudete si nikdy jistí, zda jste přečetli skutečně všecha řešení.
Možné využití DNA počítačů je tam, kde zase záleží jen na rámcové přesnosti - tj. například jako nějaké strojky regulující procesy probíhající v buňkách a tak...

Ještě k dotazům o aprílu:
Článek byl míněn zcela vážně, i když šlo o myšlenkový experiment. Leonard Adleman s tím začal experimentovat v polovině 90. let. Letos byl na CeBITu k vidění i DNA počítač již částečně programovatelný, respektive s algoritmem "vypáleným" :-) do destičky, bez nutnosti ručně přelévat zkumavky. Olympus by to chtěl komerčně spustit možná již v příštím roce (pronajímat to podobně jako kdysi sálové počítače), bádají na tom v Princetonu, Frauhoferově ústavu, v Izraeli atd.
Samozřejmě se to může ukázat jako úplně slepá ulička nebo vhodné jen pro velmi specifický okruh problémů, ale osobně se mi to zdá být realizovatelnější než častěji zmiňované počítače kvantové...

Neumim posoudit, zda-li se takhle vubec da provadet operace deleni, ale pokud jo, tak tech delitelu (molekul) jsou mozna stovky miliard a kazdy je uplne jiny.

Vyrobit tolik ruznych molekul (priprava na chemicky pokus) by asi bylo dost casove narocne, zrejme mnohem pomalejsi nez provadet vypocet primo na klasickym pocitaci.

Rad by som len poznamenal, ze existuje viacero metod faktorizacie, ktore nie su zalozene na hrubej sile...

obavam se, ze vlozit do zkumavky tolik molekul, jako ma cislo potencialnich delitelu (tzn. odmocnina z n) je neproveditelne a to i v pripade, ze bychom pouzili binarni zpusob zapisu.

v dnesni dobe zajimava cisla, tedy radove 2^2048, maji 2^1024 potencialnich delitelu. i kdyby kazda molekula zabirala 1 atom, tak se to dost tezko do zkumavky vleze. hmm, vlastne i do naseho vesmiru :))

o DNA pocitace jsem se trosku zajimal, nicmene jsem toho rychle nechal. na rozdil od kvantovych pocitacu nenabizeji zadnou "technologii", jak obelstit exponencialu. pokud nejaky problem vyzaduje prozkoumat exp. pocet moznosti, je nutno pouzit exp. pocet molekul a pres to nejede vlak. jak jste sam napsal, nabizeji pouze rychly paralelismus.

kvantove pocitace diky superpozici a entanglementu naopak umeji exponencialne urychlit NEKTERE vypocty (cim vice strukturovane, tim lepe, napr. fourierova transformace pouzita mimo jine pri faktorizaci je velice "pravidelna", takze pro ni to funguje) a kvadraticky LIBOVOLNE hledani v nesetridene databazi (zde se da trivialne dokazat, ze lepe to nejde, pokud nema databaze vnitrni strukturu).

Sice si nedovedu ani DNA ani kvantovy pocitac moc dobre predstavit, ale nedavno jsem cetl, ze na kvantovem lze faktorizaci resit viz napr: http://www.stp-gateway.de/Archiv/archiv450-e.html

Ještě mě včera večer napadlo, že by se teoreticky dala cisla na DNA pocitaci modelovat i v pozicni soustave, nejen pres pocet nukledotidu. priklad: T je oddelovac radu, A vyjadruje pocet.
takze AAATTATT je 30100 (za predpokladu, ze na konec se uz oddelovac nedava a ze mame desitkovou soustavu)

Upřímně řečeno netuším, kde autor zaslechl, že faktorizace se dělá postupným zkoušením možných dělitelů. To tak asi na základní škole, když se má zjistit, že 26=2*13. Normální dítě začně mít problémy už třeba s 217 (není to náhodou prvočíslo? :-].
Vlastní faktorizace se dnes dělá pomocí konstrukce čísla, které modulo n dává čtverec. A to použitím "prosévání" a postupného skládání. Ale to už opouštíme "středoškolskou" matematiku.