Spectrum problem

• Thesis title in Czech: Problém spektra
• Thesis title in English: Spectrum problem
• Key words: logika prvního řádu|problém spektra|nedeterministický čas
• English key words: first-order logic|spectrum problem|non-deterministic time
• Academic year of topic announcement: 2022/2023
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Algebra (32-KA)
• Supervisor: prof. RNDr. Jan Krajíček, DrSc.
• Author: Bc. Gabriel Krejčí - assigned and confirmed by the Study Dept.
• Date of registration: 07.11.2022
• Date of assignment: 08.11.2022
• Confirmed by Study dept. on: 29.11.2022
• Date and time of defence: 04.09.2023 10:00
• Date of electronic submission: 20.07.2023
• Date of submission of printed version: 24.07.2023
• Date of proceeded defence: 04.09.2023
• Opponents: Michael Kompatscher, Ph.D.

Guidelines

Nastudovat a presentovat definici spektra uzavřené formule 1. řádu a souvislost těchto spekter s třídou výpočetní složitosti NE. Najít příklady zajímavých množin přirozených čísel, která jsou spektra.

Learn and present the definition of a spectrum of a first-order sentence and a connection of spectra to the class of computational complexity NE. Find examples of interesting sets of natural numbers which are spectra.

References

A. Durand, N.D. Jones, J.A. Makowsky and M. More,
Fifty Years of the Spectrum Problem: Survey and New Results,
preprint (submitted to the Bulletin of Symbolic Logic), 2009
http://www.diku.dk/hjemmesider/ansatte/neil/SpectraSubmitted.pdf

R.Fagin, Finite-model theory - a personal perspective, Th.Comp.Sci, 116, (1993), 3-31.

Preliminary scope of work

Problém spektra z teorie konečných modelů je jeden z nejstarších problémů
blízkých slavnému novodobému P vs. NP problému.

Preliminary scope of work in English

The spectrum problem from finite model theory is one of the oldest
problems close to the famous contemporary P versus NP problem.