| dc.date.accessioned |
2010-11-25T12:12:44Z |
und |
| dc.date.accessioned |
2017-11-06T11:05:12Z |
|
| dc.date.available |
2010-11-25T12:12:44Z |
und |
| dc.date.available |
2017-11-06T11:05:12Z |
|
| dc.date.issued |
2007-10-08 |
|
| dc.identifier.uri |
http://hdl.handle.net/10138/21314 |
|
| dc.publisher |
Helsingin yliopisto |
fi |
| dc.publisher |
Helsingfors universitet |
sv |
| dc.publisher |
University of Helsinki |
en |
| dc.title |
Nashin tasapainon löytämisen laskennallinen vaativuus |
fi |
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/225405e8-3362-4197-a7fd-6e7b79e52d14 |
|
| ethesis.department |
Institutionen för datavetenskap |
sv |
| ethesis.department |
Department of Computer Science |
en |
| ethesis.department |
Tietojenkäsittelytieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Hassinen, Marja |
|
| dct.issued |
2007 |
|
| dct.language.ISO639-2 |
fin |
|
| dct.abstract |
Tässä tutkielmassa käsitellään approksimatiivisen Nashin tasapainon löytämisongelmaa laskennallisen vaativuuden kannalta. Vaikka Nashin tasapainon tiedetään olevan aina olemassa, on tasapainon löytäminen osoittautunut vaikeaksi ongelmaksi.
Approksimatiivisen Nashin tasapainon löytämisongelma on PPAD-ongelmaluokan täydellinen ongelma. PPAD-luokkaan kuuluvat sellaiset etsintäongelmat, joissa etsittävän ratkaisun olemassaolo seuraa suunnattujen graafien pariteettiargumentista. Suunnattujen graafien pariteettiargumentti toteaa, että jos graafin jokaisen solmun lähtö- ja tuloasteet ovat korkeintaan yksi ja graafissa on tunnettu lähdesolmu, niin graafissa on myös nielusolmu tai toinen lähdesolmu.
PPAD-täydellisyyden takia on luultavaa, ettei approksimatiivista Nashin tasapainoa voi löytää polynomisessa ajassa.
Tässä kirjoituksessa esitetään uudelleenmuotoiltu ja tarkennettu versio approksimatiivisen Nashin tasapainon löytämisongelman PPAD-vaikeustodistuksesta. Lisäksi esitetään todistus ongelman kuulumiselle luokkaan PPAD. Vastaavaa todistusta ei löydy kirjallisuudesta, vaikka approksimatiivisen Nashin tasapainon löytämisongelman kuuluminen luokkaan PPAD mainitaan. |
fi |
| dct.language |
fi |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/fin |
|
| ethesis.language |
Finnish |
en |
| ethesis.language |
suomi |
fi |
| ethesis.language |
finska |
sv |
| ethesis.supervisor |
Nurmi, Petteri |
|
| ethesis.supervisor |
Kääriäinen, Matti |
|
| ethesis.supervisor |
Kivinen, Jyrki |
|
| ethesis.supervisor |
Pasanen, Tomi |
|
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| dct.identifier.urn |
URN:NBN:fi-fe200805091360 |
|
| dc.type.dcmitype |
Text |
|
| dct.rights |
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. |
en |
| dct.rights |
Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. |
sv |
| dct.rights |
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. |
fi |
