The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variable. We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations.
Another body of related works is those by Grandjean, Olive and Pudlak which established the variable hierarchy for spectra of sentences using relation and function symbols @cite_17 @cite_16 @cite_19 @cite_12 @cite_10 . Let @math denote the spectra of first-order sentences using up to @math variables with vocabulary consisting of relation and function symbols, and @math denote the restriction of @math to sentences written in prenex normal form with universal quantifiers only and using only @math variables. In his series of papers, Grandjean showed that @math , for each positive integer @math , where @math denotes the class of sets of positive integers accepted by non-deterministic RAM in time @math , and @math is the input integer @cite_17 @cite_16 @cite_19 . By Skolemisation, it is shown that @math , for all @math [Theorem 3.1] GrandjeanO04 . Combined with Cook's hierarchy of non-deterministic time @cite_5 and the known inclusions @math , for each function @math , see @cite_16 , it implies @math , for all @math .
@cite_19 @cite_5 @cite_16 @cite_10 @cite_12 @cite_17
2007053458 2125449161 2031764672 1799262171
The spectrum of a first-order sentence is the set of cardinalities of its finite models. We refine the well-known equality between the class of spectra and the class of sets (of positive integers) accepted by nondeterministic Turing machines in polynomial time. Let @math denote the class of spectra of sentences with d universal quantifiers. For any integer @math and each set of positive integers, A, we obtain: [ A NTIME (n^d ) A Sp (d ) A NTIME (n^d ( n)^2 ). ] Further the first implication holds even if we use multidimensional nondeterministic Turing machines. These results hold similarly for generalized spectra. As a consequence, we obtain a simplified proof of a hierarchy result of P. Pudlak about (generalized) spectra. We also prove that the set of primes is the spectrum of a certain sentence with only one variable. The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using only two variables, but allowing counting quantifiers, the spectra of first-order logic sentences are semilinear and hence, closed under complement. At the heart of our proof are semilinear characterisations for the existence of regular and biregular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices. Our proof also provides a simple characterisation of models of two-variable logic with counting -- that is, up to renaming and extending the relation names, they are simply a collection of regular and biregular graphs. Abstract Define a (∀1 unary)-sentence to be a prenex first-order sentence of unary type (i.e., a type which only contains unary relation and function symbols and constant symbols) with only one (universal) quantifier. A successor structure is a structure 〈 B , S 〉 such that S is a function which is a permutation of the basis B with only one cycle. We exhibit a (∀1, unary)-sentence φ of type S , U 1 , …, U p such that if B is finite then 〈 B , S 〉 is a successor structure if 〈 B , S 〉 satisfies ∃ U 1 , …, ∃ U p ϕ . It implies that ⋃ NRAM( cn )=SPECTRA(∀1, unary), c ⩾1 where NRAM(cn) denotes the class of sets of positive integers accepted by a nondeterministic random access machine in time cn (where n is the input integer) and SPECTRA(∀1, unary) is the class of finite spectra of (∀1, unary)-sentences. Another consequence is that some graph properties (hamiltonicity, connectedness) can be characterised by sentences with unary function symbols and constant symbols and only one variable. This contrasts with the result (by Fagin and De Rougemont) that these two graph properties are not definable by monadic generalized spectra (without function symbols) even in the presence of an underlying successor relation. Given two graphs @math and @math , the Subgraph Isomorphism problem asks if @math is isomorphic to a subgraph of @math . While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time @math using the color-coding technique of Alon, Yuster, and Zwick; (2) in time @math using Courcelle's Theorem; (3) in time @math using a result on first-order model checking by Frick and Grohe; or (4) in time @math for connected @math using the algorithm of Matou s ek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of @math and @math (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time [ f_1(p_1,p_2,..., p_ ) n^ f_2(p_ +1 ,..., p_k) ] exist, where each of @math is one of the 10 parameters depending only on @math or @math . We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of @math gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when @math is a bounded-degree tree of constant pathwidth and @math is a planar graph of bounded pathwidth.