Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



ECCC BOOKS, LECTURES AND SURVEYS > SPECTRUM PROBLEM:

Ondřej Ježil

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

Spectrum Problem

Download


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.


Table of Contents


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