Given a formula \(\phi\) of some logic, the spectrum of
\(\phi\), denoted \(\rm{spec}(\phi)\), is the set of non-negative
integers \(n\) such that \(\phi\) has a model of cardinality
\(n\). The notion of a spectrum has been introduced by Scholz in
1952,, along with the main problem: characterize sets of integers
which appear as spectra of a given class of formulae. Fagin has
shown in his seminal paper in 1974 that a set \(S\) is a spectrum of
some first order formula \(\phi\) iff the set of unary
representations of elements of \(S\) is in {\bf NP}. This also shows
that the main open problem from spectra theory, called Asser's
conjecture -- whether a complement of a spectrum is also a spectrum
-- is equivalent to the complexity theoretic problem
NEXPTIME=co-NEXPTIME. An interesting question is, what
happens when we put restrictions on the vocabulary, formulae, or
models involved? We are going to talk about the following
restrictions:
- We consider only models of bounded degree (to be more precise,
models whose Gaifman graphs are of bounded degree). In this case,
we provide lower and upper complexity theoretic bounds for spectra
of this kind, with only a polylogarithmic gap.
- We consider only models whose Gaifman graphs are
planar. Again, we provide lower and upper complexity theoretic
bounds for spectra of this kind, and the gap is polynomial. We can
also consider only formulae whose all models are planar graphs. In
this case, the gap is bigger (the lower bound uses just
logarithmic memory).
- We consider only formulae of \(C^2\) logic, that is, using
only two variables and counting up to some threshold (``there
exist at least \(k\) elements \(x\) such that \(\phi(x,y)\)''). In
this case, we show that spectra are exactly ultimately periodic
sets, and in the more general multi-dimensional case where we
count the number of elements satisfying predicate \(P_i\) for
\(i=1,\ldots,k\), they are exactly semilinear sets. This shows
that Asser's conjecture holds for \(C^2\) logic.
- Let \(\operatorname{spec}_k\) be spectra of formulae of
\(FO_k\) logic (using \(k\) variables). We show that for \(k\geq
2\) \(\operatorname{spec}_k \subsetneq
\operatorname{spec}_{2k+2}\), hence the variable hierarchy does
not collapse.
|
