Browsing by Author "Nissinen, Hannu"

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.