Kirjaudu

Uutiskirje

Rekisteröidy Sektoriin ja tilaa itsellesi joko aamuisin tai iltaisin ilmestyvä uutiskirje sähköpostiisi.

Lauantai, 16.3.2002

DNA-tietokone ratkaisi monimutkaisen ongelman

DNA-molekyyleihin perustuva tietokone on Kalifornian yliopiston Leonard Adlemanin johtamassa kokeessa ratkaissut monimutkaisen laskennallisen ongelman, jota yksikään ihminen ei käsin laskemalla olisi voinut ratkaista. Kokeessa DNA-tietokone joutui käymään läpi miljoonia eri vaihtoehtoja päästäkseen oikeaan lopputulokseen. Vielä lastenkengissään olevalle DNA-teknologialle onnistunut koe on merkittävä edistysaskel.

Nykyisten tietokoneiden ongelmanratkaisu perustuu jonomaiseen ajatteluun, mutta DNA-tietokoneet kykenevät käsittelemään dataa massiivisen rinnakkaisesti, joka on paljon tehokkaampaa. DNA-tietokoneiden pelätään ennen pitkää kykenevän salausten purkamiseen liiankin tehokkaasti, mutta ainakin toistaiseksi DNA-tietokoneet ovat virheherkkiä ja kykenevät vain tarkasti rajattuun ongelmanratkaisuun.

Lue juttu oma, 16.3.2002 19:15. Lähde: NASA

Muita aiheeseen liittyviä uutisia

Rekisteröidy ja kirjaudu sisään, jos haluat kommentoida.

Kommentit ( 16 uutta / 16 )
pistettä.
Näytä vain kommentit joilla on vähintään
Boing
Anonyymi kommentoija, 17.3.2002 09:33:07		 Pisteet: 0
Kummallista että toitotetaan jatkuvasti että uudet superkoneet ratkaisevat kaikki salaukset. niin varmasti kaikki NYKYISET. mutta mitä luultavimmin näille uusille DNA ja kvanttikoneille kehitetään niiden tekniikkaan perustuvia salausmenetelmiä jolloin palataan taas tietyllä tavalla alkutilanteeseen.
Re: Boing
Anonyymi kommentoija, 17.3.2002 15:31:16		 Pisteet: 0
Kummallista että toitotetaan jatkuvasti että uudet superkoneet ratkaisevat kaikki salaukset. niin varmasti kaikki NYKYISET. mutta mitä luultavimmin näille uusille DNA ja kvanttikoneille kehitetään niiden tekniikkaan perustuvia salausmenetelmiä jolloin palataan taas tietyllä tavalla alkutilanteeseen.
Joo, niin sitten kun kaikilla on DNA:han perustuvat tietokoneet, mutta jos niitä DNA:han perustuvia koneita on vaikkapa vain yksi, ja kaikilla muilla on tämmöiset transistoripohjaiset lelut, niin minkäs teet.
Justus Näin on
Justus, 18.3.2002 11:12:08		 Pisteet: 0
Joo, niin sitten kun kaikilla on DNA:han perustuvat tietokoneet, mutta jos niitä DNA:han perustuvia koneita on vaikkapa vain yksi, ja kaikilla muilla on tämmöiset transistoripohjaiset lelut, niin minkäs teet.
Niin, Jet Propulsion Lab on niin pirun rahapulassa että varmaan myyvätkin sitten ensimmäisen DNA-tietokoneen eniten tarjoavalle, eihän niillä siellä NASA:n kehityslaboratoriossa ole sellaiselle koneelle käyttöä. Johan siellä kuussakin on käyty 60-luvulla ja ne vasta kökköjä olikin ne tietokoneet, ajatteles. :-)
Memes don't exist. Tell your friends.
One-time Pad ja fotonit
Japp, 17.3.2002 13:06:03		 Pisteet: +1
Onhan noita todisteltu että on olemassa täydellisiä salauksia, joita ei voi siis mitenkään murtaa. Ainoa ongelma on että miten saadaan lähettäjän avaimet sille vastaanottajalle. Tähän on kehitetty sitten noita erilaisia menetelmiä, jotka on wräpätty yksisuuntaisten funktioiden avulla niin että niitä on vain hieman vaikeampi murtaa, koneiden laskennallisen rajoittuneisuuden vuoksi.
Mutta mikäli saat sen avaimen jotenki toiselle kaverille, turvalisesti, on näillä tehtyä salausta mahdoton murtaa ( One-time Pad ), kuten myös Charles Bennett tai Stephen Wiesner ovat kokeissaan ja ajatuksissaan havainneet.
------------------------
Do you think thats air your breathing ?
zepi Re: One-time Pad ja fotonit
zepi, 17.3.2002 16:12:23		 Pisteet: +1
Onhan noita todisteltu että on olemassa täydellisiä salauksia, joita ei voi siis mitenkään murtaa. Ainoa ongelma on että miten saadaan lähettäjän avaimet sille vastaanottajalle. Tähän on kehitetty sitten noita erilaisia menetelmiä, jotka on wräpätty yksisuuntaisten funktioiden avulla niin että niitä on vain hieman vaikeampi murtaa, koneiden laskennallisen rajoittuneisuuden vuoksi.
Hmm, vaikea uskoa, että olisi olemassa salaus, jota ei voi murtaa. Sillä jos sen voi purkaa tuolla oikealla avaimella, niin mikä estää arvaamasta tuota oikeaa avainta? Vaikka se avain olisi 32kilobitin kokoinen tai vaikka 16Mbitin, niin silti olisi teoriassa mahdollista osua samaan avaimeen tsägällä.

Matematiikka on kuitenkin kovin monimutkaista ja oma hiukan yliopistotason peruskursseja raapaiseva tietämykseni ei ole täydellistä ;). Ehkä tuollaisen avaimen voi tosiaan rakentaa sellaiseksi, että sitä ei _voi_ arvata. Terve järki ja matikka kun eivät oikein kulje aina käsi kädessä.
Re: One-time Pad ja fotonit
Anonyymi kommentoija, 17.3.2002 21:51:32		 Pisteet: +1
Hmm, vaikea uskoa, että olisi olemassa salaus, jota ei voi murtaa. Sillä jos sen voi purkaa tuolla oikealla avaimella, niin mikä estää arvaamasta tuota oikeaa avainta?
Ideanahan tuossa OTP:ssä on se että avain on yhtä pitkä kuin salattava viesti ja jokaista avainta käytetään vain kerran. Salaukseksi riittä bitittäinen XOR salattavan viestin ja avaimen välillä. Purkaminen suoritetaan samalla tavalla (mieleen saattaa tulla ROT13 ;).

olisi teoriassa mahdollista osua samaan avaimeen tsägällä.
Teoriassa kyllä, mutta tuolloin todennäköisyys on yhtä suuri kuin arvata viestin sisältö sen pituuden perusteella. Ja salatun viestin loppuun voi lisätä ylimääräistä dataa.
JttL Re: One-time Pad ja fotonit
JttL, 18.3.2002 18:42:43		 Pisteet: +1
Hmm, vaikea uskoa, että olisi olemassa salaus, jota ei voi murtaa. Sillä jos sen voi purkaa tuolla oikealla avaimella, niin mikä estää arvaamasta tuota oikeaa avainta? Vaikka se avain olisi 32kilobitin kokoinen tai vaikka 16Mbitin, niin silti olisi teoriassa mahdollista osua samaan avaimeen tsägällä.
Tiettävästi avainta jota ei voi arvata niin on mahdoton keksiä, mutta kun laskee perusmatematiikalla todennäköisyyden sille, että onnistuu arvaamaan 32kb avaimen on (1/2)^32786 = 7,0648 * 10^-9865 voi tältä pohjalta sanoa, että jo 32kb avaimenkin raaka arvaaminen on lähes mahdotonta. 16Mb avaimelle en todennäköisyyttä edes onnistunut laskemaan windowsin laskimen ja TI-86:n ilmoittaessa virheellistä syötettä.

En kyllä tiedä mikä määritellään mahdottomaksi murtaa, mutta teorettiinen mahdollisuus osua oikeisiin avaimiin on aina olemassa. Vaikkakin se on hyvin hyvin epätodennäköistä.
"A stroke of brush doesn't guarantee art from bristles." --Kosh
Re: One-time Pad ja fotonit
Japp, 18.3.2002 19:34:53		 Pisteet: +1
Kuten siis sanottu, teoriassa tuo arvaaminen on mahdollista, mutta et voi tietää onko arvauksesi oikein. Kuvitetellaan että arvaat yhden 10 merkkisen avaimen. Tämän avaimen syötettyäsi purkualgoritmiin saat merkkijonon "oikeinmeni". Kaverisi kuitenkin ehdotaa omaa avainta, jolla oli samalla purkualgoritmillä saanut oikeaksi viestiksi, "väärinpäin". Itseasiassa jonkin ajan kuluttua huomaatte että eri avaimilla saatte myös merkkijonot "eipä_toimi" , "ihmehommaa" ja "mikäsenyon" sekä itseasiassa eri avaimilla, kaikki mahdolliset 10-merkkiset merkkojonojen kombinaatiot. Eli onko pirullinen vihollinen sitten hyökkäämässä "ehkä_kohta" vai onko jo "liianmyöhä".
------------------------
Do you think thats air your breathing ?
JttL Re: One-time Pad ja fotonit
JttL, 19.3.2002 07:46:02		 Pisteet: 0
Jos nyt onnistuin ajattelemaan järkevästi niin tämähän pätee vain mikäli avain on vähintään yhtä pitkä kuin viesti. Sillä mikäli avain on esim vain tuon 10 merkkiä niin purettaessa se toistaa itseään eikä kaikkia mahdollisia viestejä tule käytyä läpi (?). Tietenkin yksittäisiä sanoja tulee muodostumaan, mutta tällaiset viestit voi suoraan karsia viestiin jäävien järjettömien merkkien takia.

Tuo mitä sanoit on kieltämättä totta, mutta tosiaankin vain mikäli avain on tarpeeksi pitkä. Kaipa tuollainen voidaan sitten jo laskea murtamattomaksi.
"A stroke of brush doesn't guarantee art from bristles." --Kosh
TeknoHog Re: One-time Pad ja fotonit
TeknoHog, 17.3.2002 20:06:25		 Pisteet: +1
Hmm, vaikea uskoa, että olisi olemassa salaus, jota ei voi murtaa. Sillä jos sen voi purkaa tuolla oikealla avaimella, niin mikä estää arvaamasta tuota oikeaa avainta? Vaikka se avain olisi 32kilobitin kokoinen tai vaikka 16Mbitin, niin silti olisi teoriassa mahdollista osua samaan avaimeen tsägällä.
Kyllahan sen voi useimmiten arvata, mutta vaaralla avaimella saat tulokseksi todennakoisesti jotain sekavaa merkkijonoa. Oikea avain on se, joka tuottaa alkuperaisen viestin. Jos et tieda alkuperaista viestia, et voi tietaa arvasitko oikean avaimen.

Sitten on viela olemassa kvanttikryptaus. Tai oikeastaan Quantum Key Distribution koska sita kaytetaan One-Time Padin siirtamiseen osapuolten valilla. Kvanttimekaniikka varmistaa, etta mahdollinen salakuuntelu paljastuu, mutta periaatteessa siinakin jaa mahdollisuus etta salakuuntelun sijasta arvataan avaimen sisalto.
-><-
Good shit, huh? Dozer makes it. It's good for two things: degreasing engines and killing brain cells.
J^hattu Siitä ja sen edistyksellisyydestä
J^hattu, 17.3.2002 03:18:26		 Pisteet: +1
Tietääkseni ensimmäiset kokeilut DNA:n tietojenkäsittelyominaisuuksista tehtiin jo 1994, jolloin ratkaistavana oli niinkutsuttu NP-täydellinen ongelma (joka on tavallisille, "jonomaisesti ajatteleville" tietokoneille erittäin vaikea). Nyt, kahdeksan vuotta myöhemmin, ollan edetty vasta suunnilleen lähtökuoppiin. Tietenkään mitään scifi-ihmeitä ei näinkään uudelta tieteenalalta voi odottaa, mutta jotenkin epäilen, että innokkaimmat saavat odottaa DNA-prosessoreitaan useamman sukupolven ajan...
Re: Siitä ja sen edistyksellisyydestä
Anonyymi kommentoija, 17.3.2002 10:55:38		 Pisteet: +1
Tietääkseni ensimmäiset kokeilut DNA:n tietojenkäsittelyominaisuuksista tehtiin jo 1994, jolloin ratkaistavana oli niinkutsuttu NP-täydellinen ongelma (joka on tavallisille, "jonomaisesti ajatteleville" tietokoneille erittäin vaikea). Nyt, kahdeksan vuotta myöhemmin, ollan edetty vasta suunnilleen lähtökuoppiin. Tietenkään mitään scifi-ihmeitä ei näinkään uudelta tieteenalalta voi odottaa, mutta jotenkin epäilen, että innokkaimmat saavat odottaa DNA-prosessoreitaan useamman sukupolven ajan...
Vuonna 1994 ratkaistiin kauppamatkustajan ongelma jonka kuka tahansa ihminen olisi pystynyt ratkaisemaan käyttämällä kynää ja paperia. Nyt taas ratkaistiin huomattavasti suurempi ongelma johon kukaan ihminen ei olisi pystynyt.
lokori Re: Siitä ja sen edistyksellisyydestä
lokori, 17.3.2002 18:59:41		 Pisteet: +1
Vuonna 1994 ratkaistiin kauppamatkustajan ongelma jonka kuka tahansa ihminen olisi pystynyt ratkaisemaan käyttämällä kynää ja paperia. Nyt taas ratkaistiin huomattavasti suurempi ongelma johon kukaan ihminen ei olisi pystynyt.
Hmm, kauppamatkustajan ongelman optimaalinen ratkaisu syntyy tietokoneelta ajassa O(n^2) (eli ratkaisuaika on verrannollinen kaupunkien määrän toiseen potenssiin).

Miten ihminen ratkaisee muka kauppamatkustajan ongelman järjellisessä ajassa jos kaupunkeja on vähänkin enemmän?
Re: Siitä ja sen edistyksellisyydestä
Anonyymi kommentoija, 18.3.2002 00:08:24		 Pisteet: 0
Hmm, kauppamatkustajan ongelman optimaalinen ratkaisu syntyy tietokoneelta ajassa O(n^2) (eli ratkaisuaika on verrannollinen kaupunkien määrän toiseen potenssiin). Miten ihminen ratkaisee muka kauppamatkustajan ongelman järjellisessä ajassa jos kaupunkeja on vähänkin enemmän?
Kyseessä oli seitsemän kaupungin ongelma.
Re: Siitä ja sen edistyksellisyydestä
Anonyymi kommentoija, 18.3.2002 13:40:26		 Pisteet: +1
.
Hmm, kauppamatkustajan ongelman optimaalinen ratkaisu syntyy tietokoneelta ajassa O(n^2) (eli ratkaisuaika on verrannollinen kaupunkien määrän toiseen potenssiin).
Tämä nyt ei pidä ollenkaan paikkaansa. Kauppamatkustajan ongelma (TSP) on ns. NP-täydellinen ongelma; käytännössä tarkoittaen, että tietokoneella TSP:tä ei todistetusti voida ratkaista polynomisessa ajassa (siis missään O(n^x), kuten kirjoittaja väitti), ellei P=NP. P on luokka, johon kuuluu ongelmat jotka on ratkaistavissa deterministisellä Turing-koneella (naiivisti ajatellen tietokoneella). P=NP konjektuuria taas ei ole kukaan pystynyt todistamaan oikeaksi tai vääräksi, mutta on kaikki syy olettaa ettei näin ole.

Jos joku keksii tavan ratkaista TSP polynomisella algoritmilla, pääsee hän takuulla historiaan erittäin suurena nimenä. P=NP? on ehkä tietojenkäsittelyn suurin avoin kysymys.

Laskennallisesta vaativuudesta kannattaa lukea enemmän teoksesta Papadimitriou: Computational Complexity, jos asia kiinnostaa enemmän.
lokori Re: Siitä ja sen edistyksellisyydestä
lokori, 19.3.2002 19:06:42		 Pisteet: 0
Hmm, kauppamatkustajan ongelman optimaalinen ratkaisu syntyy tietokoneelta ajassa O(n^2) (eli ratkaisuaika on verrannollinen kaupunkien määrän toiseen potenssiin).
Tämä nyt ei pidä ollenkaan paikkaansa. Kauppamatkustajan ongelma (TSP) on ns. NP-täydellinen ongelma; käytännössä tarkoittaen, että tietokoneella TSP:tä ei todistetusti voida ratkaista polynomisessa ajassa (siis missään O(n^x), kuten kirjoittaja väitti), ellei P=NP. P on luokka, johon kuuluu ongelmat jotka on ratkaistavissa deterministisellä Turing-koneella (naiivisti ajatellen tietokoneella). P=NP konjektuuria taas ei ole kukaan pystynyt todistamaan oikeaksi tai vääräksi, mutta on kaikki syy olettaa ettei näin ole.
Seison korjattuna.

Taisi olla niin että tietyillä oletuksilla TSP ratkeaa jopa ajassa O(n lg n), mutta mielivaltainen TSP ei ratkea missään eksponentiaalisessa ajassa.

Jos joku keksii tavan ratkaista TSP polynomisella algoritmilla, pääsee hän takuulla historiaan erittäin suurena nimenä. P=NP? on ehkä tietojenkäsittelyn suurin avoin kysymys.
On ylipäätään hupaisaa miten helppo on esiittää matemaattinen ongelma tai teoreema, jota on käsittämättömän hankala todistaa. Tuotakin on yritetty vängätä suuntaan jos toiseenkin jo aika kauan, mutta mitään lopullista ei ole todettu.

Kokeilkaapas tätä: Montako väriä tarvitaan mielivaltaisen kartan värittämiseen niin että vierekkäiset maat ovat erivärisiä? Vierekkäisyys tulkitaan siten että yhteinen rajapiste ei tee maista vierekkäisiä, vaan pitää olla rajaviiva.

Ko. ongelman ratkaisu löytyy melko helposti intuitiivisesti paperilla kokeilemalla, mutta todistaminen osoittautui todella vaikeaksi.