Under the auspices of the Computational Complexity Foundation (CCF)

ECCC BOOKS, LECTURES AND SURVEYS > SPECTRUM PROBLEM:

Ondřej Ježil

Faculty of Mathematics and Physics,
Charles University in Prague, 2020

Spectrum Problem

Abstract

We study spectra of first-order sentences. After providing some interesting examples of spectra we show that the class of spectra is closed under some simple set-theoretic and algebraic operations. We then define a new class of definable operations generalizing the earlier constructions. Our main result is that the class of these operations is, in a suitable technical sense, closed under a form of iteration. This in conjunction with Cobham’s characterisation of FP offers a new proof of Fagin’s theorem and also of the Jones-Selman characterisation of spectra as NE sets.

```Introduction
1 Preliminaries
1.1 Logic
1.2 Cobham’s characterization of FP
2 Elementary results on spectra
2.1 Interesting examples of spectra
2.1.1 Spectra based on factors
2.1.2 Mutually orthogonal latin squares
2.2 Operations on spectra
2.2.1 Set operations on spectra
2.2.2 Arithmetical operations on spectra
3 \Sigma_1^1-definable functions
3.1 Basic notions
3.2 \Sigma_1^1-definability of FP
3.3 Fagin’s theorem
3.4 F\Sigma_1^1 operations on generalized spectra
Concluding remarks
```

Number of pages: 36

ISSN 1433-8092 | Imprint