Abstract
This paper, originally published in ACM Transactions on Computational Logic, addresses a fundamental question in finite model theory: the expressive power of first-order logic when the number of variables is restricted. The authors provide a definitive answer to the long-standing "variable hierarchy" problem, proving that the hierarchy of first-order spectra is infinite. Furthermore, the research demonstrates a significant reduction for Asser’s conjecture, showing that the question of whether spectra are closed under complement can be settled by examining sentences restricted to just three variables and binary relations.
Introduction
In mathematical logic, the spectrum of a first-order sentence is defined as the set of all positive integers $n$ such that the sentence has a model of size $n$. Since the 1950s, the study of spectra has been central to understanding the intersection of logic and computational complexity. Two primary questions have dominated this field:
- Asser’s Conjecture: Is the class of spectra closed under complement? This is equivalent to the major complexity theory question of whether the class NE (Non-deterministic Exponential Time) is equal to co-NE.
- The Variable Hierarchy: Does increasing the number of variables ($x_1, x_2, \dots, x_k$) allowed in a first-order sentence increase the class of sets of integers that can be defined?
Previously, some researchers conjectured that the hierarchy might collapse to just three variables, as three variables are sufficient to simulate a universal Turing machine. This paper refutes that conjecture, establishing that the hierarchy is indeed infinite while simultaneously providing a new focal point for Asser's conjecture.
Methodology: Bridging Logic and Complexity
The authors employ the tools of descriptive complexity to establish a correspondence between the number of variables in a sentence and the time complexity of a Non-deterministic Turing Machine (NTM) that recognizes the spectrum.
Encoding Computations
To prove the hierarchy's separation, the authors represent the "space-time diagram" of an NTM computation as a grid. By utilizing specialized "shift operators" ($\Delta_h, \Delta_v$), they demonstrate how to navigate this computational grid using a minimal number of variables. To refine these results, they transition from a standard $N \times N$ grid to a more sophisticated coordinate system ($N^k \times R$), allowing for a tighter mapping between variable counts and computational bounds.
Padding and Separation
The proof of an infinite hierarchy relies on "padding arguments" common in complexity theory. By showing that $Spec_k$ (the set of spectra definable with $k$ variables) can be simulated by machines with specific time bounds, and then using those bounds to find sets that require more variables, the authors establish a strict separation between different levels of the hierarchy.
Key Insights and Results
The Infinite Hierarchy
The primary result of the paper is the proof that for every integer $k \ge 3$, $Spec_k \subsetneq Spec_{2k+2}$. This confirms that the variable hierarchy does not collapse; adding variables consistently allows for the definition of more complex sets of integers. This result also extends to Existential Second-Order logic ($SO\exists$), providing a new structural understanding of the complexity class NP.
The Power of Three
Despite the infinite nature of the hierarchy, the authors identify a unique property of the lower bound. They demonstrate that $NTIME[2^n]$—a significant complexity class—is contained within $Spec_3$. This "engine" allows them to prove a surprising reduction: NE = co-NE if and only if the complement of every spectrum defined by a 3-variable sentence (using only binary relations) is also a spectrum.
This creates a fascinating tension in the results: while more variables provide more expressive power, the fundamental closure properties of the entire class are determined by the behavior of sentences at the very bottom of the hierarchy.
Discussion and Limitations
While the paper successfully proves the hierarchy is infinite, it leaves a specific "gap" in the separation. The authors prove $Spec_k \subsetneq Spec_{2k+2}$, but they do not prove the tighter conjecture that $Spec_k \subsetneq Spec_{k+1}$. While this incremental separation is widely expected to be true, it remains an open problem for future research.
Additionally, the reduction of Asser’s conjecture highlights the specific importance of binary relations. Previous research indicated that 2-variable logic with counting quantifiers is significantly weaker, suggesting that 3-variable logic with binary relations represents the true "frontier" of complexity for these logical problems.
Conclusion
This work clarifies the structural properties of first-order spectra and their relationship to computational complexity. By proving the hierarchy is infinite, the authors have corrected a long-standing misconception in the field. By reducing Asser's conjecture to the 3-variable case, they have provided researchers with a specific, simplified target for investigating one of the most significant open problems in logic and complexity theory.
Summary updated