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