| dc.date.accessioned |
2013-12-16T07:38:26Z |
und |
| dc.date.accessioned |
2017-10-24T12:21:17Z |
|
| dc.date.available |
2013-12-16T07:38:26Z |
und |
| dc.date.available |
2017-10-24T12:21:17Z |
|
| dc.date.issued |
2013-12-16T07:38:26Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/3372 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/3372 |
|
| dc.title |
PTIME and Generalized Quantifiers |
en |
| 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 |
Nissinen, Hannu |
|
| dct.issued |
2013 |
|
| dct.language.ISO639-2 |
eng |
|
| dct.abstract |
We consider the problem of finding a reasonable logical characterization for the complexity class PTIME in the class of all finite models. We approach this problem by adding a set Q_n of n-ary generalized quantifiers to the infinitary finite variable logic L^k_{∞ Ω}. More precisely, we show that it is not possible to characterize PTIME in such a way. This result is obtained by constructing models A(G) and B(G) which are L^k_{∞ Ω}(Q_n)-equivalent and by showing that there is a PTIME computable boolean query q such that q(A(G)) \neq q(B(G)) for any appropriate finite graph G. |
en |
| dct.abstract |
Työssä käsitellään ongelmaa tyydyttävän loogisen karakterisaation löytämiseksi vaativuusluokalle PTIME kaikkien äärellisten mallien luokassa. Tätä ongelmaa lähestytään lisäämällä kaikki n-paikkaiset yleistetyt kvanttorit infinitaariseen äärellisen monen muuttujan logiikkaan L^{Ω}_{∞ Ω}. Työssä todistetaan, ettei ole mahdollista karakterisoida vaativuusluokkaa PTIME kyseisellä tavalla. Tämä tulos saavutetaan konstruoimalla mallit A(G) ja B(G), jotka ovat L^k_{∞ Ω}(Q_n)-ekvivalentteja ja näyttämällä, että on olemassa polynomiaalisessa ajassa laskettava boolen kysely q, jolle pätee q(A(G)) \neq q(B(G)) kaikilla sopivilla äärellisillä verkoilla G. |
fi |
| dct.language |
en |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/eng |
|
| ethesis.language |
English |
en |
| ethesis.language |
englanti |
fi |
| ethesis.language |
engelska |
sv |
| 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-fe2017112251630 |
|
| dc.type.dcmitype |
Text |
|
