Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
Spectrum problem
Thesis title in Czech: Problém spektra
Thesis title in English: Spectrum problem
Key words: Scholzův problém, spektrum, Asserův problém, zobecněné spektrum, Cobhamova věta
English key words: Scholz's problem, spectrum, Asser's problem, generalized spectrum, Cobham's theorem
Academic year of topic announcement: 2019/2020
Thesis type: Bachelor's thesis
Thesis language: angličtina
Department: Department of Algebra (32-KA)
Supervisor: prof. RNDr. Jan Krajíček, DrSc.
Author: hidden - assigned and confirmed by the Study Dept.
Date of registration: 21.10.2019
Date of assignment: 21.10.2019
Confirmed by Study dept. on: 21.11.2019
Date and time of defence: 29.06.2020 10:00
Date of electronic submission:02.06.2020
Date of submission of printed version:04.06.2020
Date of proceeded defence: 29.06.2020
Opponents: doc. Mgr. Jan Šaroch, Ph.D.
 
 
 
Guidelines
Nastudovat a presentovat definici spektra uzavřené formule 1. řádu a souvislost těchto spekter s množinami z třídy výpočetní složitosti NE. Najít příklady zajímavých množin přirozených čísel, která jsou spektra.
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.
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html