| dc.date.accessioned |
2010-11-25T12:12:57Z |
und |
| dc.date.accessioned |
2017-11-06T11:14:19Z |
|
| dc.date.available |
2010-11-25T12:12:57Z |
und |
| dc.date.available |
2017-11-06T11:14:19Z |
|
| dc.date.issued |
2009-11-30 |
|
| dc.identifier.uri |
http://hdl.handle.net/10138/21323 |
|
| dc.publisher |
Helsingin yliopisto |
fi |
| dc.publisher |
Helsingfors universitet |
sv |
| dc.publisher |
University of Helsinki |
en |
| dc.title |
Luokan P loogisesta karakterisoinnista |
fi |
| ethesis.discipline |
Mathematics |
en |
| ethesis.discipline |
Matematiikka |
fi |
| ethesis.discipline |
Matematik |
sv |
| ethesis.discipline.URI |
http://data.hulib.helsinki.fi/id/44bc4f03-6035-4697-993b-cfc4cea667eb |
|
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/61364eb4-647a-40e2-8539-11c5c0af8dc2 |
|
| ethesis.department |
Institutionen för matematik och statistik |
sv |
| ethesis.department |
Department of Mathematics and Statistics |
en |
| ethesis.department |
Matematiikan ja tilastotieteen 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 |
Korhonen, Janne |
|
| dct.issued |
2009 |
|
| dct.language.ISO639-2 |
fin |
|
| dct.abstract |
Deskriptiivisessä vaativuusteoriassa tutkitaan laskennan vaativuuteen liittyviä kysymyksiä logiikan työkalujen avulla. Tällöin käsitellään tilannetta, jossa laskennan syötteenä toimivat äärelliset mallit. Tässä kehyksessä erinäisiä vaativuusluokkia voidaan karakterisoida etsimällä logiikoita, joilla on kyseistä vaativuusluokkaa vastaava ilmaisuvoima. Klassiset esimerkit tällaisista tuloksista ovat Faginin esittämä epädeterministisen polynomiaalisen ajan karakterisaatio logiikan Σ 1 1 avulla ja Immermanin, Livchakin ja Vardin esittämä deterministisen polynomiaalisen ajan karakterisaatio ensimmäisen kertaluvun inflatorisen kiintopistelogiikan avulla.
Tässä opinnäytetyössä tarkastellaan Gurevichin esittämää kysymystä polynomiaalisessa ajassa ratkeavien kielten luokan P vahvasta loogisesta karakterisaatiosta. Kyseinen kysymys on yksi äärellisen malliteorian haastavimpia ongelmia. Kysymyksen esittelyyn tarvittavan peruskoneiston läpikäynnin lisäksi tässä käsitellään myös sen yhteyksiä laskennan vaativuusteoriassa keskeiseen P-NP-ongelmaan.
Gurevichin kysymyksestä voidaan esittää myös rajoitetumpia versioita, mikäli käsitellään tilannetta, jossa laskennan syötteenä voi olla vain kiinnitetyn malliluokan K malleja. Tällöin luokan P karakterisointi helpottuu, ainakin jos luokka K on riittävän suppea. Tässä opinnäytetyössä käydään läpi Grohen esittämä tulos siitä, että mikäli luokaksi K valitaan 3-yhtenäisten tasoverkkojen luokka, niin ensimmäisen kertaluvun inflatorinen kiintopistelogiikka karakterisoi polynomiaalisessa ajassa laskettavat kielet. |
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 |
Kontinen, Juha |
|
| ethesis.supervisor |
Luosto, Kerkko |
|
| 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-fe201006041960 |
|
| dc.type.dcmitype |
Text |
|
| dct.alternative |
On the logical characterisation of class P |
en |
| 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 |
