PTIME and Generalized Quantifiers
| Title: | PTIME and Generalized Quantifiers |
| Author(s): | Nissinen, Hannu |
| Contributor: | University of Helsinki, Faculty of Science, Department of Mathematics and Statistics |
| Discipline: | Mathematics |
| Language: | English |
| Acceptance year: | 2013 |
| 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.
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.
|
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
| PROGRADU.pdf | 493.3Kb |
This item appears in the following Collection(s)
-
Faculty of Science [4203]